Module CCCache

Caches

Particularly useful for memoization. See with_cache and with_cache_rec for more details.

type 'a equal = 'a ‑> 'a ‑> bool
type 'a hash = 'a ‑> int

Value interface

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) t
val clear : (__t ‑> unit

Clear the content of the cache.

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.

val with_cache : ?⁠cb:('a'bcallback ‑> ('a'bt ‑> ('a ‑> 'b) ‑> 'a ‑> 'b

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.

val with_cache_rec : ?⁠cb:('a'bcallback ‑> ('a'bt ‑> (('a ‑> 'b) ‑> 'a ‑> 'b) ‑> 'a ‑> 'b

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'bt ‑> ('a ‑> 'b ‑> unit) ‑> unit

Iterate on cached values. Should yield size cache pairs.

val add : ('a'bt ‑> '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.

val dummy : ('a'bt

Dummy cache, never stores any value.

val linear : eq:'a equal ‑> int ‑> ('a'bt

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.

val replacing : eq:'a equal ‑> ?⁠hash:'a hash ‑> int ‑> ('a'bt

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.

val lru : eq:'a equal ‑> ?⁠hash:'a hash ‑> int ‑> ('a'bt

LRU cache of the given size ("Least Recently Used": keys that have not been used recently are deleted first). Never grows wider than the given size.

val unbounded : eq:'a equal ‑> ?⁠hash:'a hash ‑> int ‑> ('a'bt

Unbounded cache, backed by a Hash table. Will grow forever unless clear is called manually.