On Jan 2, 8:52 am, Dr Jon D Harrop ... wrote
....
> You want structural ha****ng, which is one of the developments added by
> OCaml and improved by F#.
....
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#?
|
