We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or registerto boost this post!

Show some love to the author of this blog by giving their post some rocket fuel ðŸš€.

Login to see the application

Engineers who find a new job through Blockchain Works average a 15% increase in salary ðŸš€

You will be redirected back to this page right after signin

Anamorphisms aka Unfolds Explained

Marty Stumpf 13 May, 2021 | 4 min read

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`!

Join over 111,000 others and get access to exclusive content, job opportunities and more!

`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.

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!

Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

Related Issues

cosmos / gaia
• Started
• 0
• 6
• Intermediate
• Go
cosmos / gaia
• Started
• 0
• 3
• Intermediate
• Go
cosmos / ibc
• Started
• 0
• 2
• Intermediate
• TeX
cosmos / ibc
• Open
• 0
• 0
• Intermediate
• TeX

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Blockchain Works average a 15% increase in salary.