haskell - Functors, Applicative Functors and Monoids - Monoids introduction

In this post, we will going to examine the monoid, monoids are a typeclass, which has an associative binary function and a value which acts as an identity with respect to that function. 

 

Before we goes into the details and tell you what its the definiton of monoid from a textbook's definitino, let's see some example which some some trait of monids. 

 

we know '*" operator and the ++ operator which operate on the list argument, and we know this kind of operations. 

 

4*1 == 1 * 4 == 4

[1,2,3] ++ [] == [[ ++ [1,2,3] == [1, 2, 3]

 

to summarize, there exists some values to * and the ++ operator, which when applied, will return the same value no mater which operate together with it. 

 

and there are more.. 

(3 * 2) * (8 * 5) == 3 * (2 * (8 * 5))  

"la" ++ ("di" ++ "da")  == ("la" ++ "di") ++ "da"  

which means the oder of which they operate does not matter, so, the same result will be returned. 

 

with the two properties which we have covered above, here let's see how is the official definition of the Monoids...

 

class Monoid m where  
    mempty :: m  
    mappend :: m -> m -> m  
    mconcat :: [m] -> m  
    mconcat = foldr mappend mempty  

 

to use the Monoid typeclass, you will first need to import the following 

 

import Data.Monoid

 

so, how to construe the monoid type? First is the type called mempty what does it mean? mempty is identity value for a particular monoid, it is a polymorphic constant. 

 

next, it is the mappend, it works well in the mind with the ++ operator, however, what is the menaing when it is applied to the * opeartor, the meaning is not that straightforward. so avoid thinking in terms of appending and just think in terms of mappend being a binary function that takes two monoid values and returns a third.

 

the last is the mconcat, it takes a list of monoids value and reduces them to a single value by doing mappend between the list's emement. and it has a default implementaion, so you shouldn't worry to provide an implement .  which just takes mempty as a starting value and folds the list from the right with mappend. However, if you have some more effecient way to implement the mconcat, you are more than welcome to  provide one. 

 

As always, we willlook at what are the ruels on Monoids, you can certainly make a instances of monoid which does not follow this rules, but what is the point? so make sure you follow the followings. 

• mempty `mappend` x = x
• x `mappend` mempty = x
• (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

The first two state that mempty has to act as the identity with respect to mappend and the third says that mappend has to be associative i.e. that it the order in which we use mappend to reduce several monoid values into one doesn't matter. Haskell doesn't enforce these laws, so we as the programmer have to be careful that our instances do indeed obey them.

 

there are some instances that are monoids, we will introduce some of the monoid instances

 

List are monoids

 

instance Monoid [a] where  
    mempty = []  
    mappend = (++)  

 

 

you may find that the implementaion very concise and interest, '[]' is an empty list, and the operator (++) will concat two list... (contrast that to the (:) operator which will append one element to another ). YOu can run some examples to testify that .

 

Also ,you may wonder why the type of Monoid definition is [a] rarther than type []?? that is because teh Monoid will demands a concrete type, [a] is a concrete type, while [] is not. 

 

 

ghci> [1,2,3] `mappend` [4,5,6]  
[1,2,3,4,5,6]  
ghci> ("one" `mappend` "two") `mappend` "tree"  
"onetwotree"  
ghci> "one" `mappend` ("two" `mappend` "tree")  
"onetwotree"  
ghci> "one" `mappend` "two" `mappend` "tree"  
"onetwotree"  
ghci> "pang" `mappend` mempty  
"pang"  
ghci> mconcat [[1,2],[3,6],[9]]  
[1,2,3,6,9]  
ghci> mempty :: [a]  
[]  

 

 

Product and sum are monoids

 You may find it very surprising that Product and Sum are actually some data types, it is not some operation.

 

To use the internal Product and Sum, you will need to import the module called.  

 

import Data.Monoid

 

and here are the definition of the Product and the Sum operation. 

 

newtype Product a =  Product { getProduct :: a }  
    deriving (Eq, Ord, Read, Show, Bounded)  

 

and to make Product a instance of Monoid, this is required. 

instance Num a => Monoid (Product a) where  
    mempty = Product 1  
    Product x `mappend` Product y = Product (x * y)  

 

while, now let's do some test, which we will need to call getProduct on the result to get a Show instance so taht we can see from the command line. 

ghci> getProduct $ Product 3 `mappend` Product 9  
27  
ghci> getProduct $ Product 3 `mappend` mempty  

 

Any and All are monoids. 

 

the definition of Any is not something fancy .... 

newtype Any = Any { getAny :: Bool }  
    deriving (Eq, Ord, Read, Show, Bounded)  

 

now, let's see how it is made an instance of the Monoid. 

 

instance Monoid Any where  
        mempty = Any False  
        Any x `mappend` Any y = Any (x || y)  

 

and again, there are some code that helps to testify it. 

ghci> getAny $ mempty `mappend` Any True  
True  
ghci> getAny . mconcat . map Any $ [False, False, False, True]  

 

simliarily, you can find the all deifnition. 

 

newtype All = All { getAll :: Bool }  
        deriving (Eq, Ord, Read, Show, Bounded)  

 

and here is definition of the All monoid instance. 

instance Monoid All where  
        mempty = All True  
        All x `mappend` All y = All (x && y)  

 

again, we will use some code to see how it can be operated. 

ghci> getAll $ mempty `mappend` All False  
False  
ghci> getAll . mconcat . map All $ [True, True, True]  

 

Odering is also Monoid

 

Ordering is monoid?? No, you don't have a wrong ear, odering as others, satisify some trait of the Monoid. 

To see why, let's first see some odering instance.  

ghci> 1 `compare` 2  
LT  
ghci> 2 `compare` 2  
EQ  
ghci> 3 `compare` 2  
GT  

 

while if you want to make the Ordering part of hte Monoid, here is probably the code that you will every need to implement.

 

instance Monoid Ordering where  
    mempty = EQ  
    LT `mappend` _ = LT  
    EQ `mappend` y = y  
    GT `mappend` _ = GT  

 

and now since we already have the  ordering being made part of the monoid typeclass, here is what you can do to test it . 

 

ghci> LT `mappend` GT  
LT  
ghci> GT `mappend` LT  
GT  
ghci> mempty `mappend` LT  
LT  

 

So you may wonder what the use of making use of the Odering monoid, here let's make a applicable use of lengthCompare, which will compare two strings, if character at the same index is equal, we compare the next, and if one character is less/greater than the other, then the result of the comparision is the result of the comparing the character. 

 

here is the orignial code impl without the ordering monoid, 

 

lengthCompare :: String -> String -> Ordering  
lengthCompare x y = let a = length x `compare` length y   
                        b = x `compare` y  
                    in  if a == EQ then b else a  

since we have learned the monoid and we have made the ordering part of monoid, so let's reimplement it 

 

lengthCompare :: String -> String -> Ordering  
lengthCompare x y = let a = length x `compare` length y   
                        b = x `compare` y  
                    in  if a == EQ then b else a  

 

this can make it every easy to extend, suppose that we have another criteria and that we will compare the vowels in the string as the second significant factor, here is the code. 

 

import Data.Monoid  
  
lengthCompare :: String -> String -> Ordering  
lengthCompare x y = (length x `compare` length y) `mappend`  
                    (vowels x `compare` vowels y) `mappend`  
                    (x `compare` y)  
    where vowels = length . filter (`elem` "aeiou")  

 

maybe the monoid. 

Let's take the monoid to some even more bizarred types, such as the "Maybe" .. 

 

Here is what we will made of Monoid, and the code is as below. 

 

instance Monoid a => Monoid (Maybe a) where  
    mempty = Nothing  
    Nothing `mappend` m = m  
    m `mappend` Nothing = m  
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)  

 

and let's see again some code that show the code can be used. 

 

ghci> Nothing `mappend` Just "andy"  
Just "andy"  
ghci> Just LT `mappend` Nothing  
Just LT  
ghci> Just (Sum 3) `mappend` Just (Sum 4)  
Just (Sum {getSum = 7})  

 

 

First and Last. 

 

and there is one constraint, in that , the content of the Maybe must be an Monoid, but what if the they are not? one possible way out is discard the second value and kept the first one, the First a type exists and here is the definiiton. 

 

newtype First a = First { getFirst :: Maybe a }  
    deriving (Eq, Ord, Read, Show)  

 

and according to the rules we have discussed before, here is what we will do ... 

 

instance Monoid (First a) where  
    mempty = First Nothing  
    First (Just x) `mappend` _ = First (Just x)  
    First Nothing `mappend` x = x  

 

and let's test it out. 

 

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')  
Just 'a'  
ghci> getFirst $ First Nothing `mappend` First (Just 'b')  
Just 'b'  
ghci> getFirst $ First (Just 'a') `mappend` First Nothing  
Just 'a'  

 

If you are interested, that you can find such a Last type that is declared in the Data.Monoid type.. 

 

ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]  
Just 10  
ghci> getLast $ Last (Just "one") `mappend` Last (Just "two")  
Just "two"