monad

We can abstract common part of language features such as state and exception. It allows programming these features in pure lambda calculus.
A monad M a is an abstract type—
the “normal” type is a, and we have the semantics hidden in M.
return: a \to Ma bind: M a \to (a \to M b) \to M b — it takes a monad, a function that takes the unwrapped thing and hands back a new monad, and returns that bind is written with v \gg = f for monad v and function f: a\to M b
discussion Monads were used to explain stuff like state within Church theories; so languages are “core functional parts with monadic exceptions”—there’s a set of monads which is built in, like state, exceptions, concurrencies, ec.
upsides “just programming”: users can write their own monads fairly ubiquitous in haskall downsides programs using return and bind tends to be contagious performance is bad: no free lunch stuff ends up looking like C++ state monad return: a -> Ma = \lambda v. \lambda s . (v,s) (just give us the state transformer) p >>= f: Ma -> (a -> Mb) -> Mb = \lambda s . let (v, s’) = (p\ s)\ \text{in}\ f\ v\ s’ “run p first against some state, get new state s’ and resulting value, then apply this value to f, and then run it on the new state; notice that this whole thing takes a state”
exceptions Exceptional e a = Success a | Exception e the monad:
monad M = Exceptional e return := Success bind:
>>= :: M a -> (a -> M b) -> M b v >>= f = case v of Exception I -> Exception I Success r -> f r throw:
throw = Exception catch:
catch e h = case e of Exception I -> h I Success r -> Success r partial functions Maybe(a), that is Option
head: List(a) -> Maybe(a) div: int -> int -> Maybe(int) because these things may fail r not exist.
Maybe a = Just a | Nothing Composition:
lx.let y = f x in case y of Nothing: Nothing Just v: g(v) Notice how the above is tedious. We will then make this a monad.
monad M = Maybe return: Just
bind
with v: Ma, f: a \to Mb
v >>= f = case v of Nothing -> Nothing Just x -> f x which means that we can write the above function:
lx.x >>= f >>= g head of list head x = case x of Nil: Nothing Cons(a,as): Just(a) taking the head of the head of the list
λ l. return l >>= head >>= head