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

More on Anamorphism: Unfolding More Than List in Haskell

Marty Stumpf 27 July, 2021 | 3 min read

This is the seventh 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, I mentioned that Haskell's unfold only works for lists. But why can't it be like fold which can work on a whole type class? Recall that fold works for any Foldable type.

In this post, I will show you an unfold function that can work on more than list. I first explain the Monoid type class, then I show a more general unfold than Haskell's default unfold. In the next post, I will show examples of a few things you can do with this unfold function that you can't do with Haskell's default unfold.

A Type Class for Unfold

Like the Foldable type class for fold, the type class for unfold needs to fulfill some requirements such that the structure can be unfolded. What requirements do we need? Let's revisit the formal definition of unfold for list:

Given a predicate and a function f which returns a pair (a, bโ€™). I.e., f b = (a, bโ€™). A list anamorphism unfold is: When the predicate is true, unfold b = [], otherwise, unfold b = a : unfold bโ€™.

Notice that we need to be able to perform two things depending on whether the predicate is true or not:

  1. Return an empty list. This implies that we need a structure for which empty is defined.
  2. Return a result which cons (:) or appends one value to another.

That's it! We can unfold any structure that fulfills these two requirements! It so happens that Monoid describes exactly such a structure!

The Monoid Type Class

We talked about typeclasses in an earlier post - readers who are not familiar with them may want to review it before proceeding.

Monoid is not to be confused with Monad. However, they are related, as depicted from the below graph from Typeclassopedia:

  • Solid arrows point from the general to the specific; that is, if there is an arrow from Foo to Bar it means that every Bar is (or should be, or can be made into) a Foo.
  • Dotted lines indicate some other sort of relationship.

We can see that Monoid and Foldable are related too! We'll cover more of these type classes in later posts. For now, we'll focus on Semigroup and Monoid.

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

Semigroup

Semigroup is a superclass of Monoid, i.e., anything that belongs to the Monoid type class also belongs to the Semigroup type class. This is because the requirement for a type to be a Semigroup is also a requirement for the Monoid type class!

Looking at the reference for semigroup, you will see that there's only one method:

(<>) :: a -> a -> a

The function (<>) has to satisfy associativity. I.e., the following has to hold for <>:

 x <> (y <> z) = (x <> y) <> z

And that's it! For example, list is an instance of semigroup because the append function ((++)) is associative:

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

Because we know that:

[1,2] ++ ([3,4] ++ [5,6]) 
= [1,2,3,4,5,6]
= ([1,2] ++ [3,4]) ++ [5,6]

Because list's (++) satisfies the requirement for semigroup, it is an instance of semigroup.

If a type is an instance of the semigroup we know that we can append a value to another, which is what we need for unfolds!

Monoid

We still need the requirement that empty is defined. Monoid has such requirement on top of the semigroup requirement. From the reference, Monoid has the following methods:

mempty :: a

mappend :: a -> a -> a

The requirement for mappend is exactly as the (<>) method of Semigroup. That's why the reference mentions that this method is redundant and has the default implementation mappend = (<>).

These are the requirements for mempty:

Right identity
    x <> mempty = x
Left identity
    mempty <> x = x

That is, it has to be the case that when you append anything to mempty from the left or right, you get the same thing. This is exactly what we need for unfolds.

For list, the empty list fullfills the requirements for mempty because we know that [] <> [a] = [a] and [a] <> [] = [a]. List is therefore an instance of the Monoid type class.

A More General Unfold

Now we are ready to write our unfold by requiring the Monoid type class:

unfoldm :: Monoid m => (t -> Maybe (m, t)) -> t -> m 
unfoldm f a = 
  case f a of 
    Just (first, second) ->
      first `mappend` (unfoldm f second)
    Nothing -> mempty

We implement the same function as the list version but replace the empty list with mempty and the (:) with mappend. Doing so lets us generalize the function to work for all types that belong to the Monoid type class.

In the next post, I will go into detail about how we use this, along with some examples to illustrate how powerful this is. 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

open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML

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