Easier Recursion

Let's use recursion to model The Fibonacci Sequence. We'll say that we would like to be able to fetch a specific number or look at the first several numbers of the sequence. Here's what that code could look like:

  defmodule FibonacciRecursion do
    def advance({nil, 0}), do: {0, 1}
    def advance({prev, cur}), do: {cur, prev + cur}

    def at(seq \\ {nil, 0}, n)
    def at(seq, 0), do: elem(seq, 1)
    def at(seq, n) do
      seq
      |> advance()
      |> at(n - 1)
    end

    def take(seq \\ {nil, 0}, n, acc \\ [])
    def take(_seq, 0, acc), do: Enum.reverse(acc)
    def take(seq, n, acc) do
      take(advance(seq), n - 1, [elem(seq, 1) | acc])
    end
  end

  FibonacciRecursion.take(10) |> IO.inspect()
  FibonacciRecursion.at(9) |> IO.inspect()

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
34

This code separates the business logic (FibonacciRecursion.advance/1) from the interface (FibonacciRecursion.at/2 and FibonacciRecursion.take/2). The interface functions are where we see the recursive approach.

This works fine, obviously, but there are a few drawbacks. First, we may need to dream up a new strategy for each way that we want to access this data. Both existing functions keep dropping a counter to tell when to stop, but one of them also has to build up an accumulator as it works. We could generalize this by introducing mechanisms to control when to stop and for assembling the output, but that would introduce some additional complexity. That brings me to another point.

Recursion very often involves three things at once:

• The actual work we're doing (generating Fibonacci numbers)
• Checking for the stop case (when our counter reaches some predetermined value)
• Creating the desired outcome (keeping track of the last number or building a list of all of them)

I struggle to address those elements individually when I'm coding up something complex. I generally feel like I have to do the whole thing together. It's more mental overhead to manage.

Circling back to the first problem, if we later decide that we want the second set of ten numbers or to find the first number in the sequence over 100, we will have to introduce two new recursion strategies or that generalization layer discussed previously. The mental overhead continues to rise.

It took me a while, but I think Stream has become one of my favorite modules in Elixir.

Earlier on I had some weird mental block about thinking that it was similar to Enum, but slower in many cases. I now know that I was confused on multiple levels.

First, it's not like an Enum, it is an Enum and that's awesome! It means that we can use all of the iterators to help us build.

Also, Stream is not about speed. It's about controlling the flow of iteration. We can use it to transform a list of items one at a time while we search for a specific one that we need and avoid working through the rest of the list after we've found it. We can also use it to build potentially infinite sequences of data.

The real irony is that — since I've figured out how to use Stream properly — I've been able to drastically outpace replaced Enum operations on several occasions.

Let's focus in on one function of the Stream module to show what all of this means. A great place to begin is Stream.iterate/2. This one function isn't too tough to get the hang of and it can be used in a lot of cases.

The idea is simple. You pass Stream.iterate/2 two things:

• Some starting data
• A function that turns any given piece of data into the next piece of data, also known as a reducer

The Stream call returns an enumerable that will infinitely step through the data until it's instructed to stop. During iteration it will first return the starting data. Then it will call the passed function with the starting data and return the result. Then it will call the passed function with that previous result and return the new result. And so on.

starting -f.(starting)-> result -f.(result)-> next_result -f.(next_result)-> …

The emitted values are the variable contents before each function call in that flow: starting, result, next_result, …

Let's take our first step toward converting our Fibonacci generator to this new model:

  defmodule Fibonacci do
    def stream(seq \\ {nil, 0}) do
      Stream.iterate(seq, fn
        {nil, 0} -> {0, 1}
        {prev, cur} -> {cur, prev + cur}
      end)
    end
  end

  Fibonacci.stream()
  |> Enum.take(5)
  |> IO.inspect()

[{nil, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 3}]

We're definitely not all the way back to the desired outcome yet, but you can find the sequence hiding in there if you squint a bit.

What's more interesting is what isn't there. We haven't had to worry about how we'll actually stop things so far. The use of |> Enum.take(5) is just a handy trick that's available to us, now that we can use the iterators, for peeking in on how things are going.

We also haven't decided to care about producing the final output at this point. As we'll see shortly, that's trivial to add on when we're ready.

We've really just recreated the business logic here, in a slightly different form. This is about a third of the cognitive load of the recursive interface at this point. We can worry about those other concerns separately. We don't need to solve the whole problem in one move.

Let's take those last steps to see it all come together:

  defmodule Fibonacci do
    def stream(seq \\ {nil, 0}) do
      seq
      |> Stream.iterate(fn
        {nil, 0} -> {0, 1}
        {prev, cur} -> {cur, prev + cur}
      end)
      |> Stream.map(fn {_prev, cur} -> cur end)
    end
  end

  # the two original examples
  Fibonacci.stream()
  |> Enum.take(10)
  |> IO.inspect()

  Fibonacci.stream()
  |> Enum.at(9)
  |> IO.inspect()

  # the considered expansions
  Fibonacci.stream()
  |> Stream.drop(10)
  |> Enum.take(10)
  |> IO.inspect()

  Fibonacci.stream()
  |> Enum.find(fn n -> n > 100 end)
  |> IO.inspect()

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
34
[55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
144

That may look like a bunch of code, but most of it is examples. We've recreated the two we started with and added on the two possible additions mentioned earlier. Note how it's now easy to combine Stream and Enum staples to get at the data any way we can dream up.

This is possible because we now stream the actual sequence of numbers. That's the most significant change in this version: we add on a call to Stream.map/2 to transform the underlying data structure into the numbers that we care about as it iterates. That's really all it takes!

I've used this strategy in a wide range of cases:

• Analyzing data from File.stream!/3 and CSV.decode!/2
• Ingesting Web API's
• Running simulations until specific criteria are met
• Building complex graph and tree data structures
• Pathfinding algorithms

I take a very similar approach each time. I start by building a struct that holds all the details of the work that needs doing: inputs, resources, calculations, caches, stage tracking, partial results, and whatever else it takes. Then I build a reducer function that can advance the work one step at a time by taking the current struct and returning an updated one. I end with an iteration pipeline that passes a starting struct and the reducer into something like Stream.iterate/2 and uses other iterators to hunt for the expected results.

There are other great tools hiding in the Stream module. For example, Stream.unfold/2 is an upgraded Stream.iterate/2 that I use a lot. It adds the ability to differentiate between what the stream emits and carries forward as well as the ability for the reducer function to end the stream. Just remember that those quality of life improvements aren't strictly needed! We changed emitted values with Stream.map/2 and ended the stream with Enum.find/3 in the previous code block.