Thursday, April 16, 2009

Monads 102: using Haskell online (or 'Finding your inner Klingon')

The Goal

This post is a long-delayed follow-up to a talk I gave at the Lambda Lounge. It will use a simple code example to show some intermediate ideas of monads in Haskell.

The best part is that the code can be pasted into Codepad (no affiliation) and tinkered with. No download necessary!

(Note that a recent review of RWH calls Haskell "like Klingon, but with math". Hence the subtitle.)

Where is Monads 101?

There is no Monads 101 post on this blog. This is part of the zen of monads, as explained in Monads are Burritos. I did my best at the Lambda Lounge, and have some fun ideas for the future, but for now, this post is intended for readers who have some background in Haskell.

Ok, ok, as a super brief recap, check out this photo. Recall that

1. m is a type constructor (i.e. it is a generic type that wraps another type)

2. a -> m a is a function that injects/wraps something of type a into something of type m. In Haskell, this is called return

3. m a -> (a -> m b) -> m b is a function that takes a monad m a and another function, a -> m b. It returns m b. Loosely speaking, it breaks the inner type out of m and applies the function, resulting in a computed value back inside another m. The 'breaking out of' part is unspecified and unique to each monad. This whole doozie is called bind and uses this symbol: >>=

It is vital to understand that a, b, and m above are types (e.g. Integer, String). Haskell has a gorgeous fluidity between data variables and type variables that can be confusing at first.

A monad is a type that supports all three of the above. I warned you that this was Monads 102. If you aren't comfortable at this point, that's fine. This is non-trivial stuff.

The Goals

We'll take a code example that defines a trivial function called tuple. This example won't change but we'll send in some different monadic values and see what happens.

Example: Maybe (with Integer)

Here is the full example... Paste this into Codepad:


-- see comments below
tuple mx = mx >>= \x -> return (x, x + 1 )

mx = Just 10

main = (print (tuple mx))
Here is a version with comments:

-- In English, tuple accepts a mx, a monad.
-- The monad pulls x out, and builds a simple tuple
-- which is returned in a monad of the same type.
-- Here mx is a variable name. It is of type 'm a'
-- where m and a are types
--
-- 1. tuple takes m a and returns m (a, a)
-- 2. note that \x -> ... is a lambda expression
-- with a parameter 'x'. This expression is
-- the function a -> m b that is passed to bind.
-- 3. >>= is called 'bind' because it binds the
-- value of x
-- NOTE: mx defines the way >>= behaves!!!

tuple mx = mx >>= \x -> return (x, x + 1 )

-- mx is of type Maybe Integer

mx = Just 10

-- main just prints the result

main = (print (tuple mx))
The output should be:
Just (10,11)
Try some other values for mx. Experimentation here will be worth a zillion words and comments.

Example: Maybe (with Double)

In the Codepad editor, change the value of mx to:

mx = Just 3.14
and run again. Since Haskell is Klingon-esque about types, this is a big deal. The tuple function works with Maybe Integer as well as Maybe Double. In fact, it should work with any m a where a supports addition.

Example: Maybe (with Nothing)


Now, again in Codepad, change the value of mx to:

mx = Nothing
The output should be the same: Nothing. What is happening? Recall that the monad supplies the bind function by 'breaking out' the inner type: but each monad can define that behaviour.

In the case of Maybe, that behaviour is defined in part as: if the value is Nothing, then don't even bother calling the supplied function! Hence, the result is Nothing.

Example: List

Here's where things get fun... Let's wish Maybe a fond farewell and use another monad: List. Remember that tuple isn't going to change here.

In Codepad, do this:

mx = [1,2,3,4]
Try and guess what the output should be, then run it.

You should see:
[(1,2),(2,3),(3,4),(4,5)]
The reason for this is that the List monad uses a different definition for 'breaking out' when applying >>= / bind. Clearly, the List definition is to apply the provided function to each element in the list.

Conclusion

The upshot here is that tuple isn't changing. The monads are changing. (Or for you Zen types, your mind is changing. For Klingons, the semantics of the syntax is bending to your will.)

It is important to note that tuple is indeed a lame function with no utility. The types Maybe and List are useful; as monads, they are very basic. If you were to describe the 'breaking out' in pseudocode, they seem trivial:

Given m >>= f where m is m a and f is a -> m b
  • When m is Maybe: if it has something, it applies f; else it does nothing.
  • When m is List: it applies f for each element in the list.
Don't be fooled! There are other monads in Haskell that are much more sophisticated (an intense example is the STM monad for software transactional memory).

The important thing is to understand that the power is in the 'breaking out', which is individual to the monad. Yet against that flexibility, we have seen with tuple that monadic code remains constant.

That's monads in a nutshell: rigidity and flexibility in a powerful combination.

5 comments:

Scott Bale said...
This comment has been removed by the author.
Scott Bale said...

I think I speak for all Java programmers when I drool on myself and my eyes glaze over.

Hamlet D'Arcy said...

This in an improvement in content over the bumper stickers but a step backwards in terms of humor.

This is helpful though, very nice.

Rob said...

Great post!

Anyone who is still a little lost might be illuminated by examining the (inferred!) type of tuple:

tuple :: (Num a, Monad m) => m a -> m (a,a)

Debra said...

I fully agree with anything you've printed here.