[erlang-questions] List comprehensions

[Richard Carlsson]

Liam Clarke wrote:
 > How could I rewrite the permutations comprehension as a function so I
 > can sprinkle it with io:format()s so as to understand what's happening
 > better?

I really don't think that would be much helpful in this case. It drowns 
you in mostly irrelevant details instead of helping you focus on the 
concept of comprehensions. More below.

 > I think I get how dual generators work now -
 > [[H|[T]] || H <- [a,b,c],T <- [1,2,3]]
 >
 > will yield
 >
 > [[a,1],[a,2],[a,3],[b,1],[b,2],[b,3],[c,1],[c,2],[c,3]]

Yes. Note that [H | [T] ] could be written [H | [T | [] ] ], or (much 
simpler) [H, T]. Contrast this to [H | T], which "adds" H to the 
beginning of the list T. It's a bit misleading to use 'T' in the former 
case, since it is not used as a "tail", but as a second element.

> perms([]) ->[[]];
> perms(L) ->
>     [[H|T] || H <- L, T <- perms(L--[H])].
> 
> I'm having trouble with understanding what's happening. I assume it's 
> evaluated left to right from the ||, and I'm sort of grasping the 
> general interplay of the generators and the recursion, but I'm also 
> missing it at the same point.

Read it like this:
    An empty list only has one, trivial, permutation.
    For a nonempty list L, its permutations are all lists [H|T]
    such that:
      - the first element H is an element in L
      - the rest (T) is a permutation of the remaining elements
        of L after you remove the element H.
    Since the two generators will produce all combinations of picking
    an element H in L and some permutation of L--[H], you know you will
    get all permutations of L.
    You also know what order the combinations will be produced in
    (compare your dual generator example above), since this is part of
    the specified behaviour of list comprehensions.

Try to think equationally rather than procedurally; it helps not only 
here, but in most kinds of recursive functions.

     /Richard