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.
-module(linkedlist).
-export([new/0,
head/1,
tail/1,
append/2,
nth/2,
last/1,
length/1,
is_empty/1,
main/0
]).
-record(list, {head, length=0}).
-record(item, {data, next}).
new() ->
#list{}.
new_item(Data) ->
#item{data=Data}.
head(List) ->
List#list.head.
tail(List) when List == #list{} ->
undefined;
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 Item#item.next == undefined ->
Item#item{next=new_item(Data)};
append_item(Data, Item) ->
Item#item{next=f(Data, next(Item))}.
next(Item) ->
Item#item.next.
% Get the Nth item from List
% N: Index of item to get
% List: List to get from
nth(N, List) when N < 1 ->
undefined;
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 ->
Item;
nth(N, I, Item) ->
nth(N, I + 1, next(Item)).
last(List) ->
nth(linkedlist:length(List), List).
length(List) ->
List#list.length.
is_empty(List) ->
List == new().
p() ->
io:format("\n").
p(Object) ->
erlang:display(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"),
ok.
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)}),
p(),
ok.
1 A new blade and O-ring for my old-fashioned Oster blender came also. Double w00t!
