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 toStream.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)
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...
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 π
I would not say that
Stream.unfold
is a bad name, however, for folks of my generation it is what we know ascons_stream
from SIOCPI didn't know that βΊοΈ