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

[Remi VANICAT <vanicat@labri.u-bordeaux.fr>]

Christopher Quinn <cq@htec.demon.co.uk> writes:

[...]

> That said, I do not understand the memoization function
> itself. Perhaps John Prevost could comment on the use of Val|Exn - in
> particular I cannot see how an initial Exn can be stored in the first
> place as an exception can only be caused by the presence of an Exn!

no, an exception can be caused by the evaluation of the function to
memoize. then the result of evaluating the function (which is the Exn)
will be stored.

By the way, one shouldn't catch the Stack_overflow exception, as it is
not really the result of the evaluation...

>
> What is the advantage over specifying it this way? :
>
> let stow = Hashtbl.create 20
> let memoize f =
>    fun x -> try
>      Hashtbl.find stow x
>    with Not_found ->
>      let v = f x in
>      Hashtbl.add stow x v;
>      v

this memoize function have several problem : 
- it is not fully polymorphic (you have '_a type)
- you cannot apply this function to two different function :

let even' odd' x =
  if x = 0 then true
  else (odd' (x - 1))

let odd' even' x =
  if x = 0 then false 
  else (even' (x - 1))

let rec even x =
  even' odd x
and odd x =
  odd' even x

this work, but 

let rec meven x =
  even' (memoize modd) x
and modd x =
  odd' (memoize meven) x

won't (as they will both use the same hastable)

the only way I see to resolve all those problem is to make:

let new_memoize () =
  let stow = Hashtbl.create 20
  fun f x -> try
     Hashtbl.find stow x
  with Not_found ->
     let v = f x in
     Hashtbl.add stow x v;
     v

each call to new_memoize () will make a new memoize function that
could be apply to one function.



-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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