Stream.unfold/2
Tags: elixir
Published: 2019-10-13 21:31:11

In Elixir's core lib, there is a function called `Stream.unfold/2`.

When I first started to have a look at this function, I could not make sense of what it was supposed to be used for. I have learned that now, and I thought i would share it :)

The name `unfold` surely references the opposite of `fold` (or `reduce` as it is called in `Enum`), but how do you un-reduce something?

`Enum.reduce/3`, `List.foldl/3` and `List.foldr/3` all take a list and reduces it into a single value. `unfold` takes a single value and turns it into a list.

`Stream.unfold/2` takes "the thing" and an emitter function as input. The emitter function must output a tuple with the next emitted element and the next "thing". The whole function returns a stream of all the emitted elements.

## Simple example

Confused? Yes, so was I. Let's have an example. Say we want to turn a binary (our thing) into a list of bytes representing the binary. Yes, we could use `:binary.bin_to_list/1`, but that would not learn us some `unfold`.

```elixir
Stream.unfold(<<1, 2, 3>>, fn
  <<first, rest::binary>> -> {first, rest}
  <<>> -> nil
end)
```

So what's going on here?

* We input "the thing" as `<<1, 2, 3>>`
* We input a function that emits a tuple with the first byte of the binary (next element) and the rest of the binary (next "thing").
* When we have no more elements, the function returns `nil`. This indicates to `Stream.unfold/2` that the stream is stopping here.

The output of this function is not a list of three bytes. It's apparently a function:

```elixir
#Function<65.33009823/2 in Stream.unfold/2>
```

This is actually a stream that we can use in the `Enum` and `Stream` modules. We could for example turn it into a list:

```elixir
Stream.unfold(<<1, 2, 3>>, fn
  <<>> -> nil
  <<first, rest::binary>> -> {first, rest}
end)
|> Enum.to_list()
```

Which will give the expected bytes:

```elixir
[1, 2, 3]
```

We could have achieved the same thing with a recursive function with an accumulator like so:

```elixir
defmodule MyMod do
  def bin_to_list(binary), do: bin_to_list(binary, [])

  defp bin_to_list(<<first, rest::binary>>, acc), do: bin_to_list(rest, [first | acc])
  defp bin_to_list(<<>>, acc), do: Enum.reverse(acc)
end
```

## Fibonacci numbers as a Stream (FaaS)

It seems we can use `Stream.unfold/2` instead of recursive functions in some cases. Here is another example: Calculating fibonacci numbers:

```elixir
fib = Stream.unfold({1, 1}, fn {a, b} -> {a, {b, a + b}} end)
```

Here we cleverly use a tuple of `{current, next}`, which is all the in-memory data we need to calculate the fibonacci sequence.

This will give us a stream of fibonacci numbers. Obviously, we can't make this into a list, since the stream never ends, but we can manipulate it in any way we can with other streams:

```elixir
fib |> Enum.take(10) 
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

fib |> Enum.at(100) 
# 573147844013817084101

fib |> Stream.map(& &1 * 2) |> Enum.take(10)
# [2, 2, 4, 6, 10, 16, 26, 42, 68, 110]
```

## Other examples

Endless stream of two-exponents

```elixir
two_exp = Stream.unfold(1, &{&1, &1 * 2})

two_exp |> Enum.take(10)
# [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

two_exp |> Enum.at(16) 
# 65536
```

Endless stream of FizzBuzz

```elixir
fizz_buzz =
  Stream.unfold(1, fn n ->
    elem =
      case n do
        n when rem(n, 15) == 0 -> "FizzBuzz"
        n when rem(n, 3) == 0 -> "Fizz"
        n when rem(n, 5) == 0 -> "Buzz"
        n -> Integer.to_string(n)
      end

    {elem, n + 1}
  end)

fizz_buzz |> Enum.take(20)
# ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", "16", "17", "Fizz", "19", "Buzz"]
```

## When to use unfold

`Stream.unfold/2` is nice in two scenarios:

* Instead of a recursive function, because it is desired to write it in-line.
* To easily wrap a recursive behaviour in a Stream.

Examples of the first scenario include the first example in this post about splitting a binary into bytes.

Examples of the second scenario could be the Fibonacci or FizzBuzz above.

Note that the two scenarios may overlap if a recursive logic is both desired to have inline and wrapped in a Stream :)