While reading Learn You Some Erlang For Great Good I stumbled upon a list growing problem. Little did I know that my lack of understanding was about to dispatch me on a 1-hour journey that would help me better understand and appreciate the pros of conses (I’ll explain what conses are in a sec).
What Are Lists?
An Erlang list is a finite collections of items (elements could be of different
types) and is notated as
[...|...] notation is referred
to as a cons (it’s a list constructor) in Erlang patois and requires a left-hand
operand commonly referred to as the head and a right-hand operand, the tail.
So let’s look at a few snippets that demonstrate lists.
. % nil or an empty list [monkey,mole]. % monkey and mole in a list [monkey|[mole]]. % monkey and mole in s list [monkey|[mole|]]. % monkey and mole in a list [mokey|mole]. % improper list, steer clear of these
The book does a great job in explaining lists too by the way and if you want to get a deeper understanding I have attached a fragment of the Erlang Specification Draft 0.7 below, otherwise just skip the PDF.
It always helps to truly understand how things work… Variables in Erlang aren’t really variable as everything is immutable. This means that we can’t reassign values or modify properties.
My lack of understanding the implications of immutability required me to do 1 hour worth of reading and thinking, after having proposed inefficient code, before finally appreciating the design.
Basically, we should keep in mind that we need to construct new data if we need anything changed… every single time which means that we have to play ball in an entirely different manner when dealing with those immutable creatures.
Let’s cut to the chase…
NoFlyList represents a list of creatures we don’t want on our flight
because of bad behavior. Maybe the monkey pooped:poop: in his seat and the mole
burrowed his way into a fluffy cushion:seat:… really, that isn’t the point; of
importance is realizing that Erlang
Lists are singly linked-lists meaning
that list items only know who their successors are.
In the case of the
NoFlyList the monkey only sees the mole and the mole
doesn’t see jack–it’s practically blind anyways :eyes:.
Now the most interesting bit, which should help us understand the merit of conses, is that we could extend our list of creatures unwelcome on our flights:airplane: by prepending or appending items to the list.
++ list operator is officially called the list addition operator, so
yeah… it will allow us to add something to a list. In our example we want
to add a list containing just a ghost to our already existing list of
creatures we’d rather not board on our planes.
NoobNoFlyList = NoFlyList++[ghost].
Experienced Erlang coders, a title and burden I aspire to carry in the future, will probably chuckle when they see that snippet because they can only imagine the author’s recklessness in daring to specify this inefficient code. Until a few hours ago I wasn’t aware of this fuckup either, which explains why I’m far from bearing that title :trophy:.
Erlang looks at the
++ operator, takes whatever it finds on the
right-hand side (the tail) as the item it wants to connect something to, where
the operand on the left-hand (the head) side represents the item we’re going to
connect to the tail.
We have a immutable list containing a ghost and need to extend the no-fly list to contain all items in the list that currently contains just our ghost. This basically means that we want the mole, the last one in our no-fly list, to look at the first item in our tail, which is the ghost. It’s Erlang, however; so the mole is immutable therefore we’ll have to create a copy of the mole that looks at the ghost in order to realize that list extension.
The new mole has nothing looking at it and we need the monkey to do that, yet again we stumble into the problem of the monkey being cast in stone, so we’ll have to create a new monkey to look at the newly created mole. Now we’ll have a list in which the monkey looks at the mole which looks at the ghost, but as you noticed we had to recreate the entire list on the left-hand side. Bummer!
Section 6.13.1 in the Erlang Specification Draft contains a formal definition
++ operator which I attached below for your convenience :wink:.
In order to use the
++ list operator without having to step through an
entire list which could very well be comprised of a million misbehaving
critters it would be more sensible to have the list on the right-hand side of
OkayNoFlyList = [ghost]++NoFlyList.
Note that the left-hand operand represent a list of a single item – our ghost.
The list happens to be immutable so Erlang cannot in good conscience modify
it or any of its contents, therefore being forced to make a copy.
This time the
ghost needs to look at the first screw-up in the no-fly list,
therefore being the only item that needs to be copied. In the meantime the
monkey still looks at the mole which is still blind as a bat.
Just sidetracking here
- the left-hand operand of the
++operation is always a list. Erlang throws up if it isn’t.
- the left-hand operand of the
++operation will be traversed in its entirety, leading to a time complexity of $O(n)$ where $n$ represents the number of items in the left-hand operand
- the last item in the head (the left-hand operand) (which is a list) will need to point to the first item in the tail (the right-hand operand). Being pointed to doesn’t require anything at all, so the passive tail will survive unscathed, however; the active head, having to do the pointing, will have to be reconstructed.
[mole]++bat==[mole|bat]. % improper list [mole]++[bat]==[mole,bat]. % proper list [mole]++[bat]==[mole|[bat]]. % same thing [mole]++[bat]==[mole|[bat|]]. % we covered this before
Using list cons, one could perform the previous feat more effectively.
EliteNoFlyList = [ghost|NoFlyList].
As suggested in the Efficiency Guide
the constructor does not have to copy the ghost as it directly creates the
ghost looking at something, that very something we call the tail :wink:. Which directly gives us a ghost looking at a
monkey, which is looking at a blind mole. In the
we create the ghost, and subsequently have to recreate a copy of it to look at
whatever the hell is first up in the
Always remember that using a non-list tail will result to a improper list, with which you will most likely have a bad time
[monkey|mole] != [monkey,mole]. % avoid [monkey|[mole]] == [monkey,mole]. % do this :)