Haskell: Monoids
(Edited: 7052021)
Monoids
Coming from the world of algebra, a monoid is a :
 semigroup with an identity, which is a:
 magma with associativity, which is a:
 closed set, with a binary operation which is closed under it
 magma with associativity, which is a:
So what?
Well believe it or not, Haskell defines a Monoid as a Typeclass
, that lets you
do funky stuff. Great!
Let’s have a go and demonstrate these funky useful stuff.
Use case
Say we have a parser that takes a list or stream of numbers and checks if any of them are any of the following:
1) odd
2) divisible by 4
3) divisible by 6
… (you can carry on imagining adding rules here)
First Solution
The first solution would be pretty straight forward:
s1 = [2,4,5,7,5,3]  this one checks
s2 = [1,1,1,1,1,1]  this one doesn't
check :: [Int] > Bool
check [] = False
check (x:xs) = odd x  x `mod` 4 == 0  x 'mod 6 == 0  check xs
That’s all nice and tidy, but say you wanted to add another test  it can be a
bit annoying to chain another  test x
to the previous expression. So what
else can we do?
Second Solution
Well, we can make an observation that all the functions:
1) are of the type Int > Bool
,
2) we have a list of [Int]
,
3) our type is check :: [Int] > Bool
.
So in essence we need a way to take a list of [Int>Bool]
tests, and map them
to [Int]
. Then we flatten the list, and repeat until we get to the end of the
list of [Int]
or we get True
after we flatten.
check' :: [Int] > Bool
check' [] = False
check' (x:xs) = foldl1 () ( map ($x) tests)  check' xs
where
tests = [ t1, t2, t3 ]
t1 = odd
t2 = \x > x `mod` 4 == 0
t3 = \x > x `mod` 6 == 0
And realistically, even this form, if we look at the recursivity of check'
we can
improve by observing that check'
is very much a map
.
check'' :: [Int] > Bool
check'' = foldr1 () . map (\x > foldl1 () ( map ($x) tests))
where
tests = [ t1, t2, t3 ]
t1 = odd
t2 = \x > x `mod` 4 == 0
t3 = \x > x `mod` 6 == 0
Ok, I know what you are thinking, that might not be the nicest section ever, but
Haskell allows us to make it nicer by taking that aux
function and declaring it
as such:
check'' :: [Int] > Bool
check'' = foldr1 () . map aux
where
aux x = foldl1 () (map ($x) tests)
tests = [ t1, t2, t3 ]
t1 = odd
t2 = \x > x `mod` 4 == 0
t3 = \x > x `mod` 6 == 0
Option 3
Ok so we’ve done it in a more flexible way, but where does the Monoid come
into play. Well if we remember the properties from the introduction and we have
a look in ghci at the :info Monoid
we find out a few things. From Semigroup
typeclass
we get:

We have a function
mappend
that has the type signatureSemigroup a => a > a > a
. So what this does is takes two elements, applies the monoids operation and returns the result. 
We have this other function
mconcat
with the signatureSemigroup a => [a] > a
. This one takes a list of elements and flattens it with the binary operation. 
We find out that
[a]
(so any list) is amonoid
. 
We find out about the existence of
All
andAny
twoMonoids
. When we look at theirinfo: All
andinfo: Any
we find out that they are anewtype Any = Any {getAny :: Bool}
. Nice!
So let’s try and get these to work for us.
Let’s start by defining our tests as higher order monoids first:
newtype Tester a = Tester {getTest :: a > Any}
instance Semigroup (Tester a) where
f1 <> f2 = Tester $ \x > (getTest f1) x <> (getTest f2) x
instance Monoid (Tester a) where
mempty = Tester (\x > Any False)
Awesome, the type checks (that’s a good hint that the rules might be good) and
we can also see that the Monoid laws hold(left as an exercise for the
reader). Also by using the Monoid Any
in the type signature we know we can
further flatten it. So our function now becomes a lot clearer/cleaner, and
nicer:
check''' :: [Int] > Bool
check''' = getAny . mconcat . map aTests
where
aTests = mconcat $ map (getTest . Tester) lstT
lstT :: [(Int > Any)]
lstT = [t1,t2,t3]
t1 = \x > Any $ odd x
t2 = \x > Any $ x `mod` 4 == 0
t3 = \x > Any $ x `mod` 6 == 0
And now let’s transform those tests into sections, as they read nicer:
check'''' :: [Int] > Bool
check'''' = getAny . mconcat . map aTests
where
aTests = mconcat $ map (getTest . Tester) lstT
lstT :: [(Int > Any)]
lstT = [t1,t2,t3]
t1 = Any . odd
t2 = Any . (==0) . flip mod 4
t3 = Any . (==0) . flip mod 6
And as suggested here
(thank you for the suggestions) we can further neaten it up by using the infix
notation for mod
together with partial application:
check :: [Int] > Bool
check = getAny . mconcat . map aTests
where
aTests = mconcat $ map (getTest . Tester) lstT
lstT :: [(Int > Any)]
lstT = [t1,t2,t3]
t1 = Any . odd
t2 = Any . (==0) . (`mod` 4)
t3 = Any . (==0) . (`mod` 6)
We can extend this type of manipulation to most monoids, and internalising the rules and general capabilities can lead to pretty awesome solutions, and applications.
Further Reading
Roger out!