looking for learning exercise: implement these monads

Question

When learning about new programming subjects I usually follow a pattern: I read about it, I understand it, and then I code up a few examples to make sure I really get it.

I've read a lot about monads, and I'm confident that I understand and get them. I'm now at a stage where I'd really like to code up a few monads to solidify my understanding, and really figure out what it takes to implement bind for a variety of types.

The problem is that I can't think of many obvious monads to implement, so I'm looking for recommendations. Preferably, I'd like a list of recommendations, with some easy ones and some not so easy ones.

I also realize that while monads are used to 'encapsulate' side effects in functional programs, they are also more general than that. So, I'd like the recommendations to include monads that both encapsulate side effects and some general ones.

Thanks!

(as a side note: I'll be working with f# to do this, but I think this question could apply to any functional language).

Answer 1

The list of datastructues/computations that follow some kind of monadic law is extremely rich.

It reaches from lists over optional data ('a option in F#), continuations and multithreading up to highly complex things like parsers.

Just start implementing some of them. Basic exercies:

// Identity monad

let something = ident {
    let! value = id 42
    return value
}

let somethingelse = ident {
    let! value = something
    let! otherValues = id 40
    return value + othervalue
}


// Implement maybe for 'a option
let sum = maybe {
    let! a = maybeInputNumber("a")
    let! b = maybeInputNumber("b")
    let! c = maybeInputNumber("c")
    return a + b + c
}

match sum with
| None -> ...
| Some(n) -> ...

You could also increase your understanding by playing a litte bit with helper functions and explicit monadic syntax.

// Given m >>= f for m.Bind(f)

let (>-) f monad = monad >>= (fun k -> return(f x))

// What's this?
let res = ((+) 1) >- [1..10]

If you want some complex examples, take a look at monadic parser combinators. This will allow you to implement complex recursive descent parsers in plain F# (Take a look at the FParsec-Project)

let parseVector = parser {
    do! ignore $ char '('
    let! [x;y;z] = sepBy parseNumber "," 
    do! ignore $ char ')'
    return new Vector(x, y, z)
}

A simple implementation for this is based on following types:

type 't Computation = 
    | Error of ...
    | Result of 't

type Input     = char list
type 'a Parser = Input -> (('a * Input) Computation)

Try to implement bind and return ;-)

And as a general tip: If you really want to understand monads in their natural environment, you'll have to use Haskell ;-) In F# there are just computation expressions, just a vague analogue, but Haskell introduces a general interface for any monadic computation. Perfect to try them!

Answer 2

I think that the catalog in All About Monads is a good start (the continuation monad is actually useful for catamorphisms, see e.g. here); additionally parsers, and possibly transactional effects. Async is another nice one to try to implement on your own (logically-single-threaded code that hops across different actual threads to be non-blocking). And the underlying monad of the Reactive Framework looks like a good advanced challenge.

Answer 3

Although I suppose there's no challenging the fact that Haskell is the natural language in which to learn about monads, I find that a very helpful exercise is to bring monadic computations to a language which does not, out of the box, have Haskell-like super smooth support for them. It is fully possible in any language, and in any reasonably high-level language it will probably be possible to be creative and actually make them look nice -- learning a lot in the process! I've seen cool monadic syntax for Python (at Valued Lessons, I think), for example.

There's also Clojure's clojure.contrib.monads library which provides nice facilities for using monads in a Lisp. Trying to recreate some of its functionally might be quite instructive. Also, using it sometimes in place of Haskell may be helpful in detaching the general patterns from the particulars of Haskell's syntax (though they are quite nice, to be sure).