I've been reading through Classic Computer Science Problems in Python (CCSP) 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 CCSP. 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:
- Memoization (aka Caching)
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-1) until we reach the base case of
fib(0) = 0:
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:
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:
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.