lfudacaching

A pure Haskell implementation of cache data structures with multiple eviction policies:

• LFUDA (Least Frequently Used with Dynamic Aging) - Prevents cache pollution by aging out stale entries
• GDSF (Greedy Dual-Size Frequency) - Factors in entry size alongside frequency
• LFU (Least Frequently Used) - Classic frequency-based eviction without aging

Based on the Go implementation from lfuda-go.

Installation

Add lfudacaching to your package.yaml dependencies:

dependencies:
  - lfudacaching

Or in your .cabal file:

build-depends: lfudacaching

Usage

Note: Data.LfudaCache exports its own lookup, so you need to hide it from Prelude.

import Data.LfudaCache
import Prelude hiding (lookup)

main :: IO ()
main = do
  -- Create a cache with capacity 100 using LFUDA policy
  let cache = newLFUDA 100

  -- Insert key-value pairs
  let cache1 = insert "alice" 42 cache
  let cache2 = insert "bob" 99 cache1

  -- Lookup updates frequency (affects eviction priority)
  case lookup "alice" cache2 of
    Just (val, cache2') -> do
      putStrLn $ "Found alice: " ++ show val
      -- Use cache2' going forward (frequency of "alice" was bumped)
      print (size cache2')
    Nothing -> putStrLn "Not found"

  -- Peek reads without updating frequency
  case peek "bob" cache2 of
    Just val -> putStrLn $ "Peeked bob: " ++ show val
    Nothing  -> putStrLn "Not found"

  -- Check membership without frequency update
  print $ contains "alice" cache2  -- True

  -- Remove an entry
  let cache3 = remove "alice" cache2

  -- Cache info
  print $ size cache3  -- 1
  print $ keys cache3  -- ["bob"]

A demo program is included — run it with stack exec lfuda-demo.

API Overview

Construction

Operations

Cache Information

Typeclass Instances

LfudaCache k is an instance of Functor, Foldable, and Traversable, allowing you to map, fold, and traverse over cached values.

Eviction Policies

LFUDA

Priority = frequency + cache age. When an entry is evicted, the cache age is set to the evicted entry's frequency. This prevents long-lived but infrequently accessed entries from dominating the cache.

GDSF

Priority = frequency + cache age * entry size. Similar to LFUDA but factors in entry size, giving larger entries higher eviction resistance. Currently all entries use a fixed size of 1, so GDSF behaves similarly to LFUDA.

LFU

Priority = frequency. Simple frequency counting with no aging. The cache age never changes. Entries that were popular in the past stay cached even if they are no longer accessed.

Important Behavioral Notes

Priorities are sticky

Entry priorities are stored in the underlying priority queue and are only recalculated on lookup, not when the cache age changes. This means:

• After an eviction raises the cache age, existing entries keep their old (lower) priorities.
• A freshly inserted entry gets priority = 1 + current_age, which can be higher than an old entry whose priority was computed when the age was lower.
• To "refresh" an entry's priority to account for the current age, you must lookup it.

This is standard LFUDA behavior and means that entries which haven't been accessed recently will naturally drift toward eviction as the cache ages.

Re-inserting a key resets its frequency

Calling insert on an existing key replaces the value and resets its frequency to 1. If you've built up a high frequency through many lookup calls, re-inserting the same key throws that away. Use lookup to access entries without resetting frequency, or check with contains/peek before inserting.

Eviction happens during insert

When the cache is full, insert evicts the lowest-priority entry before returning. If you insert a key you intend to immediately remove, the eviction still happens. This can remove entries you intended to keep.

Purge does not reset age

purge clears all entries and resets the size to 0, but the cache age is preserved. Entries inserted after a purge will have their priority calculated using the pre-purge age.

Building

stack build        # Build library
stack test         # Run tests (29 tests)
stack bench        # Run benchmarks
stack exec lfuda-demo  # Run demo program