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_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*make*s,*return*s, 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)))

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", ...]

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!

Can anyone explain to me why all the text is double-spaced starting at the "Another Monad..." heading? It looked fine in the post editor...

ReplyDeleteAlso, how do you get syntax-colored code?

On another computer (as in, right now), the text looks fine...

Delete