Module CCCache

module CCCache: sig .. end

Caches

Particularly useful for memoization. See CCCache.with_cache and CCCache.with_cache_rec for more details.
Since 0.6


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 : ('a, 'b) t -> unit
Clear the content of the cache
val with_cache : ('a, 'b) t -> ('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 : ('a, 'b) t -> (('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 CCCache.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 : ('a, 'b) 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 dummy : ('a, 'b) t
Dummy cache, never stores any value
val linear : ?eq:'a equal -> int -> ('a, 'b) t
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.
eq : optional equality predicate for keys
val replacing : ?eq:'a equal -> ?hash:'a hash -> int -> ('a, 'b) t
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, 'b) t
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, 'b) t
Unbounded cache, backed by a Hash table. Will grow forever unless CCCache.clear is called manually.