You Can Unfold So Much More with Monoid: Examples

This is the eighth 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 wrote an unfold function that works for the Monoid type class. In this post we'll look at some examples of applying our unfold to other type instances of Monoid.

Unfolding a List

With Haskell's unfoldr

Recall Haskell's default unfold with this signature:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

Note that this unfold takes an initial input. We saw an example of its usage:

example :: (Ord a, Num a) => a -> [a]
example = unfoldr (\x -> if x > 9 then Nothing else Just (x, x+1))

example 7 returns:

[7,8,9] 

With Our Monoid unfoldm

Our unfold is more general which means we can unfold to a list using it, like Haskell's default unfold. Recall our unfold's type signature:

unfoldm :: Monoid m => (t -> Maybe (m, t)) -> t -> m 

Note that the Maybe returns a tuple with its first element of a type that belongs to the Monoid type class. When we use our unfoldm, we need to make sure of that. To apply unfoldm in a manner similar to the above example, we have to return [x] not just x in the else case:

example = 
  unfoldm (\x -> if x > 9 then Nothing else Just ([x], x+1))

Running example 7 returns the same result as above.

Unfolding to Other Monoid Types

Now, let's unfold to other Monoid types!

Unfolding to Map

Haskell has a Map data type. As mentioned in its reference:

data Map k a

A Map from keys k to values a. 

Instance
Ord k => Monoid (Map k v)

Map is a data type that maps keys to their values, similar to a dictionary. When you look up a key (or a word in the case of a dictionary), you get its associated value (or in the case of a dictionary, the meaning of the word).

Map belongs to the Monoid type class if the key k is orderable . This means that if the key is orderable, we can use our unfold function to unfold to a Map!

Here is an example of a unfolding a Map with keys that are of a type such that k > 26 is valid:

import Data.Map as Map

-- our unfoldm from the last post
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

mapExample :: (Ord k, Num k, Enum v) => (k, v) -> Map.Map k v     
mapExample =     
  unfoldm 
    (\(x,y) ->     
      if x > 26 then Nothing           
      else Just ((Map.insert x y empty),((x+1),(succ y))))

Because the type of the keys also belongs to the Ord typeclass, this Map belongs to the Monoid typeclass. Therefore, we can use our unfoldm function with it.

I have specified the value is of a type that belongs to the Enum typeclass. This allows me to use the succ (successor) function.

The function we input to our unfoldm takes a tuple. The first element of the tuple is the key, while the second element is the value.

The unfolding stops when the key is greater than 26. We start with the input key and value, then we mappend (or insert in this case with Map) with the key goes up by 1 and the value being the successor of the current value each time.

Running mapExample with the integer 1 and the Char K, or (1,'K') gives:

*Main> mapExample (1,'K')
fromList [(1,'K'),(2,'L'),(3,'M'),(4,'N'),(5,'O'),(6,'P'),(7,'Q'),(8,'R'),(9,'S'),(10,'T'),(11,'U'),(12,'V'),(13,'W'),(14,'X'),(15,'Y'),(16,'Z'),(17,'['),(18,'\\'),(19,']'),(20,'^'),(21,'_'),(22,'`'),(23,'a'),(24,'b'),(25,'c'),(26,'d')]

Running it with the value of type Float works too, because it belongs to the Enum class:

*Main> mapExample (0,1.55)
fromList [(0,1.55),(1,2.55),(2,3.55),(3,4.55),(4,5.55),(5,6.55),(6,7.55),(7,8.55),(8,9.55),(9,10.55),(10,11.55),(11,12.55),(12,13.55),(13,14.55),(14,15.55),(15,16.55),(16,17.55),(17,18.55),(18,19.55),(19,20.55),(20,21.55),(21,22.55),(22,23.55),(23,24.55),(24,25.55),(25,26.55),(26,27.55)]

Because the output of mapExample is a Map, we can apply Map's method on it, for example, we can look up the value of a specific key using lookup:

*Main> Map.lookup 10 (mapExample (1,'K'))
Just 'T'

Unfolding to Set

The Set e type represents a set of elements of type e. If e is an orderable type then the Set e type belongs to the Monoid typeclass.

I challenge you to write a function that unfolds to a Set using unfoldm. Have fun!

As you can see, once we master some functional programming concepts, we can apply them in any way we want to great effect! With the concept of unfold and the Monoid type class, we built a more powerful unfold function. This is what I love about functional programming: it's so powerful!

In a later post, I will explain the concept of list being a free Monoid - it will shed light on why Map can be generated by a fromList function above.