Distributed Life

List Comprehension

Do you remember the lists:map/2 and lists:filter/2 functions from the previous post? If not, consult the Lists & lists Module post. lists:map(Function, List) returns a new list that results from List after applying the Function to each element. lists:filter(Predicate, List) returns a list that contains only the elements of List for which the call to Predicate returns true.

Both the aforementioned operations are commonly used, as well as their combination; map & filter (does it remind you map & reduce?). Erlang provides this combined functionality using the list comprehension construct.

Format

A list comprehension look like the following:

[Expression || Generators1, Guards1, Generators2, ...]

Generators

As their name suggests, generators create the data used in the filter-map operations. A generator has the Pattern <- Data format, where Data is a list or an expression that results to a list and Pattern is a pattern used to match with the elements of the list. This pattern can be used to disassembly elements. For example, two valid generators are I <- lists:seq(1, 10) and {X, Y} <- [{'A', 'Excellent'}, {'B', 'Good'}, {'C', 'Fair'}].

Expression

The expression specifies the elements of the result. For example, [I || I <- [1, 2, 3]] returns the input list element as is.

Guards

Guards are expressions that return either true or false, the same as the guards we have seen in the previous posts. They apply to the variables that are on the left of the guard and the ones that are accessible due to the scope where the comprehension runs. For example, I <- [1, 2, 3, 4], I rem 2 == 0 is a valid generator - guard combination (the result should be obvious; only the even numbers "pass" the guard's test).

Lists Examples

Following the same template with the previous posts, I will first show some examples that implement some list functions. Most of them already exist in the lists module. As I did in the past, I will add these functions to the module called mlists.

map/2

Called as map(Function, List). The resulting list contains the elements of the input list after applied to the input function.

% Generator : the items of the list provided
% Guard : no guard expression, all items are kept
% Expression : the item from the generator after applied
%              to the Function
map(Function, List) ->
    [Function(I) || I <- List].
 
% example
2> mlists:map(fun(I) -> 2 * I end, [1, 2, 3, 4]).
[2,4,6,8]

filter/2

Called as filter(Predicate, List). Keeps the elements for which the call to Predicate returns true.

% Generator : the items of the list provided
% Guard : the item should return true when applied to the Pred
% Expression: keep the elements of the list that "pass" the
%             guard test, as they are
filter(Pred, List) ->
    [I || I <- List, Pred(I)].
 
% example
6> mlists:filter(fun(I) -> is_atom(I) end, [1, a, 2, b, 3.0, "d"]).
[a,b]

deleteall/2

Deletes all occurrences of an Element from the list.

% Generator : the items of the list provided
% Guard : the item should not be equal (both value and type)
%         with the Elem
% Expression: keep the elements of the list that "pass" the
%             guard test, as they are
deleteall(Elem, List) ->
    [I || I <- List, I =/= Elem].
 
% example
2> mlists:deleteall(3, [1, 2, 3, 4, 3, 2, 1]).
[1,2,4,2,1]

partition/2

Partition a list into two, according to if the elements satisfy or not a given predicate.

partition(Pred, List) ->
    {[I || I <- List, Pred(I)],
     [I || I <- List, not(Pred(I))]}.
 
% an alternative implementation
partition2(Pred, List) ->
    Sat = filter(Pred, List),
    {Sat, List -- Sat}.
 
% example
10> mlists:partition(fun(I) -> is_atom(I) end, [1, a, 2, b, 3.0]).
{[a,b],[1,2,3.0]}

replicated/2

Called as replicated(Item, Times). Creates a list of Items of length Times.

% Generator : only used for fixing the length
% Expression : a fixed item
replicated(Item, Times) ->
    [Item || _ <- lists:seq(1, Times)].
 
% example
14> mlists:replicated(':-)', 10).
[':-)',':-)',':-)',':-)',':-)',':-)',':-)',':-)',':-)',
 ':-)']

replicate_items/2

Called as replicate_items(Times, List). Replicates each elements of the list Times times.

replicate_items(Times, List) ->
    mlists:flatten([[Item || _ <- lists:seq(1, Times)] || Item <- List]).
 
% same as
% replicate_items(Times, List) ->
%    mlists:flatten([replicated(Item, Times) || Item <- List]).
 
% example
5> mlists:replicate_items(3, [a, b, c]). 
[a,a,a,b,b,b,c,c,c]

member/2

Returns true if an element is a member of the list, else returns false.

member(Elem, List) ->
    [] /= [ok || I <- List, I == Elem].
 
% example
1> mlists:member(a, [3, 2, 1, a, x, z]).
true
2> mlists:member(a, [3, 2, 1, aa, x, z]).
false

member_times/2

Returns the number of occurences of an element in a list.

member_times(Elem, List) ->
    length([ok || I <- List, I == Elem]).
 
% example
5> mlists:member_times(a, [1, a, 2, 3, b, a, c]).
2
6> mlists:member_times(a, [1, a, 2, 3, b, c]).   
1
7> mlists:member_times(a, [1, 2, 3, b, c]).   
0

intersection/2

Called as intersection(List1, List2). Returns the List1 without the elements that are exist in List2.

intersection(List1, List2) ->
    [I || I <- List1, not(mlists:member(List2))].
 
% example
9> mlists:intersection([1, 2, 3, 4, 3, 2, 1], [2, 4]).
[1,3,3,1]

quicksort/1

This is the famous Quicksort implementation that is often used to show the power and compactness of Erlang.

qsort([]) ->
    [];
qsort([Pivot | List]) ->
    qsort([I || I <- List, I < Pivot]) 
    ++ 
    [Pivot | qsort([I || I <- List, I >= Pivot])].
 
% example
2> mlists:qsort([7, 1, 3, 9, 1, 2, 0, 4, 6, 5]).
[0,1,1,2,3,4,5,6,7,9]

Other Examples

Eratosthenes' Sieve

Sieve of Eratosthenes is an algorithm for calculating the primes up to a given integer. In a nutshell, given an integer N the algorithm works as following:

1. Generate the list that contains the integers 2, 3, 4 ... N.
2. Remove the first element E and add it to the list with the found primes.
3. Remove all the multiplies of E from the remaining list since they cannot be a prime.
4. If the resulting list is empty, the algorithm finished, else, go to step two with the resulting list as input.

For more details on the algorithm go to Wikipedia.

sieve(N) when is_integer(N) ->
    calc(lists:seq(2, N)).
 
calc([]) ->
    [];
calc([Prime | Rest]) ->
    [Prime | calc([N || N <- Rest, N rem Prime /= 0])].
 
% example
4> erat:sieve(120).
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
 79,83,89,97,101,103,107,109|...]

As you can see, the definition of the algorithm in Erlang is shorter and more clear than the textual one :-). Just to note that the algorithm that I described is actually the Euler's sieve and not the Eratosthenes one. Euler's sieve is an "optimized" version of the Eratosthenes' algorithm.

Multiple Generators

Now I will present some examples with multiple generators.

% think of this example as a for loop with an inner for loop
% the J <- [...] would be the inner for loop
1> [{I, J} || I <- [1, 2, 3], J <- [a, b, c]].
[{1,a},{1,b},{1,c},{2,a},{2,b},{2,c},{3,a},{3,b},{3,c}]
 
% duplicate list
2> [I || _ <- [a, a], I <- [1, 2, 3]].
[1,2,3,1,2,3]
 
% duplicate elements 
3> [I || I <- [1, 2, 3], J <- [a, a]].
[1,1,2,2,3,3]
 
% discard elements and duplicate the others
4> Discard = [2, 4].                                                                         
[2,4]
5> [I || I <- [1, 2, 3, 4, 5, 6], not(lists:member(I, Discard)), _ <- [a, a]].            
[1,1,3,3,5,5,6,6]
 
% subsequences
8> [[I || I <- lists:seq(1, J)] || J <- lists:seq(1, 10)].
[[1],
 [1,2],
 [1,2,3],
 [1,2,3,4],
 [1,2,3,4,5],
 [1,2,3,4,5,6],
 [1,2,3,4,5,6,7],
 [1,2,3,4,5,6,7,8],
 [1,2,3,4,5,6,7,8,9],
 [1,2,3,4,5,6,7,8,9,10]]

Next

Next post will be about creating processes in Erlang.