Erlang Programming/List Comprehensions

List Comprehensions

Intro to Comprehensions

A list comprehension is a mathematical way to construct a list. To do list comprehension we have to use a new operator "<-", "taken from".

L = [ X*X || X <- [1,2,3,4] ].

English translation is: build a list L, with elements that have the value X*X, such that X is taken from the list [1,2,3,4]. It gives the output:

[1,4,9,16]

Notice that this is similar to

lists:map(fun(X) -> X*X end, [1,2,3,4])

In fact, list comprehension provides a shorthand notation for most of the functions in the lists module.

Simple Comprehensions

You can use them to solve equations.

 L = [ {X,Y} || X <- [1,2,3,4], Y <- [1,2,3,4], X*X == Y].

output:

[ {1,1}, {2,4} ]

Lists version

Can you figure out the lists functions used in the above comprehension ?

How about

 F = fun(X, Y) ->
  lists:filter(fun({X0, Y0}) -> X0 * X0 == Y0 end,
     lists:reverse(
        lists:foldl(fun(E, Acc) -> 
             lists:zip(lists:duplicate(length(Y), E), Y) ++ Acc
           end, [], X))) end.
 F([1,2,3,4], [1,2,3,4]).

That is 5 functions in one succinct line. For the remainder of the examples take some time and find the corresponding lists functions that do the same thing.

Permutations

Here we flip two coins:

[ [X]++[Y] || X<-"HT", Y<-"HT"].

Note: strings are lists in erlang. all combinations are: output:

["HH","HT","TH","TT"]

Intermediate list comprehensions

An important use of List Comprehensions is to help translate Prolog-like statements into Erlang. [Why is this "important"?]

1- Erlang is a functional language designed for message passing (MIMD) parallel processing. Prolog is designed for logic programming. Sometimes a problem is most easily defined as a logical set of constraints on some set of data. If one thinks logically or thinks in constraints, or thinks in prolog, this style of list comprehensions can be a helpful way to do your tasks in erlang. There exist many useful solutions in prolog that can be moved to erlang via list comprehensions.

2- Constraint programming and logic programming are considered a higher level way to program than functions, and hence, are a good way to save you time and increase terseness.

Warning: constraint and logic based programs can be harder to debug because strict step by step actions are hidden and delegated to the list comprehension engine. Order of constraints in erlang list comprehensions can affect the output. Order dependence of constraints can be a non-intuitive distraction.

Note: in general, using huge numbers of atoms is not a good idea as they are never garbage collected.

-module(think).              %
-compile(export_all).        %
                             %
male(adam) -> true;          %
male(seth) -> true;
male(cain) -> true;
male(abel) -> true;
male(noah) -> true;
male(_X) -> false.
                             %
female(eve) -> true;
female(_X) -> false.
                             %
parent(adam,cain) -> true;
parent(adam,abel) -> true;
parent(eve,cain) -> true;
parent(eve,abel) -> true;
parent(noah,shem) -> true;
parent(_X,_Y) -> false.
                                                %
people() ->
       [ adam, shem, cain, abel, eve, noah ].
                                                %
father_of() ->
       [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), male(X) ].
mother_of() ->
       [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), female(X) ].

compile with c(think). and generate output with:

17> think:father_of() ++ think:mother_of().
[{adam,cain},{adam,abel},{noah,shem},{eve,cain},{eve,abel}]

Advanced List Comprehensions

Example with quicksort in 7 lines.

-module(sort).
-compile(export_all).
                                % classic way to show off erlang terseness.
qsort([]) ->
   [];
qsort([H | T]) -> 
   qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).

% sample output:
%
% sort:qsort([1,5,3,7,6,8,9,4]).
%   [1,3,4,5,6,7,8,9]

(Btw: This isn't actually "quicksort," as you'd want to use it, because it uses more memory than necessary, and doesn't get the VM page/cache benefits of an in-place quicksort. But it's neat nevertheless!)

Exercises

1) Write a program using list comprehension that finds the integer solutions {X,Y} for a circle of radius 5.

Solutions

1)

-module( solve_circle).
-export( [start/0] ).
                                                  %
numbers() -> lists:seq(-5,5).
                                                  %
start() -> [ {X,Y} ||
                   X <- numbers(),
                   Y <- numbers(),
                   X*X + Y*Y == 25 ].
                                                   %
% ================================================ %
% sample output
% 11> solve_circle:start().
% [{-5,0}, {-4,-3}, {-4,3}, {-3,-4}, 
%  {-3,4}, {0,-5}, {0,5}, {3,-4},
%  {3,4}, {4,-3}, {4,3}, {5,0}]