This kata corresponds to Five-Fundamental-Monads in Codewars
Difficulty: 4 kyu
Tags: FUNDAMENTALS MONADS DATA STRUCTURES FUNCTIONAL PROGRAMMING

Questions

In this kata we will implement five of the most fundamental monads.

Newcomers to Haskell find monads to be one of the most intimidating concepts but on a basic level - they are not too difficult to understand.

A datatype forms a monad if it is possible to complete the following definitions such that the monad laws (described below) hold. There’s nothing more to it! For a more intuitive understanding then there are a plethora of tutorials which use (sometimes wild) analogies to explain this concept.

1
2
3
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

Monad laws

1
2
3
return x >>= f = f x
m >>= return = m
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

It turns out that many different types of computation can be encapsulated by monads. For example the Maybe monad encapsulates a computation which can fail and State a computation with mutable state.

The five we will implement here are Identity, Maybe, State, Writer and Reader.

Hint: https://www.haskell.org/haskellwiki/Monad_tutorials_timeline

Note: Please feel free to contribute!

Sources Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
{-# LANGUAGE NoImplicitPrelude #-}
module Monads where

import Prelude hiding (Monad, Identity, Maybe(..), State, Reader, Writer)
import Data.Monoid

class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

data Identity a = Identity a
deriving (Show, Eq)

data Maybe a = Nothing | Just a
deriving (Show, Eq)

data State s a = State {runState :: s -> (a, s)}

data Reader s a = Reader {runReader :: s -> a }

data Writer w a = Writer {runWriter :: (w, a)}

instance Monad Identity where
return = undefined
(Identity v) >>= f = undefined

instance Monad Maybe where
return = undefined
Nothing >>= f = undefined
(Just v) >>= f = undefined

instance Monad (State s) where
return = undefined
(State g) >>= f = undefined

instance Monad (Reader s) where
return = undefined
(Reader g) >>= f = undefined

instance Monoid w => Monad (Writer w) where
return = undefined
(Writer (s, v)) >>= f = undefined

How to solve

Identity Monad

Above all, we need to implement the Identity monad instance at first, according to the law of identity in Category Theory: which means for every object $x$, there exists a morphism $id_x : x \mapsto x$ called the identity morphism for $x$, such that for every morphism $f : a \mapsto x$ and every morphism $g : x \mapsto b$, we have $id_x \circ f = f$ and $g \circ id_x = g$. Straightforwardly we can call this as a morphism (or function in a programming language) which always return itself, and for every morphism combine with any identity must be equals to morphism itself anyway.

By looking at Monad typeclass defination:

1
2
3
4
5
6
7
class Applicative m => Monad (m :: * -> *) where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
{-# MINIMAL (>>=) #-}
-- Defined in ‘GHC.Base’

So, in Haskell we can implement identity instance like this:

1
2
3
instance Monad Identity where
return = Identity
(Identity v) >>= f = f v

return function was return a Identity which accepted a parameter a implicitly, and as explicitly can be write like this: return a = Identity a

>>= is a monad-binding operator function, means that (Identity v) was bound on function f, by looking at type definition of this function, which accept the parameter m a, (a -> m b) and return the monad m b finally. So now let’s turn back to this instance, (Identity v) is the first parameter m a also f represents to (a -> m b), after the (Identity v) is done the pattern-matching, by take the parameter v out and put it into f and finally return the monad m b, that’s it what we need!

Maybe Monad

After done the identity monad, we are learned about how to construct the simple monad in Haskell, but just the only identity? Not enough! So now I’ll start to talk about the next most useful monad in Haskell, the Maybe Monad.

In this monad, defined two data types: Nothing and Just a, which Nothing does not accept any type parameter but Just a will accept a type parameter a here. So when we hold something just like an integer 1, they we can put it into Just 1, but when holding nothing, then we didn’t need to put anything into Just a, so we use Nothing to alternative that.

So let’s implement return function on Maybe Monad first, it seems like the identity monad, but still have some differences. In this case, we need to specify the Nothing and Just, just take a look at the type definition of return function, it’s must provide a parameter a, then we can be wrapping it into Just a to becomes return = Just in instance.

Second, after completed return function, to finish the >>= function, it’s also closed to the identity instance, but we know when we put a Nothing into f, there must always return Nothing, otherwise return the result moand from f, so here could be using pattern-matching to partition these two case.

Finally the Maybe Monad likes:

1
2
3
4
instance Monad Maybe where
return = Just
Nothing >>= f = Nothing
(Just v) >>= f = f v

State Monad

Reader Monad

Writer Monad

Conclusion

Great thanks to Henry for fixing my noob English grammar problem!