We'll see you soon ðŸ‘‹

# More on Anamorphism: Unfolding More Than List in Haskell

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

which returns a pair`f`

`(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:

- Return an empty list. This implies that we need a structure for which
*empty*is defined - 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`

.

We'll see you soon ðŸ‘‹

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

## Related Jobs

## Related Articles

## Related Issues

- Open
- 0
- 0
- Intermediate

- Open
- 0
- 0
- Intermediate

- Open
- 0
- 0
- Intermediate

- Open
- 0
- 0
- Intermediate

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