Re: a question about memoization

David B. Benson wrote:
> Here is a sketch of memoizing in SML, using the
> polymorphic sup****t for hash tables, HashTable,
> in the SML/NJ utility library:
> 
> signature MEMOIZE =
> sig
>   type hash_table_args =
>     {hash_fn: 'a -> word, eq_pred: 'a * 'a -> bool}
>   val memoize : hash_table_args
>                   -> ('a -> 'b) -> ('a -> 'b)
>   val memoized : ('a,'b)HashTable.hash_table
>                   -> ('a -> 'b) -> 'a -> 'b
> end
> 
> structure Memoize : MEMOIZE =
> struct
>   type hash_table_args =
>     {hash_fn: 'a -> word, eq_pred: 'a * 'a -> bool}
>   fun memoized ht f a =
>         (case HashTable.find ht a
>            of SOME b => b
>             | NONE =>
>                 let
>                   val b = f a
>                 in
>                   HashTable.insert ht (a,b); b
>                 end
>         (*esac*))
>   fun memoize {hash_fn,eq_pred} f a
>         let
>           val ht = HashTable.mkTable (hash_fn,eq_pred)
>                      (32,LibBase.NotFound)
>         in
>           memoized ht f a
>         end
> end (*structure Memoize*);
> 
> so it is clear that for each type 'a, the programmer
> has to supply a hash function and an equality predicate.
> While type 'a need not be a 'structural type', oft it is.
> What is the corresponding code in O'Caml and F#?

In F#:

  let memoize f =
    let m = Hashtbl.create 1
    fun x ->
      try m.[x] with Not_found ->
      let f_x = f x
      m.[x] <- f_x
      f_x

The critical point is that the hash and equality functions are carried in
the type automatically and do not need to be supplied separately by hand.
This solution combined the correctness of SML with brevity of OCaml.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u