[Caml-list] monads for dummies

[james woodyatt <jhw@wetware.com>]

[followups redirected to ocaml_beginners@yahoogroups.com]

On Tuesday, Mar 11, 2003, at 11:47 US/Pacific, mgushee@havenrock.com 
wrote:
>
> [...] My other big problem with Haskell was ... you guessed it: 
> monads! I
> must have read every introduction to monads that's available on line
> (and there are at least half a dozen), but I still don't really
> understand them. [...]

I'm a self-taught "programmer" with no formal education in mathematics 
or computer science, and I found the monad concept to be fairly 
difficult to learn.  It took a leap of consciousness that feels about 
the same level of difficulty as what I remember needing to get through 
my high school calculus class.

I've been seeing a lot of attempts to explain the theory lately, but 
most of them remind me of the kind of thing that I found more confusing 
than helpful when I was trying to get my head around the practical 
matters.  What I really wanted is a Monads For Dummies tutorial.

Here's what I remember being the crucial tip that got me over the hump: 
if you are working with immutable data structures (and there are at 
least three in the Ocaml standard library: Map, Set and List), then the 
monadic programming style can be really useful for composing 
complicated functions for manipulating the contents of those data 
structures from assemblies of simpler functions.

Without the monadic programming style, you end up concocting huge 
specialized functions for passing into the higher-order standard 
library functions, e.g. fold, map, filter, etc., and achieving any kind 
of modularity requires careful design work.  The problem can quickly 
become hard enough that learning monadic programming starts to seem 
like a decent trade.

Once you start using immutable data structures in complex ways (e.g. 
doing lots of weird transformations on 'a list values), you may find 
that writing your functions as monads will help you modularize your 
program, allowing you to encapsulate and reuse computations that would 
otherwise be duplicated in scattered fragments of code all over the 
place.  (Alternatively, you may want to use mutable data structures 
instead, which is always a popular way out of this problem.)

If you discover your immutable data structure manipulations are getting 
out of hand, and you want to reorganize your code for better 
encapsulation and reusability-- without changing them to use mutable 
data structures instead-- then I recommend learning about the 
continuation monad first.

Here is the signature of a module I use for the continuation monad in 
Ocaml:

   type ('x, 'a) t = ('a -> 'x) -> 'x

   (* let ( >>= ) m f x = m (fun a -> f a x) *)
   val ( >>= ): ('x, 'a) t -> ('a -> ('x, 'b) t) -> ('x, 'b) t

   val return: 'a -> ('x, 'a) t          (* let return x f = f x         
      *)
   val lift: 'x -> ('x, 'a) t            (* let lift x _ = x             
      *)
   val cont: ('x -> 'x) -> ('x, unit) t  (* let cont f g = f (g ())      
      *)
   val eval: ('x, unit) t -> 'x -> 'x    (* let eval m x = m (fun () -> 
x)    *)

By using this module, I can make new continuations (functions of type 
'x -> 'x) by composing appropriate instances of the continuation monad 
type and binding them with functions that chain the results of previous 
computations into the subsequent computations.

For a very simple example: if you have a bunch of continuation 
functions, e.g. f1, f2, f3 each of type 'x -> 'x, then you can compose 
them in sequence like so:

	let m: ('x, unit) t =
	  cont f1 >>= fun _ ->
	  cont f2 >>= fun _ ->
	  cont f3

In fact, it might be easier to represent f1, f2 and f3 as their monads 
to begin with:

	let m1: ('x, unit) t = cont f1
	let m2: ('x, unit) t = cont f2
	let m2: ('x, unit) t = cont f3

	let m: ('x, unit) t =
	  m1 >>= fun _ ->
	  m2 >>= fun _ ->
	  m3

This defines a new instance of the continuation monad type, but it 
isn't exactly the composed continuation function yet.  You *evaluate* 
the monad to get the continuation it represents:

	let f: 'x -> 'x = eval m

The 'return' function is also sometimes called the 'unit' function (but 
'unit' is a reserved word in Ocaml, so I like to avoid it).  It 
constructs a monad that passes a value through the ( >>= ) operator to 
the function that constructs a new monad value with it.  It's good for 
use in monad functions that take input from "outside" the encapsulation 
and pass it along to other monads.

The 'lift' function is a variant of the 'cont' function which ignores 
the 'x value that is input from any previous computation and produces 
the 'lifted' value as output.  It's good for use in monad functions 
that initialize (or reinitialize) the encapsulated value of the monad.  
I probably should have named it 'init' instead.

If I were writing a book on using monads for dummies, I'd launch here 
into a series of useful examples showing how to use monads to simplify 
very complicated list manipulation functions.  The example above is too 
simple to show the power of monadic programming adequately.  I don't 
have the time, but it's certainly something that needs to be done.

The continuation monad is only the beginning.  There are several 
fundamental types of monad, and it's possible to combine them into 
composites to support more operations, e.g. state manipulation, 
exception handling, backtracking, etc.  Once you understand how to use 
monads in a systematic design, you can take better advantage of the 
support for pure functional programming available in the Ocaml language.

In lieu of my writing a long list of examples, here is a paper that I 
found immensely helpful in the learning process:

	<http://www.math.chalmers.se/~augustss/AFP/monads.html>

The examples are written in Haskell, but I found them pretty easy to 
translate in my head to the equivalent Ocaml.

Warning: you don't have to go down this path very far before you will 
begin to chafe at the "operator overloading" problem.  You can't define 
a ( >>= ) operator that will be good for all monad types.  I don't know 
how to explain exactly why.  You just can't.  Some folks have proposed 
that "extensional polymorphism" would be very helpful  in helping solve 
the problem.  I buy that.

Warning2: since Ocaml strictly evaluates all the arguments to a 
function before executing it (unless the argument is of type 'a 
Lazy.t), you really can't define a proper ( >> ) operator for your 
monads.  It won't work the same as the one in Haskell, because Ocaml 
evaluates the right operand before it's needed, and you don't buy 
anything by fixing it so that it takes a Lazy.t value instead.

If what I've written isn't very helpful to you, then please tell me so 
I know not to try to explain this stuff to people.  On the other hand, 
if it *is* helpful, that would be nice to know too.


-- 
j h woodyatt <jhw@wetware.com>
that's my village calling... no doubt, they want their idiot back.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners