Re: [Caml-list] OCaml popularity (long!)

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

    Bonjour,

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

Monads are not specific to Haskell and they may be useful in many
other situations than IO in a lazy context. FFTW and FFTW-GEL both use
monads for graph traversal (even if I think afterwards it may not be
the best way).

I will try to explain monads briefly and in a non-academic manner,
since all academic explainations seem to have failed.

When you write a program, you usually have some data x and functions f
and g that you apply over your data

let x1 = f x
let x2 = g x1

Which we will write g (f x)

In functional languages, functions are first class citizens and then
you can use them as if they were data. You can do this transformation
(which I will call duality) in an explicit manner :

let dual = function x -> (function f -> f x)

Instead of writing g (f x) we will have  (dual x) (g o f) where the
'o' stands for composition

let (o) = fun f g -> (function x -> g (f x))

You can write all your programs in this 'higher-order' style. We will
use a small example I have already used in a precedent post on
continuation passing style

let rec min_list_rec m= function
  | [] -> m
  | x :: tail when x < m -> min_list_rec x tail
  | _ :: tail -> min_list_rec m tail

val min_list_rec : 'a -> 'a list -> 'a = <fun>

let min_list = function
  | [] -> failwith "the list is empty"
  | x :: tail -> min_list_rec x tail

val min_list : 'a list -> 'a

This is the 'level 0' style.

To transform it to a 'higher-order' style we will use the 'min'
function and a 'list-traversal' function as basic data

let rec list_traversal f = function
  | [] -> failwith "empty list"
  | [x] -> x
  | x :: tail -> f x (list_traversal f tail)

val list_traversal : ('a -> 'a -> 'a) -> 'a list -> 'a

let min_list = list_traversal min

min_list : 'a list -> 'a

The computation may be seen in the following way

let f1 = F f
let f2 = G f1
 ...

fn (x)


Why would you want to do something like this ?

When you write in a functional language f x y, the order in which the
two arguments will be evaluated in undefined. When you want to do IO
this may be a problem : which data will be printed first ?

On the other hand, the higher order style has a defined order : when
you write g o f, f will always be evaluated before g.

Then several solutions are available :

- Write your code with explicit sequences : f x y => f2 (f1 x y)
  where f1 does the first operation, f2 the second one.

- use a built-in sequence operator (Caml sequence ';')

- use a built-in higher order tool (Haskell monads, Scheme
continuations)

One more thing, you will find two classical 'higher order' styles :
monadic style and continuation passing style

let rec min_list_rec f = function
  | [] -> failwith "empty list"
  | [x] -> f x
  | x :: tail -> min_list_rec (fun y -> f (min x y)) tail

val min_list_rec : ('a -> 'b) -> 'a list -> 'b

let min_list = min_list_rec (function x -> x)

What is the difference ?

Roughtly, in monadic style you only apply on the right (dual x) (f (g
(h))),in CPS you can apply on the left or the right (dual x) (h (f
(g))).

This is achived by giving you one more parameter, the 'continuation'
of the current computation. In my 'min_list' example the continuation
is just the identity function.

Monads also need some 'algebraic' properties, the correct mathematical
formalisation is the theory of categories (Saunders Mac Lane, Samuel
Eilenberg)

Wadler has shown that in fact CPS and monads are equivalent (you can
simulate each one with the other one). The combination with lazy
evaluation (which can also be done in Caml) can give strange monads
like 'backtracking monad' (Wadler) which may be used to implement
backtracking searches, embedding a Prolog in a functional language
(Hinze). This can be also achieved by CPS like Screamer, a Lisp
preprocessor that rewrittes backtracking function in CPS (Siskind,
McAllester) or direct implementation with some kind of queue.


    Hope this helps,

        Diego Olivier

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