Particularly useful for memoization. See with_cache and with_cache_rec for more details.
Typical use case: one wants to memoize a function f : 'a -> 'b
. Code sample:
let f x =
print_endline "call f";
x + 1;;
let f' = with_cache (lru 256) f;;
f' 0;; (* prints *)
f' 1;; (* prints *)
f' 0;; (* doesn't print, returns cached value *)
type ('a, 'b) callback
= in_cache:bool ‑> 'a ‑> 'b ‑> unit
Type of the callback that is called once a cached value is found or not. Should never raise.
true
if the value was in cache, false
if the value was just produced.with_cache c f
behaves like f
, but caches calls to f
in the
cache c
. It always returns the same value as
f x
, if f x
returns, or raise the same exception.
However, f
may not be called if x
is in the cache.
with_cache_rec c f
is a function that first, applies f
to
some f' = fix f
, such that recursive calls to f'
are cached in c
.
It is similar to with_cache but with a function that takes as
first argument its own recursive version.
Example (memoized Fibonacci function):
let fib = with_cache_rec (lru 256)
(fun fib' n -> match n with
| 1 | 2 -> 1
| _ -> fib' (n-1) + fib' (n-2)
);;
fib 70;;
val size : (_, _) t ‑> int
Size of the cache (number of entries). At most linear in the number of entries.
val iter : ('a, 'b) t ‑> ('a ‑> 'b ‑> unit) ‑> unit
Iterate on cached values. Should yield size cache
pairs.
val add : ('a, 'b) t ‑> 'a ‑> 'b ‑> bool
Manually add a cached value. Return true
if the value has successfully
been added, and false
if the value was already bound.
Linear cache with the given size. It stores key/value pairs in an array and does linear search at every call, so it should only be used with small size.
Replacing cache of the given size. Equality and hash functions can be parametrized. It's a hash table that handles collisions by replacing the old value with the new (so a cache entry is evicted when another entry with the same hash (modulo size) is added). Never grows wider than the given size.