My Take on Monads

Monads

    Yes, monads. Don't go running off yet! I haven't even gotten started! Before you go, I'd at least like to give you my explanation about monads, and several uses of them. So bear with me.

Theoretical Explanation (and Option Monad)

    A Monadic Type is basically any type that has two operations that can be performed on it: bind and make. In a Haskell-like syntax, a monad would be defined as:

  class Monad m =

    make : 'a -> m 'a

    bind : m 'a -> ('a -> m 'b) -> m 'b

In this type class, the type m is the monadic type, and make and bind are the monadic operations. Notice how m must be a generic type, and is eventually constructed by both of the operations. make basically creates a "container" value from a regular old value, and bind takes a container value, removes the value, and creates another container value from that removed value. (I say "container value" to make things simpler). An example of a class instance that allows one to describe failure of computation is an Option monad:

  type Option 'T = Some('T) | None

  instance Monad Option =

    let make val = Some(val)

    let bind maybe cont = match maybe

    | Some(val) -> cont(val)

    | None      -> None

Notice how make takes any old value and returns an Option value from it; this is the "container value". bind takes a container value and a continuation function and then checks whether the container value actually has a value in it; if it does, that contained value is passed to the computation continuation; if it does not, then the entire computation simply fails by returning None.

    bind, as an Option monadic operation, acts as a success/failure mechanism; if the previous operation succeeded, then the value is passed on to the continuation, but if the operation failed (returned None), then bind returns None as well, to pass on the failure.

Example of Use

    A way to use this Option monad would be like this:

  let fail = None

  decl failIfBig : int -> Option int

  let failIfBig n = if n > 1000 then fail

                    else make n

  let sumIfBothSmall x y =

    bind (failIfBig x) (func new_x ->

      bind (failIfBig y) (func new_y ->

        make(new_x + new_y)))

This example shows a failIfBig function; it returns None, meaning failure, if the input is too large. Otherwise, it calls the make function to create a container Option value. The sumIfBothSmall function uses the monadic operation bind, which transmits any failure to the rest of the computation. Once there is failure, there will always be failure (None).

   The sumIfBothSmall function might make a little more sense when written in a different way:

  let sumIfBothSmall x y =

    failIfBig x |> bind (func new_x ->

    failIfBig y |> bind (func new_y ->

    make(new_x + new_y)))

Or how about like this:

  let sumIfBothSmall = do

  {
    let! new_x = failIfBig x

    let! new_y = failIfBig y

    return new_x + new_y
  }

The do { ... } syntax there is basically syntax sugar for the previous code. let! var = val in cont transforms into bind val (func var -> cont), and return val transforms into make val. Functional languages that use monads will usually desugar the nice-looking syntax into a series of makes, returns, and continuations.

    So when you look at the nice syntax, think about what is going on in the background, and then it will make more sense (hopefully). 

Another Monad 

    Another monad is the List monad. If you define lists as

  type List 'T = Link('T, List 'T) | End

and define several helper functions as

  decl singleton : 'T -> List 'T

  let singleton x = Link(x, End)

  decl append : List 'T -> List 'T -> List 'T

  let append list appendage = match list

  | End -> appendage

  | Link(head, tail) -> Link(head, append tail appendage)

  decl concat : List (List 'T) -> List 'T

  let concat lists = match lists

  | End -> End

  | Link(list, rest) -> append list (concat rest)

  

  decl map : ('T -> 'U) -> List 'T -> List 'U

  let map transform list = match list

  | End -> End

  | Link(head, rest) -> Link(transform head, rest)

  

... then you can define the List monad as:

  instance Monad List =

    let make x = singleton x

    decl bind : List 'a -> ('a -> List 'b) -> List 'b

    let bind list projection = list |> map projection |> concat

  let none = End
To make things easier, let us assume that there is a list syntax:
  [a, b, c] -->> Link(a, Link(b, Link(c, End)))

The List monad basically allows you to use functions that return lists, and then pass each return value to another function, and then flatten the resulting list, and then pass each of those values to another function and on it goes. It makes it easier to deal with functions that can return multiple results, in list form. An example of this monad's use is:
  let product listX listY = do
  {
    let! x = listX
    let! y = listY
    return (x, y)
  }
  let list1 = ["a", "b", "c"]
  let list2 = ["x", "y", "z"]
  let listProduct = product list1 list2
  # listProduct = ["ax", "ay", "az", "bx", "by", ...]

And Another Monad... 

    Another example is the Log monad. It can be used to keep track of debugging information, for example, or maintain a log string, threaded through a computation. Let's define a Log as:

  type Log 'T = ('T, string) 

Then define the makeLog function as

  decl makeLog : 'T -> string -> ('T, string)

  let makeLog value info = (value, info) 

And define pipeLog

  decl passLog : Log 'T -> ('T -> Log 'U) -> Log 'U

  let passLog (prev_val, prev_info) compute_log =

    match (compute_log prev_val)

    | (next_val, next_info) -> makeLog next_val (prev_info + next_info) 

And then define the Monad instance as

  instance Monad Log =

    let make (value, info) = makeLog value info

    let bind prev_log cont = passLog prev_log cont   

 This Log monad allows you to keep track of a string description of computation. When you bind one log into a computation, the passLog function keeps track of the previous information, and then appends it to the next information, to create a full log.

And Yet Another Monad... 

    This time, it's the point-free monad. Basically, it allows you to define point-free functions (without reference to formal parameters).

   Let's define the point-free monad as:

  type Function 'I 'O = 'I -> 'O

  let const x = func _ -> x

  instance Monad (Function 'I) =

    let make fn = const fn

    let bind prev_func cont_func = func arg -> arg |> cont_func (prev_func arg)

We can then use it in this example:

  let xTimes2PlusXOver3 = do

  {

    let! times2 = func x -> x * 2

    let! over3  = func x -> x / 3

    return times2 + over3

  }

That example basically uses the point-free monad to multiple a number by 2, and then add to that the number over 3.

  xTimes2PlusXOver3 15 # (15*2) + (15/3) = 30 + 5 = 35

Closing Words (No More Monads For You)

    I hope I explained monads well enough. I showed you the theoretical definition of a monad, desribed the Maybe/Option/Success monad, gave you an example, and then also gave you two other monads to think about. So now, I think I've written enough (so I'll stop writing soon). Next time on FAIL, I will be writing about inline blocks versus methods in Ruby (either that, or about the hypothetical functional language used in this post). See you there!