Accueil     Ŕ propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis ŕ jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml ŕ l'adresse ocaml.org.

[Caml-list] OCaml popularity
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-03-13 (01:04) From: james woodyatt Subject: [Caml-list] monads for dummies
```[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:
> 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

Once you start using immutable data structures in complex ways (e.g.
doing lots of weird transformations on 'a list values), you may find
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

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
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:

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
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

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

```