unfold

Every functional programmer loves fold. fold is universal and expressive. But fold has a secret twin brother named unfold which undoes what fold does. In this post, we will see what unfold is and how it is related to fold.

unfoldr builds a list from a seed value while foldr reduces a list to a summary value.

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr takes the element and returns Nothing if it is done producing the list or returns Just (a, b), in which case, a is a prepended to the list and b is used as the next element in a recursive call.

For example, we can define iterate as follows:

iterate f == unfoldr (\x -> Just (x, f x))

Another simple use of unfoldr:

> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

As the name suggests, unfold is the categorical dual of fold. (Maybe it should be cofold instead of unfold.) It means we can get the signature of foldr by reversing the arrows of unfoldr, and vice versa.

Let’s try this.

unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
foldr   :: (Maybe (a, b) -> b) -> ([a] -> b)

Oops! It is not our beloved foldr function whose signature is:

foldr :: (a -> b -> b) -> b -> [a] -> b

Type isomorphisms

But don’t be disappointed! We can show that they represent the same thing by using type isomorphisms:

(a → b → b) → b → ([a] → b)

by a -> b -> c ~= (a, b) -> c

((a, b) → b) → b → ([a] → b)

by a ~= () -> a

((a, b) → b) → (() -> b) → ([a] → b)

by a -> b -> c ~= (a, b) -> c

(((a, b) → b), (() -> b)) → ([a] → b)

by ((a -> c), (b -> c)) ~= Either a b -> c

((Either (a, b) ()) → b) → ([a] → b)

by Either a () ~= Maybe a

(Maybe (a, b) -> b) → ([a] → b)

Now we can clearly see that unfold is the dual of fold. If you want to learn more on the relationship between fold and unfold, see Conal Elliott’s Folds and unfolds all around us.

Implementation

Here’s an implementation of unfoldr.

unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
                Just (a, b') -> a : unfoldr f b'
                Nothing -> []