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 register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary 🚀

You will be redirected back to this page right after signin

Blog hero image

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 our newsletter
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 = [].

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!

Author's avatar
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
  • 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 Functional Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email