Ruby to Elixir: Holding State

I’ve been using this year’s Advent of Code as an excuse to learn and practice using Elixir. Elixir is a functional programming language that shares some stylistic similarities with Ruby.

While they often look similar, many of the core concepts a very different. One of these is the concept of state. In Elixir all data is immutable. Adding items into lists or maps (what would be called a Hash in ruby) creates new lists or maps and leaves the original untouched.

This data immutability is an important part of how Elixir provides fast and safe concurrency. It also forces developers to write code in a functional style. However, it poses a problem, what if I need to carry some state? For instance, if I’m writing a graph walking algorithm and need to keep track of the nodes that have already been visited, or what if I need to memoise some algorithm like factorial or Fibonacci? In ruby, I would simply write to some instance level hash or list. In Elixir, we need to make use of the Agent module.

In Elixir, the concept of state is abstracted to an agent. An agent provides an interface to fetch and update a piece of state forming a very simple client-server pattern between the calling code on the Agent holding the state. The example in the Elixir docs shows an agent being used to store a simple counter. The state in that example is a simple integer, but it could be a list, a map, or something even more complex.

Factorial Example

One of the challenges in this year’s advent of code called for an implementation of something similar to a factorial, but with the sum of numbers rather than the product of them. It is common to Memoize the factorial algorithm to make it performant. One way to do this in Elixir is to use the Agent module to keep a map of the computed values.

defmodule Factorial do
  use Agent

  def start do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end, name: __MODULE__)
  end

  def factorial(n) do
    cached_value = memo(n)
    if cached_value do
      cached_value
    else
      value = n + factorial(n - 1)
      memo(n, value)
      value
    end
  end

  def memo(n) do
    Agent.get(__MODULE__, &(Map.get(&1, n)))
  end

  def memo(n, value) do
    Agent.update(__MODULE__, &(Map.put(&1, n, value)))
  end
end

Factorial.start() # {:ok, #PID<1.234.5>}
Factorial.factorial(128) # 8256

Other Examples

More examples from my implemetations for this year’s advent of code:

Conclusion

Elixir is an expressive and powerful language, but sometimes requires looking at problems a different way, especially if you’re used to imperative and object oriented code.