Fibbing with Elixir

I've been reading through Classic Computer Science Problems in Python (CCSPiP) by David Kopec recently and had the half baked idea that it might be interesting to see the same problems done in a functional language. This post corresponds to Chapter 1 Section 1 in CCSPiP. So let's explore some ways to express Fibonacci numbers with Elixir!

We'll touch on a few approaches to mirror Kopec's treatment of the topic:

• Recursive
• Memoization (aka Caching)
• Iterative

But first, a refresher

In case anyone forgot or didn't bother going to the Wikipedia page, the Fibonnaci sequence can be defined as:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

And a Fibonnaci number is one of those resulting values, such as 0, 1, 1, 3, 5, 8, 13, 21, etc... They tend to be relegated to the occasional technical interview and computer science lecture, but otherwise live a quiet existence calculating rabbit population growth and planning poker for Scrum.

Recursion: Lather. Rinse. Repeat.

We start with a look at the recursive approach. To calculate the value of fib(n) we first calculate fib(n-2) and fib(n-1) until we reach the base case of fib(0) = 0:

def fib(n) when n < 2, do: n

def fib(n) do
  fib(n - 2) + fib(n - 1)
end

The first fib/1 uses a guard such that it only is used when n < 2. It is the base case. Otherwise, we use the second fib/1 , which triggers recursive calls for the next values... eventually they will call the first fib/1 and stop recursing.

It should be noted that this code could be rewritten into one function with an if else block:

def fib(n) do
  if (n < 2) do
    n
  else
    fib(n - 2) + fib(n - 1)
  end
end

I prefer the first snippet as it feels a bit cleaner, but both work well enough for small values of n. But what if we wanted to minimize the number of computations being done? After all, if we compute fib(10) once, repeating the same calculation is wasteful. Perhaps we can memoize the values?

Did you get the memoization memo?

In a nutshell, memoization is an optimization technique for slapping (potentially) expensive computation into some sort of cache for later reuse. Memoization makes sense for your run of the mill language that lets you play fast and loose with state. However, Elixir doesn't like having state in its functions and modules. This is unfortunate as memoization is a reasonable choice for recursive Fibonacci sequences. It seems we've reach an impasse!

Fear not - though memoization is all about maintaining state and Elixir is all about not maintaining state, we just have to get fancy. The most likely approach would be to utilize GenServer or an ETS table. There also exist robust memoization libraries, such as Memoize. I'm not about to bust those out for a small blog post, but they are available.

Let's iterate on this a bit

Recursion is said to be divine but there is always that one person who chimes in saying the recursive solution will never cut it in production. And they'd be right in this case -  recursively calculating the 100th Fibonacci number with the above snippets won't be an effective use of time.

For those that simply crave an iterative solution, we can use the Stream module... in particular, Stream.unfold/2. Note, we start from fib(0) and work up to fib(n) rather than the other way around as seen in the recursive solutions:

def fib() do
  Stream.unfold( {0, 1}, fn ({current, next}) ->
    {current, {next, current + next}}
  end)
end

The unfold function takes an initial accumulator and a function that returns a tuple with the current value and next accumulator. When the accumulator is a tuple itself everything shakes out perfectly for calculating a new value based on the previous one. To use it, we can pipe the output into another function like so:

iex(1)> Fib.fib() |> Enum.at(100)
354224848179261915075

This approach has the added benefit of being lazy... the generator function is only computing values as needed. Though note that if you use a value, everything up to and including the next value is computed as well (the current + next tidbit).

Fun fact: you'd have an infinite loop of sorts by replacing the Enum.at/2 with something like Enum.take_while(fn(x) -> x == x end).

That's a lot of rabbits

All in all, there are strong parallels between the Python code in Kopec's book and the Elixir seen here. Of course, this might just be by virtue of the subject at hand being well defined and "math-y".

I will note that the most significant distinction I found is avoding introducing state in the Elixir solutions. Not being able to trivially store and mutate state makes the translation from Python to Elixir rather intriguing.

Photo by Diana Măceşanu on Unsplash