## Sunday, October 27, 2013

### Erlang List Comprehension with Multiple Generators

I was a bit lost with the permutation example from the Erlang docs. The post by Peter Miller helped. Anyway, here is my explanation on its working.

Generate permutations of all elements in a list.
perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L -- [H])].
Let's say it's in a module named test. Compile and load it. Call it will the list [1,2,3].
1> test:perms([1,2,3]).
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
To understand this let us look at list comprehension. Single generators are straight forward.
2> [X || X <- lists:seq(1, 5)].
[1,2,3,4,5]
Read it as, X such that X is generated from a list with sequence 1 to 5. Let us consider list comprehension with multiple generators.
3> [{X, Y} || X <- [1,2,3], Y <- [10,11,12]].
[{1,10},
{1,11},
{1,12},
{2,10},
{2,11},
{2,12},
{3,10},
{3,11},
{3,12}]
Here we are constructing a tuple {X, Y} such that X is generated from list [1,2,3] and Y is generated from the list [10,11,12]. We can see the pairing from the generated list of tuples. It takes the first element from the first list and combines it with each individual element from the second list, then takes the second element from the first list and combines with all elements from the second list and so on recursively. Constructing a list. A non-empty list has a head and a tail. So we can represent a list as [H|T].
4> hd([1]).
1
5> tl([1]).
[]
6> [ 1 | [] ].
[1]
7> [ 1 | [2,3] ].
[1,2,3]
8> [H|T] = [1,2,3].
[1,2,3]
9> H.
1
10> T.
[2,3]
Let's write down the reduction steps.
perms([]) = [ [] ].

perms([1]) = [ 1 | [] ]
= [ [1] ].
perms([1,2])
% produce a list with head as 1 and tail generated from the list obtained from
% the permutation of the original list without the current head.
= [ [1|T] || T <- perms([2]) ]
= [ [1|[2]] ]
= [ [1, 2] ]
% produce a list with head as 2 and tail generated from the list obtained from
% the permutation of the original list without the current head.
= [ [2|T] || T <- perms([1]) ]
= [ [2|[1]] ]
= [ [2, 1] ]
Combining both we get,
perms([1,2]) = [ [[1|T] || T <- perms([2])],
[[2|T] || T <- perms([1])] ].

= [ [[1|T] || T <- [[2]]],
[[2|T] || T <- [[1]]] ].

= [ [1|[2]],
[2|[1]] ].

= [ [1,2], [2,1] ].
perms([1,2,3]) = [ [[1|T] || T <- perms([2,3])],
[[2|T] || T <- perms([1,3])],
[[3|T] || T <- perms([1,2])] ].

= [ [[1|T] || T <- [[2,3], [3,2]]],
[[2|T] || T <- [[1,3], [3,1]]],
[[3|T] || T <- [[1,2], [2,1]]] ].

= [ [1|[2,3]], [1|[3,2]],
[2|[1,3]], [2|[3,1]],
[3|[1,2]], [3|[2,1]] ].

= [ [1,2,3], [1,3,2],
[2,1,3], [2,3,1],
[3,1,2], [3,2,1] ].