Monads, monadic notation and OCaml

Jacques Carette
 Walid Taha
[
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:  20050328 (18:17) 
From:  Walid Taha <taha@c...> 
Subject:  Re: [MetaOCaml] Monads, monadic notation and OCaml 
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 nondeterministic 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 nondeterminism 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 breadthfirst 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 (n1) 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 statepassing, continuationpassing 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! 