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...
With two monitors at home, I find myself using less and less paper while programming. Whenever possible, instead of jotting down notes on a piece of scrap paper, I use my second screen. Not only do I save paper, it makes it automatic to save my notes in for later use. In general, it just feels right to be working mostly in electronic formats.
However, there is always still a place at my desk for a pen and pad of paper for those tasks which still just don't translate as well to the screen. One such task is code simulation, familiar to anyone who's taken an introduction to programming class. The idea is to take a piece of code, often some kind of looping or recursive structure and explicitly spell out exactly what would happen given a certain input. By doing this you can reveal obscured bugs or just plain figure out how the code works.
Typically this technique is used in introductory courses, because as you learn more about a language and programming, you tend to internalize what was a pen and paper process into a wholly mental, almost unconscious one.
I have not been taking any introduction to programming courses, but I have been reading Programming Erlang, a new book from the Pragmatic Programmers by one of the designers of the Erlang language, Joe Armstrong.
Erlang is a functional language, designed specifically for distributed, fault tolerant systems. Originally it was used in Ericsson's telecommunication switches. So if you, like me, are not that familiar with functional languages, Erlang can seem pretty strange at first.
I was getting over the strangeness of it all until Armstrong presented a bit of code that takes a list of returns a list of all its permutations. Up to this point he has explained every code snippet in detail, but for this piece of code he tells the reader to figure it out on the reader's own. And this situation brings us back to code simulation, and my pen and paper, ready for a worthy challenge.
I struggled with how to present this since I can't assume anyone reading this has any level of familiarity with Erlang. I decided to go with the full immersion approach; please check out Armstrong's book if your interest is peaked.
So, here's what the permutations function was supposed to do. The following is an example session within the Erlang interpreter:
1> c(perms2).
{ok,perms2}
2> MyList = [ 1,2,3 ].
[1,2,3]
3> perms2:
module_info/0 module_info/1 perms/1
3> perms2:perms(MyList).
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Like I said full immersion; the lines with the number> are user input, the lines below are output from Erlang. Line 1> is me telling Erlang to compile the code in permsModule.erl and import this code into my interpreter session. Line 2> is me creating a list with the elements 1, 2 and 3. Line 3> is me invoking the perms function from the imported code (in a kind of namespace.function syntax) with the list I created as an argument. Hopefully the resulting output makes sense, it is a list of lists, each list within the greater list being a permutation of the original list.
So far so good? Without further ado, the Erlang code for the perms function:
1: -module(permsModule).
2: -export([perms/1]).
3:
4: perms([]) -> [ [] ];
5: perms(List) ->
[ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ].
Line 1 tells the Erlang compiler that the code in this file is part of a module called permsModule. Line 2 says that when someone else imports this module they can use a function called perms which takes one argument (sadly this is not as exciting as the idea of figuring out what the function perms divided by one is supposed to mean). Line 3 is a blank line I put in to make the code look nicer.
With 60% of the code now covered, my work here is over halfway complete right? I think it is time for a break. I'll finish this code off next time, but before I go, here's some more sample output from that previous Erlang interpreter session for you to ponder:
4> EmptyList = [].
[]
5> permsModule:perms(EmptyList).
[[]]
6> [ [] ].
[[]]
7> ListOfOne = [1].
[1]
8> permsModule:perms(ListOfOne).
[[1]]
9> [ [1 | [] ] ].
[[1]]