Elixir immutability and data structure

TL;DR

It's impossible to create circular structures with elixir due the immutability, however there are some workaround to build them.

Immutability is a two edged sword, while it is thread safe, more error proof and have others benefits that help builds the foundation of beam. This come with a cost, like everything.

Circular list, graphs, trees with parent and a others data structures can not be build in elixir as in others programming languages.

Per example, imagine a list which: A -> B -> A

Since A links to B, then B needs to exist in advanced, however as B links to A, then B needs to exist in advanced.

Photo by Melani Sosa on Unsplash

It’s a chicken-egg problem. So far, beam does not support quantum superposition, making impossible to reference nonexistent objects. Go ahead and try.

However there are a few workarounds to implement it, one of them is using auxiliary map with id’s to represent link between nodes. Thus every node needs to have a unique identifier.

Per example: Imagine a node with the tuple:

defmodule CircularNode do
defstruct [:content, :id]
end

Now let's create a function named link that will represent a pointer between two nodes.

def link(map, nodeA, nodeB) do
Map.put(map, nodeA.id, nodeB)
end

The function only insert a key with node A id pointing do node B.To iterate over our list, lets write a function next to return the next element from the list.

def next(map, node) do
map[node.id]
end

Everything is in place to create our list:

a = %CircularNode{content: "content a", id: "id1" }
b = %CircularNode{content: "content b", id: "id2"}
map=%{}
map = CircularList.link(map, a, b)
map = CircularList.link(map, b, a)

And finally, let's test it:

iex(39)> next = CircularList.next(map, a)
%CircularNode{content: “content b”, id: “id2”}
iex(40)> next = CircularList.next(map, next)
%CircularNode{content: “content a”, id: “id1”}
iex(41)> next = CircularList.next(map, next)
%CircularNode{content: “content b”, id: “id2”}
iex(42)> next = CircularList.next(map, next)
%CircularNode{content: “content a”, id: “id1”}

Ok, this is a list. What about trees?

defmodule Tree dodef get(map, root, direction) do
Map.get(map, root.id)
|> Map.get(direction)
end
def insert(map, root, node, direction) do
new_links = map
|> Map.get(root.id, %{})
|> Map.put(direction, node)
map = Map.put(map, root.id, new_links)
# pointer to parent
parent_links = map
|> Map.get(node.id, %{})
|> Map.put(:parent, root)
Map.put(map, node.id, parent_links)
end
end

Maps of maps? Seems very hacky. Yes it is, but works:

a = %TreeNode{content: "content a", id: "id1"}
b = %TreeNode{content: "content b", id: "id2"}
c = %TreeNode{content: "content c", id: "id3"}
tree=%{}
tree = Tree.insert(tree, a, b, :left)
tree = Tree.insert(tree, b, c, :left)
iex(46)> Tree.get(tree, a, :left)
%TreeNode{content: "content b", id: "id2"}
iex(47)> Tree.get(tree, b, :left)
%TreeNode{content: "content c", id: "id3"}
iex(48)> Tree.get(tree, c, :parent)
%TreeNode{content: "content b", id: "id2"}

You may have notice that we are inserting the whole TreeNode in the map, using separate structure for data and another for the index is much efficiently, but out of the scoped for this article.

Ultimately, the graph… I will leave to you this one.

FYI this is how ligraph handle it:

This complexity is due the fact that libgraph support weighted directed graphs. For a simple graph a vertex and edge map should be enough.

Conclusion:

Elixir immutability can really increase the complexity to implement some data structures. Nothing that we can't handle, in fact most of devs will never need to rollout their on data structure and there is some pretty good libraries like libgraph and narytree out there. The auxiliary map method that is presented in this article is not the only way to create circular structure in elixir. Erlang digraph uses ETS tables per example.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store