Erlang: tuples and lists

You can't seriously program in a language just with scalar types like numbers, strings and atoms. For this reason, now that we have a basic knowledge of Erlang's syntax and variables, we have to delve into two basic vector types: tuples and lists.

Both tuples and lists represent a collection of values; however, some rules of thumb (imho) to choosing between them are:

• tuples deal with heterogeneous values, while lists are homegeneous. A tuple is then usually built as a sequence of values of different types, while all of the values of a list are of the same type. This struct versus array differentiation is true also in Python.
• Tuples and lists are pattern-matched differently (we'll see more of this when writing pattern matching code, of course).
• Tuples have O(1) random access, while lists have O(N) random access, being built of cons cells.
• In general, fixed-size structures are modelled as tuples while sequences of N values (where N varies at runtime) are modelled as lists.

Tuples

Erlang tuples are similar in syntax to Python's ones:

1> MyTuple = {number, 42}.
{number,42}
2> tuple_size(MyTuple).
2
3> element(1, MyTuple).
number
4> element(2, MyTuple).
42

And of course they are immutable, like every other value:

5> setelement(2, MyTuple, 43).
{number,43}
6> MyTuple.
{number,42}

They can have any number of values:

7> {true, 23, "Hello"}.
{true,23,"Hello"}

And the empty tuple is:

8> {}.                 
{} 

Lists

Lists are built as a sequence of cons cells (one of LISP's basic data structures; cons means construct*). Each cons cell is composed by a value and a pointer to another cons cell, which may be empty.

Thus the list [1, 2, 3] is composed of three cons cells:

p1: [1, p2]
p2: [2, p3]
p3: [3, p_to_empty_list]

Lists can be either built as sequences or even by specifying the cons cells directly. In the first case, values are separated by `,`, while in the second they are separated by `|`:

1> []
1> .
[]
2> [1].
[1]
3> [1, 2].
[1,2]
4> [1 | [2]].
[1,2]
5> [1, 2, 3].
[1,2,3]
6> [1 | [2 | [3]]].
[1,2,3]

Every function operating on lists is defined in terms of two primitives, head and tail, which return respectively the first element of the list and the rest of the list with that element removed.

While in other languages these functions are provided as head/1 and tail/1 (car and cdr for friends), in Erlang they are implemented via pattern matching; this means they are built into the language syntax. Our little exercise for today is to write these constructs as ordinary functions, to introduce how pattern matching works on lists.

head/1

Let's start with a simple case: an empty list. If you ask for the first element of such a list, our implementation should raise an error as there is no such element.

#!/usr/bin/escript
head([]) -> throw(error).

main(_) -> head([]).

This indeed shows:

escript: exception throw: error
  in function  erl_eval:local_func/5
  in call from escript:interpret/4
  in call from escript:start/1
  in call from init:start_it/1
  in call from init:start_em/1

when executed.

What has happened? We can put literal values in the formal arguments of a function, and the body of the function will only be executed if the values match these literals. Of course this also means that when we execute:

main(_) -> head([1]).

we get:

escript: exception error: {function_clause,[{local,head,[[1]]}]}

since the function is only defined for [] as an argument.

Let's add another clause to make it work also for 1-element lists:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element]) -> Element.

main(_) -> E = head([1]),
           io:format("Head: ~p~n", [E]).

Note that cases are separated by ; instead of `.` and are evaluated in sequence, so you should put the corner cases (or the base case of recursion) first.

Here we didn't use a literal pattern, since we don't know what is in the list in general. We used a variable name, so that Element is filled with the value of the only element of the list.

Now we can extend the code further, so that it deals with multiple-value lists:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element]) -> Element;
head([Element | _Tail]) -> Element.

main(_) -> io:format("Head of [1]: ~p~n", [head([1])]),
           io:format("Head of [1, 2]: ~p~n", [head([1, 2])]).

We use _Tail instead of Tail to tell Erlang that we don't need the value of this argument, but that it must exist.

Actually, we know that [1] is actually [1 | []], so we can simplify this code a bit as the third clause would match the single-element list case:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element | _Tail]) -> Element.

main(_) -> io:format("Head of [1]: ~p~n", [head([1])]),
           io:format("Head of [1, 2]: ~p~n", [head([1, 2])]).

You're not limited to pattern matching to act on lists: explore the lists* module to see how member(), nth() or length() can be use to test an element's presence, read a single value or calculate the length of the list.

I'm out of space for today, so I leave the similar tail/1 implementation as an exercise for the reader.

Conclusions

Tuples and lists are base Erlang data structures. Exercise with them and with pattern matching in the shell to make sure that you know how to manipulate variables before we move from defining functions to make them collaborate.