Stream.unfold/2

#elixir

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.

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:

#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:

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

Which will give the expected bytes:

[1, 2, 3]

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

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:

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:

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

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

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 :)

Top comments (4)

Mitch Spradlin • Oct 17 '19

I think the general term for what unfold/2 implements is an anamorphism, while fold is a catamorphism. There are other kinds of morphisms too - this page gives an overview (with fun mnemonics!): reasonablypolymorphic.com/blog/rec...

Lasse Skindstad Ebert • Oct 17 '19

Thanks, didn't know those terms. I tried quick-reading the post you linked to, but I think it's the kind of post I need focus to read 😁 Goes to my reading list 👍