Linux, kernel, OS, GPU, CUDA, virtualization, heterogeneity, anything system. Proud longhorn


Monads in Haskell

I've scratched my head for quite a while trying to understand the concept of monad in Haskell. This is a brief summary of monads. I take William Cook's Anatomy of Programming Languages as my reference.

Definitions of Monads

A monad is defined as a computational structure that involves three parts:

  • A generic data type \(m\)
  • A return function \(return_m\) :: \(t\rightarrow mt\)
  • A bind function \(\triangleright_mt\rightarrow (t\rightarrow ms)\rightarrow ms\)

Here the symbol \(m\) gives the name of the monad as well as the shape of the computation. We can call the program that uses the monad \(m\) as an m-computation. The instantiation of the generic type \(mt\) at a particular type \(t\) represents n m-computation that produces a value of type \(t\). The \(m\)-computation indicates that in addition to value \(t\), some additional requirements or effects will take place. This is the essence of monads.

The definition of the return function states that how values are converted into m-computations. The return will just return the value of type \(t\). For example, if we pass in a stateful memory information, return shouldn't modify the actual but only provide a context to which the value lies in. The reason we convert value into m-computation is that if any error occur then return will catch the error without adding additional error checking codes.

The bind function \(\triangleright_m\) specifies how computations are combined together. THe general idea is that the computation behavior of \(A\triangleright_m F\) indicates the m-computation \(A\) is performed first, the value it produces wil be passed to the function \(F\) to create a second m-computation. Because \(A\) is a m-computation, if an error happens, the computation will stop and \(F\) will not be performed.

Monads in Haskell

In Haskell, we can use Monads using type class. A type class is defined as:

class Monad m where
  (>>=) :: m t -> (t -> m s) -> m s
  return :: t -> m t

For a object of generic type \(m\) to be a Monad, it must have those two functions defined. A type class allows us to overload functions according to their type.

So why do we need Monads in the first place? If we are given a function \(func1\) which takes in an Int value and produces an Int output, we could link the function together to form a chain of computation. If we make a function like this:

func1 :: Int -> (Int, Int) -> (Int, Int) 
x & func1 = func1 x

we could use the output of the function as the input to the same function to produce another value. This process can be repeated and thus form a chain of operation:

(0, 0) & func1 1 & func1 2 & func1 3 ...

However, the function \(func1\) could potentially return a Nothing if the given input doesn't meet certain standards (exp. devide by 0). Therefore, \(func1\) can modified to:

func1 :: Int -> (Int, Int) -> Maybe (Int, Int)

The previous definition of \(func1\) says \(func1\) takes a (Int, Int) tuple as one input, but now if we feed the output of \(func1\) directly to the next \(func1\) in the chain, error would occur because \(func1\) takes a raw (Int, Int) tuple as the input, but now we have (Int, Int) wrapped in a Maybe context. The & operator is not able to pass the argument with a context to the next func1. Fortunately, we have the bind operator defined.

If we look at the definition of the »= in Monad definition, we see:

(>>=) :: m t -> (t -> m s) -> m s

This means »= is able to take a value within certain context and map a function that takes the raw value as input to the it. We can simply switch the & operator to »= such that the chaining would still work:

return (0, 0) >>= func1 1 >>= func1 2 >>= func1 3 ...

If an error occurred in one part of the chain (let's assume one computation yields Nothing). Then the Nothing value will be propagated to the next function, whill will automatically generate an error, or Nothing. Otherwise we would have written error checking code at the end of each single computation to check their output.

In short, »= is just a way to chain functions with parametric polymorphism together.

Haskell do Notation

Using the do notation can simply the use of bind operator. The basic pattern of do notation is:

  x <- e1

which is equivalent to:

e1 >>= (\lambda x.e2)

The <- notation simply indicates \(x\) is bind to the value the computation generates. In other words, \(x\) doesn't lie in a context. if \(e1\) returns Nothing, \(x\) is not bind to anything. It's important to remember that do expressions are just different syntax for chaining monadic values.

For a more detailed explaination of Monads, I found A Fistful of Monads to be extremely helpful in terms of clarifying the concept.