jump to navigation

Thinking Erlang, or Creating a Random Matrix without Loops 26 February 2009

Posted by Oliver Mason in erlang, misc, programming.
trackback

For a project, my Erlang implementation of a fast PFNET algorithm, I needed to find a way to create a random matrix of integers (for path weights), with the diagonal being filled with zeroes.  I was wondering how best to do that, and started off with two loops, an inner one for each row, and an outer one for the full set of rows.  Then the problem was how to tell the inner loop at what position the ‘0’ should be inserted.  I was thinking about passing a row-ID, when it suddenly clicked: lists:seq/2 was what I needed!  This method, which I previously thought was pretty useless, creates a list with a sequence of numbers (the range is specified in the two parameters).  For example,

1> lists:seq(1,4).
[1,2,3,4]
2> lists:seq(634,637).    
[634,635,636,637]
3> lists:seq(1000,1003).
[1000,1001,1002,1003]

Now I would simply generate a list with a number for each row, and then send the inner loop off to do its thing, filling the slot given by the sequence number with a zero, and others with a random value.

But now it gets even better.  Using a separate (tail-)recursive function for the inner loop didn’t quite seem right, so I thought a bit more about it and came to the conclusion that this is simply a mapping; mapping an integer to a list (a vector of numbers, one of which (given by the integer) is a zero).  So instead of using a function for filling the row, I call lists:seq again and then map the whole thing.  This is the final version I arrived at, and I’m sure it can still be improved upon using list comprehensions:

random_matrix(Size, MaxVal) ->
  random:seed(),
  lists:map(
    fun(X) ->
      lists:map(
          fun(Y) ->
              case Y of 
                 X -> 0; 
                 _ -> random:uniform(MaxVal)
                 end
              end,
          lists:seq(1,Size))
      end,
    lists:seq(1,Size)).

This solution seems to be far more idiomatic, and I am beginning to think that I finally no longer think in an imperative way of loops, but more in the Erlang-way of list operations.  Initially this is hard to achieve, but with any luck it will become a lot easier once one is used to it.  Elegance, here I come!

Example run:

4> random_matrix(6,7).  
[[0,1,4,6,7,4],
 [3,0,5,7,5,4],
 [5,1,0,2,5,2],
 [4,2,4,0,3,1],
 [4,4,3,3,0,1],
 [5,7,3,2,2,0]]

Note: I have used random:seed/0 above, as I am happy for the function to return identical matrices on subsequent runs with the same parameters. To get truly random results, that would have to be left out. However, for my benchmarking purposes it saved me having to save the matrix to a file and read it in, as I can easily generate a new copy of the same matrix I used before.

Advertisements

Comments»

1. Gleb Peregud - 27 February 2009

Hi.

Your solution can be improved by using tail recursive function with two accumulators. Here is the code: http://gist.github.com/71660

Best regards,
Gleb Peregud

2. Gleb Peregud - 27 February 2009

Sorry. I should have mentioned why this solution is better. It is better in terms of speed and memory.

lists:seq/1 is called Size+1 times in your code. On each call it creates a list of Size elements, which is in fact unused. By unrolling it into the tail recursive function you are not creating any extra lists. Unfortunately Erlang compiler is not capable of unrolling your code into tail recursive function by itself.

Of course your code is much more readable :)

3. andre - 27 February 2009

You could get something more efficient (avoiding the creation of intermediary lists) and arguably just as readable like this:

http://codepad.org/Fz0MLRqT

4. ojmason - 27 February 2009

Thanks! Yes, I don’t claim that my solution is optimal in any sense, and it does indeed create the matrix twice, once with coordinates and then mapped with random values.

What you mention touches on a fundamental impression I have with functional languages, in that they’re very high-level, but not all that efficient. You can express this matrix creation very elegantly in a one-liner with seq’n’map, but it has far more overheads than a more ‘manual’ approach avoiding list idioms.

However, I’m banking on the multicore future to make that less of a concern!

5. ojmason - 27 February 2009

@andre: yes, it is very readable, though it looks very much like an imperative program, rather than a functional one. And it’s very loopy!

6. Andre - 28 February 2009

@ojmason: Well, one could always rename “for” to something more obscure :P Maybe if you move the funs to named functions and just pass them as parameters to “for” it’ll look more functinal…

Note that in haskell your solution would be efficient because the lists you’re mapping over are generated lazily. I’m not sure if the erlang libs have something with this “stream-like” behaviour. That would be nice, because map/fold-based solutions are really elegant.

7. Zvi - 5 March 2009

why not?

[ [ case Y of X->0; _->random:uniform(MaxVal) end ||
Y<-lists:seq(1,Size) ] || X<-lists:seq(1,Size) ].

Zvi

8. Zvi - 5 March 2009

The problem is that Erlang doesn’t have first-class ranges (or better like NDRange in OpenCL – N-dimensional spaces).
Think about CUDA/OpenCL – running kernel over NDRange, it’s just map over NDRange.
For your example:

[ case Y of X->0; _random:unfiorm(MaxVal) || {X,Y}<-Range2D(1..Size,1..Size) ]

then you can reshape (like in Matlab) the result if you want.

Zvi

9. ojmason - 5 March 2009

Yes! That was something I was looking for but couldn’t think of. Of course you need to use two nested list comprehensions for this.

Thanks!

10. graeme defty - 21 January 2010

A bit late to the party, but . . .

I am new to functional programming in general (and Erlang in particular) but my plain (i.e. no list comprehension) attempt to do this in an Erlang-y way was as follows.

random_matrix(Size, MaxVal) ->
  random:seed(),
  r_matrix(Size, MaxVal, Size, []).

r_matrix(   _,     _,  0,Acc) ->  Acc;
r_matrix(Size,MaxVal,Row,Acc) -> 
  r_matrix(Size, MaxVal, Row-1, [r_row(MaxVal, Row, Size, []) | Acc]).

r_row(     _,   _,   0, Acc) -> Acc;
r_row(Maxval, Row, Col, Acc) -> 
  r_row(Maxval, Row, Col-1, [r_element(Maxval, Row, Col) | Acc]).

r_element(_     , Row, Col) when Row == Col -> 0;
r_element(MaxVal,_Row,_Col) ->
  random:uniform(MaxVal).

I think this pretty much avoids all the problems mentioned above (i.e. No loops. No misc variables (X,Y and chums). No double creation of anything. The matrix is built one row at a time from the back. Each row is built one element at a time from the back. the code approaches the declarative, and should run efficiently.) As a result, i think it is quite readable (though I would not have said that a month ago!) The odd spacing in the parameter lists causes them to line up in a fixed-width font, which makes it easier to see that the functino definitions match.

It is particularly nice when each function-clause definition is on a single line,, but since that too it up to column 96 I had to wrap them onto two lines :-(

Anyway, just my $0.02

11. Seanne Mc Guinness - 4 March 2010

Interesting approach….


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: