Monad Tutorial?

Making a Monad

We're going to make a monad called Result. First, define it as a type. This definition makes it essentially an enum which is generic over two types. It can either be Success containing a value of the first type, or Error containing a value of the second type.

data Result a e
  = Success a
  | Error e

resultOne :: Result Int String
resultOne = Success 4
resultTwo :: Result Int String
resultTwo = Error "Can't divide by zero."

As of now, Result is not a monad. To make it a monad, we need to implement the function bind, or >>= in Haskell's notation. We also define the function return, which is used in the definition of the monad laws, as being equivalent to the Success function. The types and definitions of these methods are:

(>>=) :: Result a e -> (a -> Result a e) -> Result a e
return :: a -> Result a e

instance Monad (Result a e) where
  (Success x) >>= f = f x
  err@(Error _) >>= _ = err
  return = Success

The Monad Laws

First Monad Law

The first monad law is:

(return x) >>= f  =  f x

Essentially, the first monad law states that bind is defined as going "inside" of a monad to apply a function on the value within. For example:

x :: Result Int String
x = Success 42

y :: Result Int String
y = Success -12

z :: Result Int String
z = Error "The cake is a lie!"

-- f returns an error for negative numbers or zero, and halves positives.
f :: Int -> Result Int String
f x | x > 0     = Success (x / 2)
    | otherwise = Error "x is negative!"

assert (x >>= f == Success 21)
assert (y >>= f == Error "x is negative!")
assert (z >>= f == Error "The cake is a lie!")

Second Monad Law

The second monad law is:

m >>= return  =  m

This states that applying the return function to a value inside the monad should be a no-op, that is, it should result in the same monad. This is true for our Result monad:

foo :: Result Int String
foo = Success 42

assert (foo >>= return == foo)

Expanding this out:

foo >>= return
-- foo = Success 42
Success 42 >>= return
-- (Success x) >>= f = f x
return 42
-- return = Success
Success 42
-- foo = Success 42
foo

The same holds for an Error:

bar :: Result Int String
bar = Error "rab"

assert (bar >>= return == bar)

bar >>= return
-- bar = Error "rab"
Error "rab" >>= return
-- err@(Error _) >>= _ = err
Error "rab"
-- bar = Error "rab"
bar

Third Monad Law

The third and final monad law is:

f x = g x >>= h
m >>= f = (m >>= g) >>= h

This is known as the law of composition, and establishes an order of evaluation for monadic expressions. An example of this law's usefulness would be in:

doubleIfPositive :: Int -> Result Int String
doubleIfPositive | x > 0     = Success (x * 2)
                 | otherwise = Error "x is negative!"

tripleIfEven :: Int -> Result Int String
tripleIfEven | x % 2 == 0 = Success (x * 3)
             | otherwise = Error "x is odd!"

quux :: Int -> Result Int String
quux x = doubleIfPositive x >>= tripleIfEven

xyzzy :: Result Int String
xyzzy = (Success -5) >>= quux

After this is run, should xyzzy be Error "x is negative!" or Error "x is odd!"? By the monad laws:

(Success -5) >>= quux
-- (Success x) >>= f = f x
quux -5
-- quux x = doubleIfPositive x >>= tripleIfEven
doubleIfPositive -5 >>= tripleIfEven
-- doubleIfPositive | otherwise = Error "x is negative!"
Error "x is negative!" >>= tripleIfEven
-- err@(Error _) >>= _ = err
Error "x is negative!"

Summary

Yeah, that's all a monad is! In real Haskell, Result already exists -- it's called Either, and has a pretty similar definition, except Success is named Right and Error is named Left. Other useful monads in Haskell include:

`IO`

IO is the most (in?)famous monad in Haskell. It holds as internal state any and all IO performed by a function.

TODO EXAMPLE

Lists

Lists are implemented as a monad. Although this sounds weird, the analogy fits:

l :: [Int]
l = [1, 2, 3]

f :: Int -> [Int]
f x = [x * 2, x]

assert (l >>= f     == [2, 1, 4, 2, 6, 3])
assert (flatMap l f == [2, 1, 4, 2, 6, 3])
-- NB: flatMap doesn't actually exist -- it's called (>>=)! Also, by Haskell
-- tradition, its arguments' order would be the opposite, which makes functional
-- programming easier to express (i.e., require fewer lambdas).

-- This makes sense, because:
(>>=)   :: [a] -> (a -> [a]) -> [a]
flatMap :: [a] -> (a -> [a]) -> [a]

-- Also,
return x = [x]
-- because
flatMap [2, 4, 6] (\x -> [x]) == [2, 4, 6]
-- which reduces to
[2, 4, 6] >>= return = [2, 4, 6]
-- which is the second monad law!

`Maybe`

Maybe is defined simply as data Maybe a = Just a | Nothing. See if you can write an implementation for its bind and return methods.

data Maybe a
  = Just a
  | Nothing

instance Monad (Maybe a) where
  (Just x) >>= f = ???
  Nothing >>= f = ???
  return x = ???

remexre/monads.md