🧊 LRU Cache

Bounded-capacity cache with least-recently-used eviction

Overview

A purely functional LRU cache that evicts the least recently used entry when the cache is full. Uses an access-ordered list combined with a shadow hash table index for O(1) lookups. All operations return new caches (immutable).

Concepts Demonstrated

Bounded data structures — fixed capacity with automatic eviction
Functional persistence — old cache versions remain valid
Shadow indexing — hash table maintained alongside list for O(1) lookups
Cache statistics — hit/miss tracking for performance monitoring
Higher-order functions — fold, iter, filter, map over cache entries

Key Functions

Function	Description
`create`	Create cache with given capacity
`put`	Insert/update entry (evicts LRU if full)
`get`	Look up and promote to most-recently-used
`peek`	Look up without changing access order
`remove`	Remove a specific key
`resize`	Change capacity (evicts if shrinking)
`stats`	Get hit rate, miss count, fill percentage
`to_list`	Entries in access order (most recent first)

Usage

open LRUCache

let cache = create 3
  |> put "a" 1
  |> put "b" 2
  |> put "c" 3

(* Cache is full — adding "d" evicts "a" (least recently used) *)
let cache = put "d" 4 cache
let _ = get "a" cache   (* → (None, cache') — evicted *)
let _ = get "b" cache   (* → (Some 2, cache') — still present *)

(* Accessing "b" makes it most-recent; "c" becomes LRU *)
let cache = snd (get "b" cache)
let cache = put "e" 5 cache  (* evicts "c" now, not "b" *)

Cache Statistics

let s = stats cache in
Printf.printf "Hit rate: %.1f%%\n" (s.hit_rate *. 100.0);
Printf.printf "Entries: %d / %d\n" s.size s.capacity;
(* → Hit rate: 66.7% *)
(* → Entries: 3 / 3 *)