Erlang: so awesome it makes my brain bleed

I have read several times Erlang is a pretty cool functional language. I even bought the book. The book has a lot of cool examples and I enjoyed skimming the first chapters, being blown away by some of the way-easier-than-sockets-in-C examples and so on. I felt like I was getting all this list stuff even though I'm neither a LISP programmer nor really a pure functional programmer. Unfortunately the moment I decided to try puzzling out exactly how some of the early samples worked it turned out I didn't understand as well as I thought. Luckily I think I figured it out, as detailed below.

First step, setting up to compile & run code. I downloaded Erlang R14B (from here), ran it, entered some expressions into the interactive shell, and all seemed well until I put some code into a .erl file in a directory, booted werl.exe (I'm on Windows for this) from that directory, and asked it to compile:

53> c(myTestModule).
./myTestModule.erl:none: no such file or directory
error

Awesome. It turns out that looking in the current directory isn't on by default. A little poking through the part of the book devoted to basic setup revealed that I needed to create a .erlang file in my user home directory that added current directory to the list of places to look. On Win7 this means C:\Users\MyUserName\.erlang with content as follows:

io:format("Running Erlang~n").
code:add_patha(".").

With that set I get a spiffy printout ('Running Erlang') when I boot the shell and now it looks for files in my current directory.

I also found using http://erlide.sourceforge.net/ for syntax highlighting and live reporting of broken code as I typed it was helpful. Unfortunately running and debugging from Eclipse operated without error and without any apparent output so I couldn't actually use Erlide to run programs and view output :(

Anyway, so far so good, next to try a simple program. List comprehensions were something very new given my background but the definition the book gave seemed clear enough:

"The most general form of a list comprehension is an expression of the following form:

[X || Qualifier1, Qualifier2, ...]

X is an arbitrary expression, and each qualifier is either a generator or a filter.

• Generators are written as Pattern <- ListExpr where ListExpr must be an expression that evaluates to a list of terms.

• Filters are either predicates (functions that return true or false) or boolean expressions."

(Programming Erlang, "3.6 List Comprehensions")

I can totally handle that! Not quite sure how to actually use a filter but the generator part seems dead simple. So on to the first little program, a for-each function:

-export([each/1]).
%% the version of each/1 to run for an empty list
each([]) ->
 io:format("each([])~n");
%% the version of each/1 to run for a list made up of 
%% head H (first item in list) and tail T (rest of list). 
%% Print the arguments then run each again on the tail. 
%% If we did something with H it'd be largely the same as
%%    for (Type h : someList { /* do stuff with h here */ }
each([H|T]) ->
 io:format("each(H=~w, T=~w])~n", [H, T]),
 each(T).

In the shell:

54> c(myModule), myModule:each([a, b, c]). 
each(H=a, T=[b,c]])
each(H=b, T=[c]])
each(H=c, T=[]])
each([])
ok

The last value (ok) is the return from the function. This is simply the L-value of the last statement. In this case we're getting ok as the io:format return value.

Our each function works as expected; this is all seeming simple enough! And then we hit the books function to generate all permutations of the items in list. And somehow it didn't just click for me.

-export([perms/1]).
perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

In the shell:

57> c(myModule), myModule:perms([a, b, c]).
[[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]

It works. And I have to admit to almost hoping it didn't! But ... how did it work? It initially looked to me like it was saying take each item from the list (H<-L) and build a list of that plus the permutations of the list with the head taken off (T <- perms(L--[H])). I'm picturing equivalent pseudo-Java'ish code similar to:

for each item in input list
  add to output that item plus the permutations of the list from the next item onwards

This wouldn't work at all! Item b would only pair it with c; we'd never generate combinations like [b, a, c]. Except clearly we do. OK, so what the heck happens when you have multiple generators in a list comprehension? It seems like it must be doing "for each item in each generator run the expression X". Or to put it another way, if we had two generators that each pulled items from a list our expression would run for every possible pair of list items. The second generator seems to be able to use the output of the first so basically we're talking about nested loops.

That seems ... kind of reasonable actually. Perhaps there is a way we could confirm that is what happens? First we'll need a way to print what is happening in the expression part of a list comprehension and still accumulate the result:

%% print B using format A and return C. 
%% This means we can display arbitrary output 
%% and return something in the X part of a list comprehension.
printABReturnC(A, B, C) ->
 io:format(A, B),
 C.

We should be able to use this to simply print each step in running through a list comprehension of a simple list, and luckily it turns out it works as expected:

-module(myModule).
-export([lc2/1]).

lc2([]) ->
 io:format("lc2([])~n");
lc2(L) ->
 [printABReturnC("lc2(L=~w) H=~w~n", [L, H], H) || H <- L].

printABReturnC(A, B, C) ->
 io:format(A, B),
 C.

In the shell:

59> c(myModule), myModule:lc2([a, b, c]).
lc2(L=[a,b,c]) H=a
lc2(L=[a,b,c]) H=b
lc2(L=[a,b,c]) H=c
[a,b,c]

Perfect!

Next we should be able to run a list comprehension that has two generators taking items from the same list. We'd expect that for [a,b,c] we'd get each possible pairing, [[a,a],[a,b],[a,c],[b,a],[b,b],[b,c],[c,a],[c,b],[c,c]].

-module(myModule).
-export([lc3/1]).

lc3([]) ->
 io:format("lc3([])~n");
lc3(L) ->
 [printABReturnC("lc3 H=~w, K=~w~n", [H, K], [H,K]) || H <- L, K <- L].

printABReturnC(A, B, C) ->
 io:format(A, B),
 C.

In the shell:

60> c(myModule), myModule:lc3([a, b, c]).
lc3 H=a, K=a
lc3 H=a, K=b
lc3 H=a, K=c
lc3 H=b, K=a
lc3 H=b, K=b
lc3 H=b, K=c
lc3 H=c, K=a
lc3 H=c, K=b
lc3 H=c, K=c
[[a,a],[a,b],[a,c],[b,a],[b,b],[b,c],[c,a],[c,b],[c,c]]

This is all slowly starting to make sense! So if we wanted to produce all unique pairs from a list we could do something like this:

-module(myModule).

-export([lc4/1]).

lc4([]) ->
 io:format("lc3([])~n");
lc4(L) ->
 [printABReturnC("lc3 H=~w, K=~w~n", [H, K], [H,K]) || H <- L, K <- L--[H]].

printABReturnC(A, B, C) ->
 io:format(A, B),
 C.

In the shell:

61> c(myModule), myModule:lc4([a, b, c]).
lc3 H=a, K=b
lc3 H=a, K=c
lc3 H=b, K=a
lc3 H=b, K=c
lc3 H=c, K=a
lc3 H=c, K=b
[[a,b],[a,c],[b,a],[b,c],[c,a],[c,b]]

Hooray!

If we go back to our original permutations example the ugly bit is perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])]. We can break this down to see we have:

• One generator that simply takes each item from the list: H <- L
• One generator that requests all permutations of the original input list except for the element H: T <- perms(L--[H])
• That is, pair item A with all permutations of [B, C]. Pair item B with all permutations of [A, C].
• Our first generator produces a series of simple values. Our second produces a series of lists. Our expression [H|T] takes each item from each generator and pairs them up as a list. 
• That is, for each item in the input list, make a list where that item is the head and the tail is all permutations of the list without that item

That seems reasonable. We should be able to use our spriffy print function to get output clearly showing it in action though:

-module(myModule).

-export([lc5/0]).
-export([lc5/1]).

lc5() ->
 lc5([]).
lc5([]) ->
 io:format("lc5([])~n"),
 [[]];
lc5(L) ->
 io:format("lc5(~w)~n", [L]),
 [printABReturnC("H=~w, T=~w~n", [H,T], [H|T]) || H <- L, T <- lc5(L--[H])].

printABReturnC(A, B, C) ->
 io:format(A, B),
 C.

And finally we can clearly see in the shell that what we thought was happening is indeed happening:

62> c(myModule), myModule:lc5([a, b, c]).
lc5([a,b,c])
lc5([b,c])
lc5([c])
lc5([])
H=c, T=[]
H=b, T=[c]
lc5([b])
lc5([])
H=b, T=[]
H=c, T=[b]
H=a, T=[b,c]
H=a, T=[c,b]
lc5([a,c])
lc5([c])
lc5([])
H=c, T=[]
H=a, T=[c]
lc5([a])
lc5([])
H=a, T=[]
H=c, T=[a]
H=b, T=[a,c]
H=b, T=[c,a]
lc5([a,b])
lc5([b])
lc5([])
H=b, T=[]
H=a, T=[b]
lc5([a])
lc5([])
H=a, T=[]
H=b, T=[a]
H=c, T=[a,b]
H=c, T=[b,a]
[[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]

In Java it seems that perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])]. would be equivalent to:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Perms {
 public static void main(String[] argv) {
  System.out.println(perms(Arrays.asList("A", "B", "C")));
 }
 
 public static List<List<String>> perms(List<String> input) {
  List<List<String>> output = new ArrayList<List<String>>();
  for (String H : input) {
   //L--[H]
   List<String> LminusH = new ArrayList<String>(input);
   LminusH.remove(H);   
   
   if (LminusH.isEmpty()) {
    //[H|T] when T is empty
    output.add(new ArrayList<String>(Arrays.asList(H)));
   } else {
    for (List<String> T : perms(LminusH)) {    
     //a list made up of [H|T]
     List<String> HT = new ArrayList<String>();
     HT.add(H);
     HT.addAll(T);
     output.add(HT);
    }
   }
  }
  return output;
 }
}

Note that the second generator can reference the output of the first, else the L--[H] wouldn't work, hence the equivalence to nested loops seems correct. Also note this isn't meant to be the best way to accomplish this in Java, rather it is the way most similar to what I think perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])]. does in Erlang.

That was kind of a lot harder that Hello, World was!!

Oh and for the record I'm using the Erlang brush for SyntaxHighlighter from http://stevegilham.blogspot.com/2009/08/improved-syntax-highlight-brush-for.html.