Up  

Module Memo


module Memo: sig .. end
Bounded-size memoization tables

This module implements memoization tables with random access and bounded size. This can be useful to memoize functions without consuming a lot of memory.
type ('a, 'b) t
Memoization tables with keys of type 'a to values of type 'b.
val create : int -> ('a, 'b) t
create n creates a new memoization table with n slots.
val get : ('a, 'b) t -> ('a -> 'a -> bool) -> 'a -> int -> 'b Lazy.t -> 'b
get tbl cmp x i v tries to fetch a previously computed value for the key x in the table tbl in the slot i. If the result is not available in the table, the result is computed by forcing the lazy argument v. It may be kept it in the table for a later call. This is the case in particular if the slot i was empty. Otherwise, the decision to keep the value for old key or to reuse the slot for the key x is not specified.

The current implementation, however, is such that, if we consider the sequence of all the calls for a given slot, and if one the keys appears strictly more often than half of the time in this sequence, then this key "wins": its result is the one which is kept in the table.

Keys are compared for equality using the function cmp.

val clear : ('a, 'b) t -> unit
clear tbl removes all the keys and the associated values from the table.