Pen & Paper Programming (Part 2)
We left off last time having covered the first 3 lines of the following Erlang function to calculate the permutations of a list:
1: -module(permsModule).
2: -export([perms/1]).
3:
4: perms([]) -> [ [] ];
5: perms(List) ->
[ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ].
Lines 4 and 5 are the core of this function and therefore the most difficult to explain and understand. Last time I gave you some output from running the function to ponder:
4> EmptyList = [].
[]
5> permsModule:perms(EmptyList).
[[]]
6> [ [] ].
[[]]
7> ListOfOne = [1].
[1]
8> permsModule:perms(ListOfOne).
[[1]]
9> [ [1 | [] ] ].
[[1]]
Now, lets connect the dots from this output to the function code above. In the output above, I make a call to perms passing in [ ], the empty list, as an argument. I get back [ [ ] ], a list containing the empty list. If you remember, the purpose of this function is to return a list of the permutations of a given list; an empty list has one permutation, the empty list, so it makes sense we get back a list with one element, the empty list.
It makes sense logically, but why does it work in code? If you look at lines 4 and 5 of the function code, you will see that line 4 ends with a semi-colon, while line 5 ends with a period. In Erlang, like English, a period marks the end of something. In this case a function definition. A semi-colon is used to delineate a clause within a function definition. So line 4 and 5 are 2 separate clauses of the same function.
When we call a function in Erlang, pattern matching is used to determine which clause to execute for a given input. So when we call perms([ ]), we will execute line 4, as the empty list parameter matches the empty list in the clause definition. Now that Erlang knows which clause to execute, the "body" of the function, everything after the -> is executed. As with many scripting languages, the last part of the function body becomes the return value, in this case [ [ ] ].
Moving on to the next call of perms, with [ 1 ]. Again, logically it makes sense for this to return [ [ 1 ] ] as there are no other permutations of a one element list other than itself. In code, Erlang again looks for a match amongst the clauses of this function. [ 1 ] does not match the empty list in line 4, so the body of line 5 is executed, since the "List" variable acts as a catch-all (or match-all).
Line 5 has a lot going on:
1: perms(List) ->
[ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ]
The structure being used here is a list comprehension, indicated by the ||. If you are familiar with Python, you would have seen list comprehensions before, but if you are coming from a .Net background, then a more direct comparison might be a reduced format for each loop.
List comprehensions create lists. The left side (before the ||) of a list comprehension gathers pieces from the right side of a list comprehension and sticks them together into a new list. The canonical list comprehension example is to take an existing list of numbers and add one to every element. Here is it in Erlang:
1> [ X+1 || X <- [1,2,3,4,5] ].
[2,3,4,5,6]
The equivalent in C# would look something vaguely like this:
1: int[] numbers = { 1,2,3,4,5 }; 2: List<int> MyNumbers = new List<int>(numbers);
3: List<int> MyNumberPlusOne = new List<int>();
4:
5: foreach ( int aNumber in MyNumber)
6: { 7: MyNumberPlusOne.Add( (aNumber + 1) );
8: }
So in the Erlang code, each element of the list gets assigned to X, one is added to X to produce the first element of the resulting list and then the next element of the original list is assigned to X, one is added to this X, and so on.
2 more bits of Erlang syntax to cover and then we'll simulate this code through. First, the syntax [ Head | Tail ] is just a list constructor in disguise; this translates into take "Head" and make it the first element in a list, followed by "Tail." List--[Head] is list subtraction, so take everything in the list "Head" and subtract it out of "List". We'll see an example of that in a second.
To start our code simulation, we'll take the clause being run and do some simple substitution of the "List" parameter with the argument [1]:
perms([1]) ->
[ [ Head | Tail ] || Head <- [1], Tail <- perms([1]--[Head]) ]
Remembering the previous example, "Head" will be set to the first element of the [1], which is 1:
perms([1])->
[ [ 1 | Tail ] || 1 , Tail <- perms([1]--[1]) ]
[1]--[1] is the empty list, so using what we know about what perms( [ ] ) is:
perms([1]) ->
[ [ 1 | Tail ] || 1, Tail <- [ [ ] ] ]
perms([1]) ->
[ [ 1 | Tail ] || 1, [] ]
perms([1]) ->
[ [1 | [] ] ]
perms([1]) ->
[ [1] ]
With all that work behind us just to figure out perms([1]), here is perms([1,2]) simulated out. Take note of how the list comprehension "iterates" using both 1 and 2 as the "Head":
perms([1,2])->
with 1 as Head
[ [ 1 | Tail ] || 1, Tail <- perms([1,2]--[1]) ]
[ [ 1 | Tail ] || 1, Tail <- perms([2]) ]
[ [ 1 | 2 ] || 1, 2 ]
[1,2]
with 2 as Head
[ [ 2 | Tail ] || 2, Tail <- perms([1,2]--[2]) ]
[ [ 2 | Tail ] || 2, Tail <- perms([1]) ]
[ [ 2 | 1 ] || 2, 1 ]
[2,1]
combine the results
[ [1,2],[2,1] ]
From here, simulating out perms([1,2,3]) is not so bad. Here's the full expansion with 1 as "Head":
perms([1,2,3]) ->
with 1 as Head
[ [ 1 | Tail ] || 1, Tail <- perms([1,2,3]--[1]) ]
with 2 as Head to Tail call of perms([2,3])
[ [ 2 | Tail ] || 2, Tail <- perms([2,3]--[2]) ]
[ [ 2 | 3 ] ] || 2, 3 ]
[2,3]
with 3 as Head to Tail call of perms([2,3])
[ [ 3 | Tail ] || 3, Tail <- perms([2,3]--[3]) ]
[ [ 3 | 2 ] ] || 3, 2 ]
[3,2]
combine the results
[ [2,3],[3,2] ]
[ [ 1 | Tail ] || 1, Tail <- [ [2,3],[3,2] ] ]
with [2,3] as Tail
[ 1 | [2,3] ]
[ 1,2,3 ]
with [3,2] as Tail
[ 1 | [3,2] ]
[ 1,3,2 ]
combine the results
[ [ 1,2,3] , [1,3,2] ]
with 2 as Head...