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 do
def 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:

A map of vertex ids to vertices (vertices)

A map of vertex ids to their out neighbors (out_edges),

A map of vertex ids to their in neighbors (in_edges), effectively the transposition of out_edges

A map of vertex ids to vertex labels (vertex_labels), (labels are only stored if a non-nil label was provided)

A map of edge ids (where an edge id is simply a tuple of {vertex_id, vertex_id}) to a map of edge metadata (edges)

Edge metadata is a map of label => weight, and each entry in that map represents a distinct edge. This allows us to support multiple edges in the same direction between the same pair of vertices, but for many purposes simply treat them as a single logical edge.

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.