[Haskell-cafe] Re: Monad definition question

[oleg at pobox.com]

Ilya Tsindlekht wrote
> > It may be useful to relate to imperative programming:
> >       m1 >>= (\x -> m2)
> > is
> >       let x = m1 in m2
> The analogy is not always straight-forward - try the list monad.

This equivalence holds even for the List Monad. Here is an example of
non-determinism:

http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/1d4df471019050b89e20a002303a8498.en.html

and here's an excerpt from that message, showing lets (aka bind):

let numbers = List.map (fun n -> (fun () -> n)) [1;2;3;4;5];;
let pyth () = 
  let (v1,v2,v3) =
    let i = amb numbers in
    let j = amb numbers in
    let k = amb numbers in
    if i*i + j*j = k*k then (i,j,k) else failwith "too bad"
  in Printf.printf "got the result (%d,%d,%d)\n" v1 v2 v3;;

Here, 'amb' is like 'msum' and any error is mzero. If we replace 'let'
with 'do', and '=' with '<-' in some places, it looks almost like
Haskell. Although the scheduler (the `run' function of the `monad')
described in the message accumulates all possible worlds, it returns
as soon as one `thread' made it successfully to the end.  It is
trivial to get the scheduler to run the remaining `treads' searching
for more answers (by threads I certainly don't mean OS threads). The
user code above stays as it is.

The implementation of amb has been extended to annotate choices (and
so possible worlds) with probabilities, which propagate in due
course. The result not merely lists the answers but also their
computed probabilities.


> > Filinski then showed that the latter seemingly missing aspect
> > indeed only appears to be missing.
> Would this require some kind of macros doing extensive pre-processing
> of the code?

Hopefully the code above showed that no macros and no preprocessing
required. In that code, addition, multiplication, if-then-else and all
other OCaml operations remain as they have always been, with no
modifications or redefinitions whatsoever. Delimited continuations
suffice for everything, as Filinski proved in his paper.