Marty Stumpf
7 Apr 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 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
.
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 anamorphismunfold
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:
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!
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:
Foo
to Bar
it means that every Bar
is (or should be, or can be made into) a Foo
.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
.
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!
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.
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!
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.
See other articles by Marty
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!