[Camllist] OCaml popularity

Graham Guttocks
 Gerd Stolpmann
 Nicolas Cannasse
 Martin Weber
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20030312 (11:24) 
From:  Diego Olivier Fernandez Pons <DiegoOlivier.FERNANDEZPONS@c...> 
Subject:  Re: [Camllist] OCaml popularity (long!) 
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 FFTWGEL 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 nonacademic 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 'higherorder' 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 'higherorder' style we will use the 'min' function and a 'listtraversal' 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 builtin sequence operator (Caml sequence ';')  use a builtin 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners