Erlang Linked List Exercise

Yesterday, my copy of Programming Erlang arrived in the mail1. w00t! Iâ€™m already part way through chapter three. I donâ€™t know what it is about this language â€“ maybe itâ€™s all hype and a passing fad â€“ but I havenâ€™t been this interested in learning a new language since I started with Python over two and half years ago.

The day before yesterday, I took a shot at implementing a linked list in Erlang. I had one basic rule, which was that I wasnâ€™t allowed to use the built in list type. Getting started was fairly difficult, but once I started to â€œget itâ€ (e.g., pattern matching, recursion), the task got much easier.

Previously, I had only played around in the shell, so this is the first Erlang module Iâ€™ve written. Erlang modules are similar to Python modules, though to make functions available outside an Erlang module, they must be explicitly exported. I havenâ€™t yet come across whether Erlang modules can be organized into packages, although I imagine there must be some kind of higher level system for organizing Erlang programs.

Recently, I did a similar exercise with Python as way to experiment with Behavior Driven Development. That version uses the familiar â€œdestructive assignmentâ€ operation throughout. Erlang allows single assignment only, so I had to think about the problem in a different way. For example, an item canâ€™t be appended to a list by manipulating a couple of object references as in Pythonâ€”instead I used recursion to build up a new list.

After I get further into the book, it will be fun to come back to this implementation and see how it can be improved given a better understanding of the language. Iâ€™m also looking forward to exploring Concurrency Oriented Programming in depth. With Python, I tend to not think in terms of concurrency, though Iâ€™m sure Iâ€™ve got code that could be improved by using it.

Finally, hereâ€™s the code. It was written in Emacs, which has a nice Erlang mode. There are two other IDEs available, one based on Eclipse and the other on NetBeans.


-record(list, {head, length=0}).
-record(item, {data, next}).

new() ->

new_item(Data) ->

head(List) ->


tail(List) when List == #list{} ->
tail(List) ->
    Length = linkedlist:length(List) - 1,
    #list{head=next(head(List)), length=Length}.

append(Data, List) when List == #list{} ->
    List#list{head=new_item(Data), length=1};
append(Data, List) ->
    Item = append_item(Data, head(List)),
    NewLength = linkedlist:length(List) + 1,
    List#list{head=Item, length=NewLength}.

append_item(Data, Item) when == undefined ->
append_item(Data, Item) ->

    Item#item{next=f(Data, next(Item))}.

next(Item) ->

% Get the Nth item from List
% N: Index of item to get
% List: List to get from
nth(N, List) when N < 1 ->
nth(N, List) ->
    nth(N, 1, head(List)).

% N: Index of item to get
% I: Current index
% Item: #item in List corresponding to index I
nth(N, I, Item) when I == N ->
nth(N, I, Item) ->

    nth(N, I + 1, next(Item)).

last(List) ->
    nth(linkedlist:length(List), List).

length(List) ->

is_empty(List) ->
    List == new().

p() ->
p(Object) ->

main() ->

    L = new(),
    test_list(L, "New list"),
    L1 = append(data1, L),
    test_list(L1, "List with one item"),
    L2 = append(data2, L1),
    test_list(L2, "List with two items"),
    L3 = append(data3, L2),
    test_list(L3, "List with three items"),

test_list(List, Description) ->
    io:format("~s~n", [Description]),
    Length = linkedlist:length(List),
    p({'list', List}),
    p({'head', head(List)}),
    p({'tail', tail(List)}),
    p({'first', nth(1, List)}),
    p({'nth', nth(Length, List)}),
    p({'last', last(List)}),
    p({'length', Length}),
    p({'is_empty', is_empty(List)}),

1 A new blade and O-ring for my old-fashioned Oster blender came also. Double w00t!

2 thoughts on “Erlang Linked List Exercise

  1. What does the f() call do? I know what it does within the interpreter (makes it forget all bindings), but Iâ€™m going through the book, and I havenâ€™t seen it used in a module.

Comments are closed.