StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h1>Intuition</h1> <p>A rough intuition would be that a Monad is a particular kind of container (<code>Functor</code>), for which you have two operations available. A wrapping operation <code>return</code> that takes a single element into a container. An operation <code>join</code> that merges a container of containers into a single container. </p> <pre><code>return :: Monad m => a -> m a join :: Monad m => m (m a) -> m a </code></pre> <p>So for the Monad Maybe you have: </p> <pre><code>return :: a -> Maybe a return x = Just x join :: Maybe (Maybe a) -> Maybe a join (Just (Just x) = Just x join (Just Nothing) = Nothing join Nothing = Nothing </code></pre> <p>Likewise for the Monad [ ] these operations are defined to be:</p> <pre><code>return :: a -> [a] return x = [x] join :: [[a]] -> [a] join xs = concat xs </code></pre> <p>The standard mathematical definition of Monad is based on these return and join operators. However in Haskell the definition of the class Monad substitutes a bind operator for join. </p> <h1>Monads in Haskell</h1> <p>In functional programming languages these special containers are typically used to denote effectful computations. The type <code>Maybe a</code> would represent a computation that may or may not succeed, and the type <code>[a]</code> a computation that is non-deterministic. Particularly we're interested in functions with effects, i.e.those with types <code>a->m b</code> for some <code>Monad m</code>. And we need to be able to compose them. This can be done using either a monadic composition or bind operator. </p> <pre><code>(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c (>>=) :: Monad m => m a -> (a -> m b) -> m b </code></pre> <p>In Haskell the latter is the standard one. Note that its type is very similar to the type of the application operator (but with flipped arguments): </p> <pre><code>(>>=) :: Monad m => m a -> (a -> m b) -> m b flip ($) :: a -> (a -> b) -> b </code></pre> <p>It takes an effectful function <code>f :: a -> m b</code> and a computation <code>mx :: m a</code> returning values of type <code>a</code>, and performs the application <code>mx >>= f</code>. So how do we do this with Monads? Containers (<code>Functors</code>) can be mapped, and in this case the result is a computation within a computation which can then be flattened: </p> <pre><code>fmap f mx :: m (m b) join (fmap f mx) :: m b </code></pre> <p>So we have: </p> <pre><code>(mx >>= f) = join (fmap f mx) :: m b </code></pre> <p>To see this working in practise consider a simple example with lists (non-deterministic functions). Suppose you have a list of possible results <code>mx = [1,2,3]</code> and a non-deterministic function <code>f x = [x-1, x*2]</code>. To calculate <code>mx >>= f</code> you begin by mapping mx with f and then you merge the results::</p> <pre><code>fmap f mx = [[0,2],[1,4],[2,6]] join [[0,2],[1,4],[2,6]] = [0,2,1,4,2,6] </code></pre> <p>Since in Haskell the bind operator <code>(>>=)</code> is more important than <code>join</code>, for efficiency reasons in the latter is defined from the former and not the other way around. </p> <pre><code>join mx = mx >>= id </code></pre> <p>Also the bind operator, being defined with join and fmap, can also be used to define a mapping operation. For this reason Monads are not required to be instances of the class Functor. The equivalent operation to fmap is called <code>liftM</code> in the Monad library.</p> <pre><code>liftM f mx = mx >>= \x-> return (f x) </code></pre> <p>So the actual definitions for the Monads Maybe becomes:</p> <pre><code>return :: a -> Maybe a return x = Just x (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Nothing >>= f = Nothing Just x >>= f = f x </code></pre> <p>And for the Monad [ ]:</p> <pre><code>return :: a -> [a] return x = [x] (>>=) :: [a] -> (a -> [b]) -> [b] xs >>= f = concat (map f xs) = concatMap f xs -- same as above but more efficient </code></pre> <p>When designing your own Monads you may find it easier to, instead of trying to directly define <code>(>>=)</code>, split the problem in parts and figure out what how to map and join your structures. Having map and join can also be useful to verify that your Monad is well defined, in the sense that it satisfy the required laws. </p> <h1>Monad Laws</h1> <p>Your Monad should be a Functor, so the mapping operation should satisfy:</p> <pre><code>fmap id = id fmap g . fmap f = fmap (g . f) </code></pre> <p>The laws for return and join are: </p> <pre><code>join . return = id join . fmap return = id join . join = join . fmap join </code></pre> <p>The first two laws specify that merging undoes wrapping. If you wrap a container in another one, join gives you back the original. If you map the contents of a container with a wrapping operation, join again gives you back what you initially had. The last law is the associativity of join. If you have three layers of containers you get the same result by merging from the inside or the outside. </p> <p>Again you can work with bind instead of join and fmap. You get fewer but (arguably) more complicated laws:</p> <pre><code>return a >>= f = f a m >>= return = m (m >>= f) >>= g = m >>= (\x -> f x >>= g) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload