When evaluating M3.(>>=) m f, the input (m) is only evaluated/called once and passed to f to give a result (tmp), before the final monadic value is returned. (This monadic value may call (tmp) several times.) When evaluating M4.(>>=) m f, the input (m) is only evaluated/called within the evaluation of the result, and it will occur as many times as this result is requested. So for example, you are trying to define a recursive function on an input of size N, and you define it as (>>=) (recursive-call) f, where (recursive-call) calls the function on an input of size N-1, you will typically get a computation time linear in N with M3 and exponential in N with M4 -- but it could also be constant-time if the result of ((>>=) (recursive-call) f) is never used. On Thu, Jan 25, 2018 at 3:04 PM, Jean-Marc Alliot wrote: > 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 >