Anamorphisms aka Unfolds Explained

This is the sixth of a series of articles that illustrates functional programming (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.

In the last post, we learned about folding nonempty structures. In this post, we'll learn about another recursion scheme: anamorphisms, also referred to as unfolds.

Fold and Unfold

Unfolds can be thought of as the dual of folds. As Conal Elliott puts it: while folds contract a structure down to a value, unfolds expand a structure up from a value!

How are they dual to each other? Folds output a value from a list while unfolds output a list from a value. They both take a function as an input which describes the fold/unfold process. In folds, the function is applied to elements of the input list. The elements are folded into a value as the function applies to each element. In unfolds, the function is applied to the input value and is unfolded to a whole list.

Folds can have a base case value for when the input list is empty. Unfold can have a predicate that describes the condition when the list should stop expanding. If no condition is given, what do we get? That’s right! An infinite list!

iterate in Haskell

Before looking at the unfoldr function in detail, let's look at a specific case of unfoldr: iterate. iterate is a function that unfolds without a predicate. It takes a function and an initial input, and returns an infinite list with the function applies to the input recursively. As stated in the prelude:

iterate :: (a -> a) -> a -> [a]

iterate f x returns an infinite list of repeated applications of f to x: iterate f x == [x, f x, f (f x), ...]

For example, let f x = 2*x, the result of iterate f 1 is [1, 2*1, 2*(2*1), 2*(2*2*1),...]

We can see this in GHCi. We need to take the first 10 results of (iterate (*2) 1) with take 10 because otherwise GHCi would not stop printing the infinite list:

Prelude> take 10 (iterate (*2) 1)
[1,2,4,8,16,32,64,128,256,512]

If you look at the source code, you will see that iterate is written with unfoldr:

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

Let's see how that works by learning more about unfoldr!

unfoldr in Haskell

You can find the unfoldr method in the Data.List module in Haskell. It has the following signature:

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

The first argument to unfoldr is a function that takes an argument of type b and returns a Maybe (a, b). That is, the return value is either Nothing (when the predicate is true) or a pair (when the predicate is false).

The second argument to unfoldr is the initial input to the first argument.

Unfolds take an initial input, apply it to a function that returns a pair, and repeat the process to the second of the pair while joining the outputs in a list.

The Formal Definition of Unfolds

The formal definition of unfolds is:

Given

(1) a predicate p which returns a bool. I.e., p b = True or p b = False.

(2) a function f which returns a pair (a, b’). I.e., f b = (a, b’).

A list anamorphism unfold is

When p b = True, unfold b = [],

otherwise, unfold b = a : unfold b’.

That is, for each unfold we just need to specify p and f and give it a value b. Let’s see an example to illustrate this definition! E.g., if we want a list [b, b+1, b+2, …, 9] then:

Let p b = b > 9 and f b = (b, b + 1), so:

When b > 9 unfold b = [],

otherwise, unfold b = b : unfold (b + 1).

E.g., when b = 7:

unfold 7 = 7 : unfold 8 because 7 > 9 evaluates to False

=> [7, (8 : unfold 9)] because 8 > 9 evaluates to False

=> [7, 8, (9 : unfold 10)] because 9 > 9 evaluates to False

=> [7, 8, 9] because 10 > 9 evaluates to True and thus unfold 10 = [].

In Haskell:

--Import Data.List so that we can use the unfoldr function. 
import Data.List

-- example takes the initial input and returns a list
-- p and f are combined into one function which you input to unfoldr
example :: (Ord a, Num a) => a -> [a]
example = unfoldr (\x -> if x > 9 then Nothing else Just (x, x+1))

--Print out results of (example 7) and (example 0).
main = do
  print (example 7)
  print (example 0)

In a terminal, run runhaskell on the file with the above code. (runhaskell runs the .hs file you specify.) You will see the lists you created:

[7,8,9][0,1,2,3,4,5,6,7,8,9]

Looking back at iterate:

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

We have specified that the function input to unfoldr is (\x -> Just (x, f x)). That is, we specify that with iterate, we always return the next output by applying the function f to it, hence the infinite list [x, f x, f (f x), ...].

Since the list constructors are in the definition of unfoldr, unfoldr always expands to a list, not other structures. This is unlike folds which applies to any foldable types.

And that's it! You've learned another recursion scheme, unfolds. In the next post, we'll look at another recursion scheme: hylomorphisms. Stay tuned!