What on earth is this?

What on earth is this?

[Thomas Fischbacher]

Maybe I just need a good night of sleep, maybe I overlooked something 
really dumb and rather should have asked on the beginner's list. Anyway, 
I find the behaviour demonstrated below quite confusing. Why don't the 
definitions ###_v1 and ###_v2 work? Any idea, anyone?

===>
(* (C) T. Fischbacher, 2005 - Demonstrating a simple form of memoizing... *)
#load "unix.cma";;

let timing ?(tagfun= fun _ -> "Time passed: ") ?(channel=stdout) f x =
  let tag = tagfun x in
  let t0 = Unix.gettimeofday () in
  let result = f x in
  let t1 = Unix.gettimeofday () in
  let () = Printf.fprintf channel "%s%f sec\n%!" tag (t1-.t0) in
  result
;;

let rec fibonacci n =
  if n < 2 then 1 else fibonacci (n-1) + fibonacci (n-2)
;;

(*
# timing fibonacci 35;;
Time passed: 4.254157 sec
- : int = 14930352
*)

let memoized ht f arg =
  try
    Hashtbl.find ht arg
  with
  | Not_found ->
      let result = f arg in
      let () = Hashtbl.add ht arg result in
      result
;;

let rec mem_fibonacci_v1 =
  let mem = Hashtbl.create 10 in
  memoized mem
    (fun n -> if n < 2 then 1 else mem_fibonacci_v1 (n-1) + 
mem_fibonacci_v1 (n-2))
;;
(* Error: "This kind of expression is not allowed as right-hand side of `let rec'" *)

let mem_fibonacci_v2 =
  let mem = Hashtbl.create 10 in
  let rec mf =
    memoized mem
      (fun n -> if n < 2 then 1 else (mf (n-1)) + (mf (n-2)))
  in mf
;;
(* Error: "This kind of expression is not allowed as right-hand side of `let rec'" *)

let mem_fibonacci_v3 =
  let mem = Hashtbl.create 10 in
  let mf yfp =
    memoized mem 
      (fun n -> if n < 2 then 1 else yfp () (n-1) + yfp () (n-2))
  in
  let rec yc x = x (fun () -> (yc x)) in
  yc mf
;;

(* This definition worked. And indeed: 

# timing mem_fibonacci_v3 35;;
Time passed: 0.000149 sec
- : int = 14930352
# timing mem_fibonacci_v3 35;;
Time passed: 0.000005 sec
- : int = 14930352
# 
 *)
<===

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] What on earth is this?

[Martin Jambon]

On Fri, 11 Nov 2005, Thomas Fischbacher wrote:

> Maybe I just need a good night of sleep, maybe I overlooked something
> really dumb and rather should have asked on the beginner's list. Anyway,
> I find the behaviour demonstrated below quite confusing. Why don't the
> definitions ###_v1 and ###_v2 work? Any idea, anyone?

> let memoized ht f arg = ...
...
> let rec mem_fibonacci_v1 =
>  let mem = Hashtbl.create 10 in
>  memoized mem
>    (fun n -> if n < 2 then 1 else mem_fibonacci_v1 (n-1) +
> mem_fibonacci_v1 (n-2))
> ;;
> (* Error: "This kind of expression is not allowed as right-hand side of `let rec'" *)
>
> let mem_fibonacci_v2 =
>  let mem = Hashtbl.create 10 in
>  let rec mf =
>    memoized mem
>      (fun n -> if n < 2 then 1 else (mf (n-1)) + (mf (n-2)))
>  in mf
> ;;

Almost there. This should work:

let mem_fibonacci_v2 =
   let mem = Hashtbl.create 10 in
   let rec mf arg =
     memoized mem
       (fun n -> if n < 2 then 1 else (mf (n-1)) + (mf (n-2))) arg
   in mf


Martin

--
Martin Jambon, PhD - http://martin.jambon.free.fr
Open Bioinformatics at http://wikiomics.org

Re: [Caml-list] What on earth is this?

[Thomas Fischbacher]

Thanks for your explanations, guys, you're great.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)