[Caml-list] In need of an ocaml guru

[Caml-list] In need of an ocaml guru

[Jean-Marc Alliot]

[-- 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 --]

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

[Gabriel Scherer]

[-- 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 --]