From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id AD6EEBC84 for ; Mon, 28 Mar 2005 20:17:33 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2SIHX6g000329 for ; Mon, 28 Mar 2005 20:17:33 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA04704 for ; Mon, 28 Mar 2005 20:17:32 +0200 (MET DST) Received: from cs.rice.edu (cs.rice.edu [128.42.1.30]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2SIHVkx000322 for ; Mon, 28 Mar 2005 20:17:32 +0200 Received: from localhost (calypso.cs.rice.edu [128.42.1.127]) by cs.rice.edu (Postfix) with ESMTP id 79A274A9B1; Mon, 28 Mar 2005 12:17:30 -0600 (CST) Received: from cs.rice.edu ([128.42.1.30]) by localhost (calypso.cs.rice.edu [128.42.1.127]) (amavisd-new, port 10024) with LMTP id 01613-01-30; Mon, 28 Mar 2005 12:17:29 -0600 (CST) Received: from boromir.cs.rice.edu (boromir.cs.rice.edu [128.42.129.71]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by cs.rice.edu (Postfix) with ESMTP id DA7C64A9AA; Mon, 28 Mar 2005 12:17:29 -0600 (CST) Date: Mon, 28 Mar 2005 12:17:29 -0600 (CST) From: Walid Taha To: Jacques Carette Cc: caml-list@inria.fr, metaocaml-users@cs.rice.edu Subject: Re: [MetaOCaml] Monads, monadic notation and OCaml In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: by amavis-2.2.1 at cs.rice.edu X-Miltered: at concorde with ID 42484A3D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42484A3B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; walid:01 taha:01 taha:01 metaocaml:01 monads:01 monadic:01 notation:01 ocaml:01 fft:01 walid:01 syntax:01 ocaml:01 haskell's:01 syntax:01 oleg:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: This is pretty cool! Are you using the same monad we used in the FFT work? Also, can you either get rid of the ";" after the "in" or the "in" before the ";"? :) Walid. On Sun, 27 Mar 2005, Jacques Carette wrote: |Attached is a camlp4 syntax extension for a 'monadic do notation' for OCaml, much like Haskell's. The syntax |extension is joint work with Oleg Kiselyov, and is loosely based on previous work of Lydia van Dijk on a similar |syntax extension. | |Naturally, in OCaml certain monads (like State and IO) are unnecessary. But other monads (List, option, etc) can be |quite convenient. | |But monads can be much more than convenient. Below is some code written in a non-deterministic monad of streams. |This example is particularly interesting in that it cannot be (naively) done in either Prolog or in Haskell's |MonadPlus monad, both of which would go into an infinite loop on this example. | |(* test non-determinism monad, the simplest possible implementation *) |type 'a stream = Nil | Cons of 'a * (unit -> 'a stream) | | InC of (unit -> 'a stream) |let test_nondet () = | let mfail = fun () -> Nil in | let ret a = fun () -> Cons (a,mfail) in | (* actually, interleave: a fair disjunction with breadth-first search*) | let rec mplus a b = fun () -> match a () with | | Nil -> InC b | | InC a -> (match b () with | | Nil -> InC a | | InC b -> InC (mplus a b) | | Cons (b1,b2) -> Cons (b1, (mplus a b2))) | | Cons (a1,a2) -> Cons (a1,(mplus b a2)) in | (* a fair conjunction *) | let rec bind m f = fun () -> match m () with | | Nil -> mfail () | | InC a -> InC (bind a f) | | Cons (a,b) -> mplus (f a) (bind b f) () in | let guard be = if be then ret () else mfail in | let rec run n m = if n = 0 then [] else | match m () with | | Nil -> [] | | InC a -> run n a | | Cons (a,b) -> (a::run (n-1) b) | in | let rec numb () = InC (mplus (ret 0) (mdo { n <-- numb; ret (n+1) })) in | (* Don't try this in Prolog or in Haskell's MonadPlus! *) | let tst = mdo { | i <-- numb; | guard (i>0); | j <-- numb; | guard (j>0); | k <-- numb; | guard (k>0); | (* Just to illustrate the `let' form within mdo *) | let test x = x*x = j*j + k*k in; | guard (test i); | ret (i,j,k) | } | in run 7 tst |;; | |We ourselves have been experimenting with a combined state-passing, continuation-passing monad, where the values |returned and manipulated are code fragments (in MetaOCaml). This allows for considerably simpler, typed code |combinators. Details of this work will be reported elsewhere. | |Jacques | | |!DSPAM:42476c8f13209207723021! |