module Memo:Bounded-size memoization tables`sig`

..`end`

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.