package lru

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Lru
One-off memoization

lru
- Lru
  - F
    
    Make
    
    K
    
    V
    
    S
  - M
    
    Make
    
    K
    
    V
    
    MakeSeeded
    
    K
    
    V
    
    S
  - Weighted

Legend:
Library
Module
Module type
Parameter
Class
Class type

Scalable LRU caches

Lru provides size-bounded finite maps that remove the least-recently-used (LRU) bindings in order to maintain the size constraint. Two implementations are provided: one is functional, the other imperative.

The functional map is backed by a priority search queue. Operations on individual elements are O(log n).

The mutable map is backed by the standard Hashtbl paired with a doubly-linked list. Operations on individual elements incur an O(1) overhead on top of hash table access.

Both versions support differentially weighted bindings, and have a capacity parameter that limits the combined weight of the bindings. To limit the maps by the number of bindings, use let weight _ = 1.

v0.2.0 — homepage

Lru

module type Weighted = sig ... end

Signature of types with measurable weight.

module F : sig ... end

Functional LRU map.

module M : sig ... end

Mutable LRU map.

One-off memoization

val memo : 
  ?hashed:(('a -> int) * ('a -> 'a -> bool)) ->
  ?weight:('b -> int) ->
  cap:int ->
  (('a -> 'b) -> 'a -> 'b) ->
  'a ->
  'b

memo ?hashed ?weight ~cap f is a new memoized instance of f, using LRU caching. f is an open recursive function of one parameter.

~hashed are hashing and equality over the arguments 'a. It defaults to (Hashtbl.hash, Pervasives.(=)).

~weight is the weighting function over the results 'b. It defaults to fun _ -> 1.

~cap is the total cache capacity.

raises Invalid_argument
when cap < 0.