Elixir by Example

Erlang Data Structures

Edit any cell and run it in your browser Download source

Elixir runs on the Erlang VM, and every Erlang module is yours to call. An Erlang module's name is a plain atom, so :queue.new() calls the new function in Erlang's queue module. Erlang's docs write it queue:new().

q = :queue.new()
IO.inspect(:queue.is_empty(q), label: "empty?")
empty?: true

Erlang's standard library has a few data structures Elixir doesn't. This page covers the ones worth knowing and when each one beats a list or a map.

First, a difference in style. Elixir functions take the "subject" first, so they pipe. Many Erlang functions take the item first and the collection last: :queue.in(item, queue). Pipe a queue into it and the queue lands in the item slot, so the call raises ArgumentError.

try do
  :queue.new() |> :queue.in(1)
rescue
  e in ArgumentError -> IO.puts("piped: " <> Exception.message(e))
end
piped: argument error

So with Erlang modules, bind each step to a variable instead of piping.

q = :queue.in(1, :queue.new())
IO.inspect(:queue.to_list(q), label: "bound")
bound: [1]

:queue, a first-in first-out line

A list is a poor queue: taking from the front is cheap, but adding to the back copies the whole list. :queue keeps two lists, a front and a reversed rear. in/2 pushes onto the rear, out/1 pops the front, and only when the front runs dry is the rear reversed into place. Each item gets reversed once, so both operations are cheap on average.

q = :queue.new()
q = :queue.in(:a, q)
q = :queue.in(:b, q)
q = :queue.in(:c, q)
IO.inspect(:queue.to_list(q), label: "front to rear")
IO.inspect(:queue.len(q), label: "len")
front to rear: [:a, :b, :c]
len: 3

out/1 returns the item and the new queue. The item comes wrapped as {:value, item}, so a stored nil or :empty can't be confused with "nothing there".

{{:value, first}, q} = :queue.out(q)
IO.inspect(first, label: "out")
IO.inspect(:queue.to_list(q), label: "left")
out: :a
left: [:b, :c]

On an empty queue you get {:empty, queue} instead. Match on both shapes with case; this is the loop you'll see in GenServers that hold a queue.

defmodule Drain do
  def all(q, acc \\ []) do
    case :queue.out(q) do
      {{:value, item}, rest} -> all(rest, [item | acc])
      {:empty, _q} -> Enum.reverse(acc)
    end
  end
end

IO.inspect(Drain.all(q), label: "drained")
drained: [:b, :c]

peek/1 looks at the front without removing it, and returns {:value, item} or a bare :empty.

IO.inspect(:queue.peek(q), label: "peek")
IO.inspect(:queue.peek(:queue.new()), label: "peek empty")
peek: {:value, :b}
peek empty: :empty

It's double-ended: in_r/2 pushes onto the front (a "jump the line" item) and out_r/1 pops from the rear.

q = :queue.from_list([2, 3])
q = :queue.in_r(1, q)
IO.inspect(:queue.to_list(q), label: "in_r")
{{:value, last}, q} = :queue.out_r(q)
IO.inspect({last, :queue.to_list(q)}, label: "out_r")
in_r: [1, 2, 3]
out_r: {3, [1, 2]}

Use it when: work arrives at one end and leaves at the other, like jobs waiting for a worker or callers waiting for room.

:gb_trees, a sorted key-value store

Map keys have no order you should rely on. :gb_trees (general balanced trees) keeps keys sorted, so "smallest", "largest" and "first key after X" are cheap. Here, timers keyed by {due_at, name}: tuples compare element by element, so they sort by time, then by name.

timers =
  Enum.reduce(
    [{{30, :flush}, "write buffer"}, {{10, :ping}, "health check"}, {{20, :ping}, "retry"}],
    :gb_trees.empty(),
    fn {key, job}, tree -> :gb_trees.enter(key, job, tree) end
  )

IO.inspect(:gb_trees.to_list(timers), label: "in order")
IO.inspect(:gb_trees.smallest(timers), label: "next due")
IO.inspect(:gb_trees.largest(timers), label: "last due")
in order: [
  {{10, :ping}, "health check"},
  {{20, :ping}, "retry"},
  {{30, :flush}, "write buffer"}
]
next due: {{10, :ping}, "health check"}
last due: {{30, :flush}, "write buffer"}

take_smallest/1 pops the next timer and returns the rest of the tree. lookup/2 reads one key.

{key, job, timers} = :gb_trees.take_smallest(timers)
IO.inspect({key, job}, label: "fired")
IO.inspect(:gb_trees.lookup({20, :ping}, timers), label: "lookup")
IO.inspect(:gb_trees.lookup({99, :nope}, timers), label: "missing")
fired: {{10, :ping}, "health check"}
lookup: {:value, "retry"}
missing: :none

An iterator walks keys in order, and iterator_from/2 starts at the first key greater than or equal to the one you give. next/1 returns {key, value, iterator}, or :none at the end. "First key at or after X" is how a hash ring finds the node that owns a key.

ring = :gb_trees.from_orddict([{100, :node_a}, {200, :node_b}, {300, :node_c}])

owner = fn hash ->
  case :gb_trees.next(:gb_trees.iterator_from(hash, ring)) do
    {_point, node, _iter} -> node
    :none -> elem(:gb_trees.smallest(ring), 1)
  end
end

IO.inspect(Enum.map([50, 200, 250, 350], owner), label: "owners")
owners: [:node_a, :node_b, :node_c, :node_a]

enter/3 inserts or replaces. insert/3 refuses a key that is already there, which catches bugs.

try do
  :gb_trees.insert({20, :ping}, "again", timers)
rescue
  e in ErlangError -> IO.inspect(e.original, label: "insert")
end
insert: {:key_exists, {20, :ping}}

Use it when: you need keys in order, the smallest or largest key, or the next key after a value.

:gb_sets, a sorted set

The same tree without values. A pool of free ids that always hands out the lowest one:

free = :gb_sets.from_list([4, 2, 7])
{id, free} = :gb_sets.take_smallest(free)
IO.inspect(id, label: "handed out")
free = :gb_sets.add(1, free)
IO.inspect(:gb_sets.to_list(free), label: "free ids")
IO.inspect(:gb_sets.is_member(4, free), label: "4 free?")
handed out: 2
free ids: [1, 4, 7]
4 free?: true

Use it when: a set must stay sorted. For plain membership, Elixir's MapSet (an unordered set of unique values) is the usual choice.

:digraph, a graph

:digraph stores vertices and edges, and :digraph_utils runs graph algorithms on it. Unlike everything else on this page it's mutable: it lives in ETS tables (shared in-memory tables, covered in the OTP track), so add_vertex/2 changes g in place and returns no new graph.

g = :digraph.new([:acyclic])
for app <- [:app, :web, :db], do: :digraph.add_vertex(g, app)
:digraph.add_edge(g, :app, :web)
:digraph.add_edge(g, :web, :db)
:digraph.add_edge(g, :app, :db)

A topological sort puts every vertex before the ones its edges point to: an order to start apps that depend on each other, read backwards.

IO.inspect(:digraph_utils.topsort(g), label: "topsort")
topsort: [:app, :web, :db]

Created with :acyclic, it refuses an edge that would close a loop, returning the existing path (:app to :db) that the new edge would turn into a cycle.

IO.inspect(:digraph.add_edge(g, :db, :app), label: "cycle")
cycle: {:error, {:bad_edge, [:app, :db]}}

Being mutable, it must be freed by hand.

:digraph.delete(g)

Use it when: you have real graph questions (paths, cycles, ordering) and can live with mutable state.

Which one?

  • List: items in order, read front to back. Adding to the front is cheap; to the back, not.
  • Map: lookup by key, no order.
  • MapSet: "have I seen this?", no order.
  • :queue: first in, first out, at both ends.
  • :gb_trees / :gb_sets: sorted keys, smallest, largest, ranges.
  • :digraph: vertices and edges.

Erlang also has :array, a functional array of integer-indexed slots with a default value. In Elixir a map with integer keys or a tuple usually reads better, so it's rarely worth reaching for.

Pitfall: a queue's inner shape (two lists) is documented as opaque. Don't match on it or build one by hand; use :queue.is_empty/1, out/1 and friends.

Pitfall: :queue.len/1 walks the whole queue, because queues don't store their length. If you check the length on every call of a long queue, keep a count next to it.

Pitfall: :gb_trees.enter/3 overwrites an existing key without a word. Two timers due at the same moment would collide on a bare due_at key; that's why the example keys on {due_at, name}.

Improve this page on GitHub