More on Anamorphism: Unfolding More Than List in Haskell
7 Apr 2022
7 April 2022
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 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
A Type Class for Unfold
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
fwhich returns a pair
(a, b’). I.e.,
f b = (a, b’). A list anamorphism
unfoldis: 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:
- Return an empty list. This implies that we need a structure for which empty is defined.
- Return a result which
:) 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
Barit means that every
Baris (or should be, or can be made into) a
- Dotted lines indicate some other sort of relationship.
We can see that
Foldable are related too! We'll cover more of these type classes in later posts. For now, we'll focus on
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](https://hackage.haskell.org/package/base-184.108.40.206/docs/Prelude.html# g:9) for
semigroup, you will see that there's only one method:
(<>) :: a -> a -> a
(<>) 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]
(++) satisfies the requirement for
semigroup, it is an instance of
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!
We still need the requirement that **empty is defined**.
Monoid has such requirement on top of the
semigroup requirement. From the [reference](https://hackage.haskell.org/package/base-220.127.116.11/docs/Data-Monoid.html# g:1),
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
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
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!
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.See other articles by Marty