[Caml-list] In need of an ocaml guru

[Jean-Marc Alliot <jean-marc.alliot@irit.fr>]

[-- Attachment #1: Type: text/plain, Size: 5203 bytes --]

Dear Ocaml Gurus,

I have recently hit a problem that I can't really solve by myself, 
probably because I lack a good understanding of the way ocaml works 
really (I am more a very long-time faithful user coming from procedural 
languages than a specialist of functional languages).

The problem that I am going to describe might look slightly far-fetched 
in ocaml, however it occured in a completely natural way in a Haskell 
program I was writing, and it took me quite a long time to spot it; then 
I translated it in ocaml, because I am more at ease with it.

The program is included at the bottom of this message. It is short and 
can be compiled without any additional modules.
The idea is to mimick (more or less...) the behavior of monads and more 
specifically of the Haskell IO monad. However, no previous knowledge of 
Haskell or of monads is required.

The program implements 4 kinds of monads that all respect the monad 
signature. The most interesting implementations are Monad3 and Monad4.

With Monad3, test has type (unit Monad3.t) which is a (unit -> unit) in 
"disguise". However running the resulting program prints "false", 
meaning that (fun v -> return (Printf.printf "%b\n" v)) has been 
executed (and the search2 function has also been executed of course).

Opening Monad4 instead of Monad3 gives a completely different result 
while it looks to a beotian like me that Monad3 is just Monad4 with a 
type constructor added...
Now "false" is not printed. And if I try now to compute (test ()) to get 
the actual answer, the program runs forever (well forever might not be 
the exact word but I was not patient enough to wait).

Let's make a very simple modification. In the third line of search2, it 
is easy to see that the value of acc doesn't matter as the lambda 
expression it is applied to is (fun _ -> ...). So it can be replaced 
(you can comment out acc and uncomment the next line) by anything such 
as (return false), and this should not change the result of the program. 
Well, it changes at least the behaviour... Now (test ()) is computed 
instantaneously and prints (correctly) false...

I would really appreciate if someone could give me answers to the 
following questions:
1) Why the programs with Monad3 and Monad4 behave differently?
2) Why does the program with Monad4 run apparently forever (or a very 
long time)?
3) Why changing acc by (return false) in the program with Monad4 
computes immediately the result?

Of course, in more than 25 years of programming with caml, I have never 
faced such issues. This is why I am going to stick with ocaml and forget 
trying to use Haskell. However, I've spent quite a lot of time on this 
already, and understanding this would make that time well spent, instead 
of lost... :-)

Friendly



(*
module Monad :
   sig
     type 'a t
     val return : 'a -> 'a t
     val ( >>= ) : 'a t -> ('a -> 'b t) -> 'b t
   end
  *)


module Monad = struct
   type 'a t = M of 'a;;
   let return x = M x;;
   let (>>=) (M m) (f : ('a -> 'b t)) = (f m);;
end;;

module Monad1 = struct
   type 'a t = M1 of 'a Lazy.t;;
   let return x = M1 (lazy x);;
   let (>>=) (M1 m) (f : ('a -> 'b t)) =  f (Lazy.force m) ;;
end;;

module Monad2 = struct
   type 'a t = M2 of (unit -> 'a);;
   let return x = M2 (fun () -> x);;
   let (>>=) (M2 m) (f : ('a -> 'b t)) =  (f (m ())) ;;
end;;

module Monad3 = struct
   type 'a t = M3 of (unit -> 'a);;
   let return x = M3 (fun () -> x);;
   let (>>=) (M3 m) (f : ('a -> 'b t)) =
     let (M3 tmp) = f (m()) in
     M3 (fun () -> tmp ());;
end;;

module Monad4 = struct
   type 'a t = (unit -> 'a);;
   let return x = (fun () -> x);;
   let (>>=) m (f : ('a -> 'b t)) = fun () -> (f (m ())) ();;
end;;

(* Use any Monad here *)
open Monad4;;

(* Poor man's multiset *)
let rec delete x (hd::tl) = if x=hd then tl else hd::(delete x tl);;
let insert x s = x::s;;
let fold f b s = List.fold_right f s b;;
let fromlist  s = s ;;

let search2 mynumbers nb =
   let rec ins numbers acc =
     (>>=)
       acc
       (* (return false) *)
       (fun _ ->
         fold
           (fun x acc1 ->
             let numbers2 = delete x numbers
             in fold
                  (fun y acc2 ->
                    let numbers3 = delete y numbers2
                    and res = x + y
                    in if res = nb
                       then (return true)
                       else ins (insert res numbers3) acc2)
                  acc1
                  numbers2)
           acc
           numbers) in
   ins mynumbers (return false);;

let b = fromlist [1;2;3;4];;

(*
Monad : val test : unit Monad.t     Exec: False
Monad1: val test : unit Monad1.t    Exec: False
Monad2: val test : unit Monad2.t    Exec: False
Monad3: val test : unit Monad3.t    Exec: False
Monad4: val test : unit -> unit     Exec: ----
  *)
let test =
   (>>=)
     (search2 b 99999999)
     (fun v -> return (Printf.printf "%b\n" v));;

(* Only use for Monad4.
    It runs forever... *)
(*
let main4 = test ();;
*)

- Jean-Marc Alliot
- Centre International de Mathématiques et d'Informatique de Toulouse 
(Labex CIMI)
   Directeur Adjoint
- mailto:jean-marc.alliot@irit.fr
- Web: http://www.alliot.fr/fpro.html.fr

[-- Attachment #2: Type: text/html, Size: 7198 bytes --]