This is an old revision of the document!


MonadPlus

Haskell class

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

Discussion

Postulates

Right unit, left unit and associativity:

m »= return $\ \leftrightsquigarrow\ $ m
return x »= f $\ \leftrightsquigarrow\ $ f x
(m »= f) »= g $\ \leftrightsquigarrow\ $ m »= (\x → f x »= g)
In reference to Counit-unit adjunction:

“F(f)” the progrmaming way: If fmap is the function mapping for a functor “F” for which we define >==, note that “(fmap f) mx” will be written as “mx »= return . f”. But »= is a strong gadget, in that, of course, its second argument doesn't have to be of the form “return 'some function'”.

In Haskell, functions of several variables are implemented using lambda expressions and currying - here's how this interacts with >==: First note that the above is the same as “mx »= \x→(return (f x))”. If f is a function of two arguments x,y, then for arguments mx,my, the “lifted” function is “mx »= \x→(my »=\y →(return (f x y)))”. Syntactic sugar: Changing the symbols in between this expression gives Haskells do-noation “do {x ← mx; y ← my; return (f x y)}”.

liftM2 f mx my = mx »= \x→(my »= \y →(return (f x y)))
liftM2 f mg my = mg »= \g→(my »= \y →(return (f g y)))
liftM2 id mg my = mg »= \g→(my »= \y →(return (g y)))
<*> mg my = mg »= \g→(my »= \y →(return (g y)))

Let $n\in\{0,1\}$. Among other things, given a function of type $a\to m^n\ b$, a monad enables you to get a function of type $m\ a\to m\ b$.
Consider a function space $A=a\to b$ and fix a term $p : m\ a$. Construct the higher order function $G:A\to m\ b$, which takes any function $g:A$ (for which $n=0$) and, using the monad, applies it to $p$. Next use the monad a second time, now on $G$ (which has $n=1$), to get a function from $m\ A$ to $m\ b$. Lambda abstraction over $p$ and flipping the arguments gives a function $<*> : m\ (a\to b)\to m\ a\to m\ b$. In this way, we've successfully lifted the apply function.
Given 'return', then 'join' (or '»=') induces '<*>'. The converse isn't true and so the Applicative concept lies between Functor and Monad.

Abstraction over $ma$ and flipping arguments gives a map $<*> : m (a->b)$

Monads sometimes have a “zero element” of monadic, acting like the multiplicative zero for bind. “Nothing” and the empty list “[]” are examples. Haskells list comprehension works by returning the empty list for elements x where a predicate returns false.

Associated methods

todo

Reference

Parents

Subset of

Link to graph
Log In
Improvements of the human condition