Re: [Caml-list] Memoizing (was: static variables...)

[Pierre Weis <pierre.weis@inria.fr>]

> let fib = ref (function | _ -> 1);;
> fib := function  | 0 | 1 -> 1 | n-> !fib (n-1) + !fib (n-2) ;;
> let memo h f x = (if not (Hashtbl.mem h x) then Hashtbl.add h  x (f x); 
> Hashtbl.find h x);;
> let h = Hashtbl.create 97;;
> fib := memo h !fib;;
>
> John Max Skaller, mailto:skaller@ozemail.com.au

A slightly more functional way of defining a memo function (i.e. with
no ref to define the memoized function):

let memo f =
  let h = Hashtbl.create 11 in
  fun x ->
    try Hashtbl.find h x with
    | Not_found ->
        let r = f x in
        Hashtbl.add h x r;
        r;;

open Lazy;;

let fib =
  let rec f =
    lazy (memo (
    function
    | 0 | 1 -> 1
    | n -> force f (n - 1) + force f (n - 2))) in
  force f;;

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners