Re: [Caml-list] In need of an ocaml guru

[Gabriel Scherer <gabriel.scherer@gmail.com>]

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

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 <jean-marc.alliot@irit.fr>
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 <jean-marc.alliot@irit.fr>
> - Web:  http://www.alliot.fr/fpro.html.fr
>

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