# 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 = []`.

``````--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. In the next post, we will look at unfolding to more structures. Stick around!

Posted

in

by

Tags: