Irken Kitties

Recreating the Haskell List Part 3: Monoids

This is part 3 of a 6 part tutorial

Monoids

It turns out that cons lists can be more than just a Functor, it can be a Monoid. A Monoid is a object with a single associative binary operation, and an identity element. This means that things like addition and multiplication form a monoid.

The identity element for addition is the number $0$, because $x + 0 = x$. An identity element and any other element, when operated on by the single associative binary operation, is one that does not change the other element. Basically you can add $0$ to any number and you just get the same number. The identity element for multiplication is $1$, because $x \cdot 1 = x$ for every number.

The binary operation should be one which can combine two of the objects, and for a list that happens to be appending them using the function ++.

[1, 2, 3] ++ [4, 5, 6] == [1, 2, 3, 4, 5, 6] Easy enough, so that means the identity element, the element you can combine with a list that will return the same list is: [], the empty list. [1, 2] ++ [] == [1, 2]

The ghci command :info shows that to be an instance of a monoid you must implement the functions mempty which returns the identity element, and either mappend or mconcat. Typeclasses can sometimes have default implementations for some functions, and it’s often the case that two functions are actually defined by default in terms of one another, meaning you only have to implement one of them and the other will automatically work. Here mappend and mconcat are defined in terms of each other so we just decide to implement the easier of the two, mappend

Looking at the type signatures below we can see mappend :: a -> a -> a, where in our case a will be the type MyList. This means mappend receives two lists and returns a third in which they are combined. For addition this would have been receiving two numbers that need to be combined, but for a list it just means to stick them together end to end.

Making MyList a Monoid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import Data.Monoid
:info Monoid
=> class Monoid a where
    mempty :: a
    mappend :: a -> a -> a
    mconcat :: [a] -> a
instance Monoid (MyList b) where
    mempty = Empty
    mappend xs Empty = xs
    mappend Empty ys = mappend ys Empty
    mappend (Cons x xs) ys = Cons x $ mappend xs ys
let list1 = (Cons 1 (Cons 2 Empty))
let list2 = (Cons 3 (Cons 4 Empty))
list1 `mappend` list2
=> Cons {car = 1, cdr = Cons {car = 2, cdr = Cons {car = 3, cdr = Cons {car = 4, cdr = Empty}}}}
[1,2] `mappend` [3,4]
=> [1,2,3,4]
-- mconcat is similar but it flattens a list of lists
mconcat [[1,2], [3, 4]]
=> [1, 2, 3, 4]

Having MyList be an instance of Monoid makes it easier to write the implementation for the Applicative type-class, because mappend is used in its implementation.