Erlang: list comprehensions

 List comprehensions are one of Erlang's most powerful tools: learn how you can write quicksort in two lines in a famous example, and more on how to read and write list comprehensions in Erlang's syntax.

Higher-order functions

This kind of functions, which work over lists, can be easily reimplemented with list comprehensions, and can serve as an example here.

As you may remember, map/2 takes a list and a function, and applies the function to all the elements of the list. You can implement map like this:

map_test() ->
  ?assertEqual([1, 4, 9], [X*X || X <- [1, 2, 3]]).

The syntax literally means X*X (the square/1 function) for all the X taken from the list [1, 2, 3].

In the same way, it's possible to reimplement filter/2, by adding a condition at the end of the expression:

filter_test() ->
  ?assertEqual([42, 5], [X || X <- [-1, 42, -2, 5], X > 0]).

Of course you can put the concepts together and map to square/1 the result of a filter:

filter_map_test() ->
  ?assertEqual([1, 4], [X*X || X <- [-1, 42, -2, 5], X < 0]).

So Erlang has a language syntax for list-related functions, after providing them as library functions.

You have the choice to combinate these operations in a single expression, or to apply them in a series of calls. The first solution has concision on its side; the second has flexibility as you have visibility on the intermediate results and can apply the functions one at a time.

Raising the difficulty

Erlang's assignment sugar is usually available also inside list comprehensions.  Thus pattern matching is something you can do in the generator of such an expression:

pattern_matching_test() ->
  % This represents a^2, b^3, c^5
  Monomia = [{a, 2}, {b, 3}, {a, 5}],
  ?assertEqual([2, 5], [Exponent || {Letter, Exponent} <- Monomia, Letter == a]).

You can even write more than one generator, so that they will be applied in sequence, in a cartesian product:

two_nested_generators_test() ->
  Letters = [a, b],
  Numbers = [1, 2],
  Expected = [{a, 1}, {a, 2}, {b, 1}, {b, 2}],
  ?assertEqual(Expected, [{Letter, Exponent} || Letter <- Letters, Exponent <- Numbers]).

Every time a Letter is extracted from the list, the Exponent generator is run so that each Exponent is assigned to each of the Letter instances.

With this in mind, we can look at the next, example, the unroll/1 function, which takes a the elements of nested lists and put them all together in a single, unidimensional list:

unroll_test() ->
  ListOfLists = [[1, 2], [3, 4, 5]],
  ?assertEqual([1, 2, 3, 4, 5], [X || SingleList <- ListOfLists, X <- SingleList]).

The key feature is that we can use the output of previous generators inside the next ones. So, for every SingleList we run a generator that extracts each element of the nested list.

Quicksort

Erlang's list comprehensions can be a mild form of metaprogramming: they compress logic in new constructs. The logic of what you would write as for() cycles in an imperative language is exposed here in a generator, so that you can write the interesting part (what to extract) in the shortest possible form, associating a list to a variable representing its element.

quicksort/1 is a very famous example of the power of list comprehensions: the quicksort algorithm implemented in two lines of Erlang code.

Here is a test for quicksort/1, which orders the elements of a list:

quicksort_test() ->
  Unsorted = [3, 1, 2, 5, 4],
  ?assertEqual([1, 2, 3, 4, 5], qsort(Unsorted)).

The first line is the base case of recursion:

qsort([]) -> [];

The second line is a bit longer, but you should be able to read it by now:

qsort([X|Xs]) ->
  qsort([Y || Y <- Xs, Y =< X]) ++ [X] ++ qsort([Y || Y <- Xs, Y > X]).

In English, this would be read as take a list and break it into an head X and tail Xs. Return a list composed of three sublists:

1. the list of all Y from the tail Xs such that Y is less than or equal to X, ordered by qsort/1.
2. the list containing just X.
3. the list of all Y from the tail Xs such that Y is greater than X, ordere dby qsort/1.

X is what is called the pivot in this implementation: the element that we keep fixed while moving the other elements of the list before or after it.

Note that quicksort/1 can be implemented so easily because it is a recursive algorithm, and as such it plays very well with Erlang. Probably mergesort/1 would be more difficult and take longer to write, but list comprehensions can be helpful in that case too.