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