Monads

a summary of Don't fear the Monads by brian beckman

1 general introduction
2 functional programming
3 functions
4 monoids
5 functions again
6 monads

1 general introduction

Haskell, but also e.g. LINQ

based on category theory; not required for understanding

2 functional programming

programming with functions

first class

function: takes input, returns something

functions are not special, they are data too (table lookup)

pure = no mutable state
- Monads can simulate shared mutable state.

3 functions

types =~ mathematical sets (ℝ, ℂ, ℕ, ℙ, ℚ, ℤ)

x: int
f: int -> int (particular type)
f: a -> a (any type = generic types)
g: a -> a

Combining f and g
```
f(g(a)) or g(f(a))
```

function application =~ method call

f(ga)     -- (g first, f later; left associative -> brackets)
(f . g) a -- new function
(f . g) a == f(ga)

4 monoids

taking two things of one type (function) and creating a new one of the same type
```
(f . g) == h: a -> a
```

composition: create complexity from simplicity; types need to line up

monoid: collection of things and a rule for combining them; the rule obeys some rules
- example: clock
  rule: (x + y) % 12, e.g. 7 + 10 = 5

rules for the rule
- x + y + z = (x + y) + z (associativity)
- x + special_member = x and special_member + 12 = x (unit element aka "zero")

5 functions again

functions under composition form a monoid (same type; otherwise monoidal category)

associativity

(f . g) . h = f . (g . h)
f(g(ha)) = f(g(ha))

unit: special function 'id'
```
(f . id) = f(id a) = f(a)
```

6 monads

almost the same as a monoid
Ma = type constructur
```
f: a -> Ma
g: a -> Ma
h: a -> Ma
```

functions that take an a and return some extra data applied to an a
\ = lambda

\a -> | (fa)  >>=   \a -> (ga) |
      |  Ma   bind   a ->  Ma  |
      |_                      _|

when you create a monad, you have to implement bind (same rules as monoid)
```
return: a -> Ma (unit)

g: a -> M b
f: b -> M c
```

how to do it with monoids?

g: a -> b
f: b -> c

(f . g) : a -> c <=> (g . g)a = f(ga)
--
\a -> (ga) >>= \b -> (fb)
a ------------------> Ma

bind: Mb -> (b -> Mc) -> Mc

Monads are a theory for interacting things.

Maybe monad
taken from (source)

-- Here's the data type, it's either nothing, or "Just" a value
-- this is in the standard library
data Maybe a = Nothing | Just a

f :: (Maybe Integer) -> Integer
f Nothing = 0
f (Just x) = x + 2

instance Monad Maybe where
  -- The bind operator for Nothing
  (>>=) :: Maybe a -> (a -> Maybe b) -> (Maybe b)
  Nothing >>= f = Nothing
  -- The bind operator for Just x
  Just x >>= f = f x

  -- the "unit", called "return"
  return = Just

-- The sample code using the lambda syntax
-- that Brian showed
z = f >>= ( \fval ->
    g >>= ( \gval ->
    h >>= ( \hval -> return (fval+gval+hval ) ) ) )

-- The following is exactly the same as the three lines above
z2 :: (Integral a, Monad m) => m a
z2 = do
   fval <- f
   gval <- g
   hval <- h
   return (fval+gval+hval)

main :: IO ()
main = do
  (readLn :: IO Integer) >>= (\x ->
  putStrLn ("You have entered the number " ++ show x))

data State s a = State (\s -> (s,a))

instance Monad (State s) where
  State m >>= f = \s -> let (s',x) = m s in (f x) s'
  return x = \s -> (s,x)

put :: s -> State s ()
put s = \_ -> (s,())

get :: Sate s s
get = \s -> (s,s)

runState :: s -> State s a -> a
runState s m = m s

test z = do
  x <- get
  put (x+1)
  return (z, x+1)

test2 = do
  a <- test "hi"
  b <- test 42
  c <- test 'c'
  return (a,b,c)

runState 0 test2  -- (("hi",1),(42,2),('c',3))

readLn :: IO a
show :: a -> String
putStrLn :: String -> IO ()