From Chen's Wiki

Jump to: navigation, search

Contents

Why this tutorial

It is true that there are bunch of tutorials online about monads, however, mainly in Haskell. I bet if you understand these Haskell things, you should be already someone knows about it. It is also true that there are ones in Scala or Python, however, just purging you to the functional world and showed you what are monads in these languages. I had to do it the hard way, reading a Haskell book. What I derived from that is you have to know about other things before you encounter monads.


Functors

The question

In programming, the use of functors answers this question:

Suppose we have a function g which takes a parameter A and returns B, how would you feed the f with the A under some context and get the B under the context?

Defination in Haskell

In Haskell, Functor is a typeclass where typeclass defines some common behaviours within that class of types.

fmap :: (a -> b) -> f a -> f b

Don't panic! It is quite simple. If you know a bit of some higher level language like Python, it is easier to see that map() is the use of functor.

map(int, [1.0, 2.0])

Recall my explanation at the start of the section, let's go through it:

  • int is the g
  • here, int take a single float and returns an int
  • Now, there is context added. The input designated for int is wrapped into the context list and returns the result under the context.
  • With the help of map(), int knows what to do when feeded with a list of something.

Python example

According to my understanding to it, I consider the following code roughly doing the same things that using a list or a number as functors.

def fmap(f, a):
        if isinstance(a, list):
                return [f(x) for x in a]
        else:
                return f(a)

print fmap(int, [1.0, 2.0])                        #[1, 2]
print fmap(int, 1.0)                                 #1

Applicative Functors

The question

How do I feed a function which has already been wrapped in the context with a value in the context and yield a value under that context

Using a Python list example, this question equals to: How to apply [int] on [1.0, 2.0]?

Clever boys, what we need to do is to extract the useful function out.

Defination in Haskell

class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b 

Here, what pure does is just taking a value of type a and put it in a context where f is a type constructor. For example, [] is a type constructor. If you put 1 in [], you will get 1 in the list context: [1].

According to my understanding, pure is just to make the applicative functor actions chainable. It is the (<*>) doing the job.

Python example

Still giving a list example:

def pure(x):
        return [x]

def applicative(f, val):
        if len(f) == 0: return []
        else:
                return [f[0](v) for v in val]

print applicative(pure(int), [1.0, 2.0])

Monad

The question

Evantually here it comes!

How do you feed a function which take a normal value and return a value under context with a value under context?

Defination in Haskell

We want this:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b  

Formally, the whole thing is:

class Monad m where  
        return :: a -> m a  
      
        (>>=) :: m a -> (a -> m b) -> m b  
      
        (>>) :: m a -> m b -> m b  
        x >> y = x >>= \_ -> y  
      
        fail :: String -> m a  
        fail msg = error msg  

However, we just need to focus on the >>= which reads bind and the return.

return does nothing with the imperative return in Python. You can see that it just does the same thing as pure.

Python example

def unit(x):                    #the "return"
        return [x]

def bind(x, f):                #the ">>="
        return flatten(map(f, x))

def flatten(xs):
        return [x for sub in xs for x in sub]

print bind([1, 2], lambda x: unit(x+1))
print bind([1, 2], lambda x:
          bind([1, 2], lambda y: unit((x, y))))

#[2, 3]
#[(1, 1), (1, 2), (2, 1), (2, 2)]

It is actually straightforward. The only tricky part here for a list monad is that a use of flatten. This makes the return value still the same with the original function.

Things making it ugly are

  1. It is hard to make a infix ">>=" operator in Python
  2. Python does not support currying by default so we have to use a chain of lambdas.

Lots of Monads

As we can see, the definition for monads is quite intuitive: adopt some value under some context. So when we talk about list monad, writer monad, etc, we can tell these are the implemented instances of the monad concept under some certain context. They might be hard to understand not because of the monads (especially after this tutorial~) but their context.

According to my understanding, functional languages need monads (or functors, etc.) because they want to be pure and pure means not being tainted with the environment, e.g. the context. When there is some stateful computation, e.g. generating numbers, you need the environment to provide some seed. Thus, a state monad will always yield a new environment state to you then the purity of the generator can be assured.

Comments


Add your Comment
Chen's Wiki welcomes all comments. If you don't want to be anonymous, register or log in. It's free.