From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA14154; Wed, 12 Mar 2003 12:24:07 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA14358 for ; Wed, 12 Mar 2003 12:24:06 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h2CBO5X14827 for ; Wed, 12 Mar 2003 12:24:05 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.8/jtpda-5.4) with ESMTP id h2CBO2ZC082828 ; Wed, 12 Mar 2003 12:24:02 +0100 (CET) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id MAA16764 ; Wed, 12 Mar 2003 12:23:02 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id MAA4333804 ; Wed, 12 Mar 2003 12:23:01 +0100 Date: Wed, 12 Mar 2003 12:23:01 +0100 (NFT) From: Diego Olivier Fernandez Pons To: mgushee@havenrock.com cc: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] OCaml popularity (long!) In-Reply-To: <3E6DDAFC.19000.44771B6@localhost> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 cicrp:01 caml-list:01 haskell:01 monads:01 duality:01 passing:01 val:01 failwith:01 'level:99 'higher:01 order':99 monadic:01 achived:01 list':01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 = 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