Easier Recursion

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!