Stream.unfold/2

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

Comments

[Mitch Spradlin]

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]

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 👍

[Robert Dober]

I would not say that Stream.unfold is a bad name, however, for folks of my generation it is what we know as cons_stream from SIOCP

[Lasse Skindstad Ebert]

I didn't know that ☺️