Introduction to Erlang : List & lists Module

This entry is part 12 of 16 in the series Introduction to Erlang

List

List is the the most important data type in Erlang, as in every (?) functional programming language. We have seen and used lists in almost every previous post. In this post, I will briefly present the “theory” of lists and then present the Erlang’s lists module and its most important functions.

Definition

A list can be recursively defined as the construct that

  • either is the empty list (denoted as [] in Erlang),
  • or is a cosntruct that its first element is a term (called head) and what remains if the head is removed is a list (called tail)

In Erlang a list of N elements has the [Element1, Element2, ..., ElementN] format (N is called the length of the list). So, [] is the empty list, [1], [{a}] are 1-element lists, [1, 2], [a, {b, c}] are 2-elements lists, etc. As we will see in a while, the format [Element1, Element2, ..., ElementN] is a shorthand for the [Element1 | [Element2 | ... | [ElementN | []] ... ] representation.

Decomposing & Pattern Matching

An empty list pattern matches with [].

1> Empty = [].
[]
2> Empty == [].
true
3> Empty = []. 
[]
4> NotEmpty = [1].
[1]
5> Empty == NotEmpty.
false
6> Empty = NotEmpty.
** exception error: no match of right hand side value [1]

A non-empty list pattern matches with [Head | Tail].

1> [Head | Tail] = [1, 2, 3, 4]. 
[1,2,3,4]
2> Head. 
1
3> Tail.
[2,3,4]
4> [Head1 | Tail1] = Tail.
[2,3,4]
5> Head1.
2
6> Tail1.
[3,4]
7> [Head2 | Tail2] = [].
** exception error: no match of right hand side value []
Normal Representation

As mentioned before, the format [Element1, Element2, ..., ElementN] is a shorthand for the [Element1 | [Element2 | ... | [ElementN | []] ... ] representation.

For example the list [1, 2, 3] is a shorthand for the [1 | [2 | 3 | []]], that is the normal representation of a list.

What we saw can be used for decomposing

1> [A | [B |[C | D]]] = [1, 2, 3].
[1,2,3]
2> A.
1
3> B. 
2
4> C.
3
5> D.
[]

and composing

1> List = [2,3].
[2,3]
2> List1 = [1 | List]. 
[1,2,3]
3> List2 = [-1 | [0 | List1]]. 
[-1,0,1,2,3]
4> List3 = [[-3, -2] | List2].
[[-3,-2],-1,0,1,2,3] % the head is just 1 element

lists. Of course, since it is more readable and easier to write, the shorthand representation is usually used:

1> [A, B, C] = [1, 2, 3].
[1,2,3]
2> [A, B, C, D] = [1, 2, 3]. % does not match cause
% the left-hand side matches a 4-elements list
** exception error: no match of right hand side value [1,2,3]
3> [A, B, C | D] = [1, 2, 3].
[1,2,3]
4> D.
[]
5> [-3, -2 | [-1, 0 | [1 | [2,3]]]].  
[-3,-2,-1,0,1,2,3]
List Parsing

The pattern matching we saw before can be used in a function in order to parse the list

parse([]) ->
    % parsed the whole list
    parsed.
parse([Head | Tail]) ->
    % do whatever with the current element Head
    parse(Tail).

Concatenation

Two lists can be concatenated using ++

1> L1 = [1, 2], L2 = [3, 4, 5].
[3,4,5]
2> L1 ++ L2.
[1,2,3,4,5]
3> L1 ++ L2 ++ L1.
[1,2,3,4,5,1,2]
4> Mirror = fun(List) -> List ++ lists:reverse(List) end.
#Fun<erl_eval .6.13229925>
5> Mirror([a, b, {c}]).
[a,b,{c},{c},b,a]

Difference

You can take the difference of two lists (the left-hand side one without the element of the right-hand side) using the -- operator

1> [1, 2, 3] -- [1, 2, 3].
[]
2> [1, 2, 3] -- [1, 3].   
[2]
3> [1, 2, 3] -- [1, 3, 3].
[2]
4> [1, 3, 2, 3] -- [1, 3, 3].
[2]
5> [3, 1, 3, 2, 3] -- [1, 3, 3].
[2,3]
6> [1, 2, 3] -- [a, b].         
[1,2,3]
7> Delete = fun(List, Element) -> List -- [Element] end.
#Fun<erl_eval .12.113037538>
8> Delete([1,2,3,4,1], 1).
[2,3,4,1]

Module lists

The lists module defines some commonly used list processing functions. This module is extremely useful, so it is a good idea to “remember” what functions it provides. You can find lists‘s module documentation here.

all/2

Called as all(Pred, List). Returns true if Pred(Element) returns true for all lists’ elements.

1> L = [2, 4, 6, 8],          
1> F = fun(X) -> X rem 2 == 0 end,
1> lists:all(F, L).
true
2> f().                           
ok
3> L = [2, 4, 5, 8],              
3> F = fun(X) -> X rem 2 == 0 end,
3> lists:all(F, L).               
false

any/2

Like all/2 but returns true if any of the elements returns true for the predicate function.

append/1|2

Concatenates the lists to one.

4> lists:append([[1, 2], [3], [4, 5]]).
[1,2,3,4,5]
5> lists:append([1, 2], [3, 4]).       
[1,2,3,4]

Notice that the operator ++ and the function append/2 are the same.

concat/1

Accepts a list of items (atom, integer, float, string) and returns the concatenation of their textual representation as a list.

9> lists:concat(["ab", '.', 1]).     
"ab.1"

delete/2

Deletes an element from the list (first occurrence, if any).

10> lists:delete(a, [d, a, d, a, d]).
[d,d,a,d]

filter/2

Called as filter(Pred, List). Returns a list containing only the elements that return true for the Pred.

11> Gt10 = fun(X) -> X > 10 end, lists:filter(Gt10, [1, 2, 22, 3, 44, 5, 66]).
[22,44,66]
12> L = [1, a, b, 2, c, 3.0, d, {4}]. 
[1,a,b,2,c,3.0,d,{4}]
13> lists:filter(fun(X) -> is_number(X) end, L).
[1,2,3.0]

flatten/1

Returns a flattened (no element is a list) version of the input list.

12> lists:flatten([1, [2], [3, 4, [5, [6, 7]]], [[[[8]]]]]).
[1,2,3,4,5,6,7,8]

key*** functions

There are several functions which their name starts with the word key. They are all used to process lists of tuples.

15> Kl = [{a, k1, a}, {b, k2, b}, {c, k3, c}, {e, k5, e}].
[{a,k1,a},{b,k2,b},{c,k3,c},{e,k5,e}]
16> lists:keydelete(k3, 2, Kl).                           
[{a,k1,a},{b,k2,b},{e,k5,e}]
17> lists:keysearch(k3, 2, Kl).
{value,{c,k3,c}}
18> lists:keysearch(k4, 2, Kl). 
false
19> lists:keyreplace(k3, 2, Kl, {new, tuple}).
[{a,k1,a},{b,k2,b},{new,tuple},{e,k5,e}]

last/1

Returns the last element of the list.

20> lists:last([1, 2, 3]).
3

map/2

Called as map(Fun, List). Applies function Fun to every item of the list and returns the resulting list.

21> lists:map(fun(I) -> 2 * I end, [1, 2, 3]).
[2,4,6]

max/1, min/1

Returns the maximum / minimum of the list.

member/2

Return true if the given element exists in the list else returns false.

22> lists:member(4, [1, 2, 3, 4, 5]).
true
23> lists:member(14, [1, 2, 3, 4, 5]).
false

nth/2

Called as nth(N, List). Return the Nth element of the List. The head of the list is element 1.

24> lists:nth(3, [{1}, {2}, {three}, {}, {s, i, x}]).
{three}

partition/2

Partitions a list to two according to if the elements satisfy or not a given predicate.

3> L = [1, a, b, 2, c, 3.0, d, {4}].              
[1,a,b,2,c,3.0,d,{4}]
4> {Satisfy, Not} = lists:partition(fun(X) -> is_number(X) end, L).   
{[1,2,3.0],[a,b,c,d,{4}]}
5> Satisfy.
[1,2,3.0]

prefix/2

Returns true if the first list is a prefix of the second, else false.

7> lists:prefix([a, b, c], [a, b, c, d, e]).
true
8> lists:prefix([a, b, c], [a, b, cc, d, e]).
false

reverse/1|2

Returns the reverse of a list.

9> lists:reverse([a, b, c, d]).
[d,c,b,a]
% reverse / append
10> lists:reverse([a, b, c, d], [1, 2, 3]).
[d,c,b,a,1,2,3]

seq/2|3

Called as seq(From, To [, Increment]). Returns the sequence of integers starting from From and containing the integers From + 1, From + 2, ... up to To or the integers From + 1*Increment, From + 2*Increment, ... up to To if it is called as seq/3.

16> lists:seq(1, 7).   
[1,2,3,4,5,6,7]
17> lists:seq(1, 8, 3).
[1,4,7]

sort/1|2

Sorts a list to increasing order or according to a given function.

24> L = [3, 1, 2, 5, 4].        
[3,1,2,5,4]
25> lists:sort(L).              
[1,2,3,4,5]
26> Gt = fun(I, J) -> I > J end.
#Fun<erl_eval .12.113037538>
27> lists:sort(Gt, L).          
[5,4,3,2,1]
</erl_eval>

split/2

Called as split(N, List1). Splits the list into two; the first having the N first elements and the second the remaining ones.

1> lists:split(3, [1, 2, 3, a, b]).
{[1,2,3],[a,b]}

sublist/2|3

Returns a sublist of a list.

2> L = [1, 2, 3, 4, 5, 6].
[1,2,3,4,5,6]
3> lists:sublist(L, 3).
[1,2,3]
4> lists:sublist(L, 2, 4).
[2,3,4,5]
5> lists:sublist(L, 11).  
[1,2,3,4,5,6]

subtract/2

Returns the first list without the elements contained in the second list. Equivalent to the operator --.

8> lists:subtract("vasilis", "ai").
"vslis"
9> "vasilis" -- "ai".              
"vslis"

suffix/2

Returns true if the first is a suffix of the second, else returns false.

10> lists:suffix([3, 4], [a, b, 1, 2, 3, 4]).
true
11> lists:suffix([3, 4], [a, b, 1, 2, 33, 4]).
false

sum/1

Returns the sum of the elements of a list containing numbers.

12> lists:sum([1, 2.2, 3]).
6.2

u*** functions

There are several function which their name starts with u and the results they return contain no duplicates.

14> lists:usort([5, 3, 2, 3, 2, 1, 4, 5]).
[1,2,3,4,5]

Next

Next post will be about list comprehension.

Series NavigationIntroduction to Erlang : BIFs & Predefined ModulesIntroduction to Erlang : List Comprehension

Leave a Reply

*

Posts’ Calendar
April 2011
M T W T F S S
« Mar   May »
 123
45678910
11121314151617
18192021222324
252627282930