Data.Cache

Documentation

data Cache k v s

A Cache is a bounded collection of data that supports fast random access. When the cach is full, the associated EvictionStrategy is used to discard an item from the cache. Library users should use readThrough to read and replace items in the cache.

newCache

Arguments

:: (Hashable k, NFData v, EvictionStrategy s, Eq k, Ord k)

=> Natural

The maximum cache size

-> s k

The evictionStrategy

-> Cache k v (s k)

Create a new cache of the specified size using the provided EvictionStrategy

readThrough

Arguments

:: (Hashable k, NFData v, EvictionStrategy s, Eq k, Ord k, Monad m)

=> Cache k v (s k)

The current cache state

-> k

The key to look up in the cache

-> (k -> m v)

The accessor function to evaluate if the key is not found

-> m (v, Cache k v (s k))

Performs a read-through operation on a given cache.

class EvictionStrategy s where

Minimal complete definition

recordLookup, evict

Methods

recordLookup

Arguments

:: (Eq k, Hashable k, Ord k)

=> k

The key to lookup

-> s k

The strategy (containing any state necessary)

-> s k

The strategy + state folloiwng adding the key

evict :: (Eq k, Hashable k, Ord k) => s k -> (s k, Maybe k)

Instances

EvictionStrategy FIFO

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> FIFO k -> FIFO k

evict :: (Eq k, Hashable k, Ord k) => FIFO k -> (FIFO k, Maybe k)

EvictionStrategy LFU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> LFU k -> LFU k

evict :: (Eq k, Hashable k, Ord k) => LFU k -> (LFU k, Maybe k)

EvictionStrategy LRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> LRU k -> LRU k

evict :: (Eq k, Hashable k, Ord k) => LRU k -> (LRU k, Maybe k)

EvictionStrategy SeqLRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> SeqLRU k -> SeqLRU k

evict :: (Eq k, Hashable k, Ord k) => SeqLRU k -> (SeqLRU k, Maybe k)

EvictionStrategy MRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> MRU k -> MRU k

evict :: (Eq k, Hashable k, Ord k) => MRU k -> (MRU k, Maybe k)

EvictionStrategy RR

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> RR k -> RR k

evict :: (Eq k, Hashable k, Ord k) => RR k -> (RR k, Maybe k)

data SeqLRU k

This is a naive and terribly slow version of an LRU cache

Instances

EvictionStrategy SeqLRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> SeqLRU k -> SeqLRU k

evict :: (Eq k, Hashable k, Ord k) => SeqLRU k -> (SeqLRU k, Maybe k)

Eq k => Eq (SeqLRU k)

Methods

(==) :: SeqLRU k -> SeqLRU k -> Bool

(/=) :: SeqLRU k -> SeqLRU k -> Bool

Show k => Show (SeqLRU k)

Methods

showsPrec :: Int -> SeqLRU k -> ShowS

show :: SeqLRU k -> String

showList :: [SeqLRU k] -> ShowS

newSeqLRU :: SeqLRU k

data LRU k

An optimized version of an LRU cache. The least recently used element in the cache is evicted once the cache fills up.

Instances

EvictionStrategy LRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> LRU k -> LRU k

evict :: (Eq k, Hashable k, Ord k) => LRU k -> (LRU k, Maybe k)

(Ord k, Hashable k) => Eq (LRU k)

Methods

(==) :: LRU k -> LRU k -> Bool

(/=) :: LRU k -> LRU k -> Bool

Show k => Show (LRU k)

Methods

showsPrec :: Int -> LRU k -> ShowS

show :: LRU k -> String

showList :: [LRU k] -> ShowS

newLRU :: LRU k

data MRU k

A Most Recently Used cache. This evicts the most recently accessed item from the cache

Instances

EvictionStrategy MRU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> MRU k -> MRU k

evict :: (Eq k, Hashable k, Ord k) => MRU k -> (MRU k, Maybe k)

(Ord k, Hashable k) => Eq (MRU k)

Methods

(==) :: MRU k -> MRU k -> Bool

(/=) :: MRU k -> MRU k -> Bool

Show k => Show (MRU k)

Methods

showsPrec :: Int -> MRU k -> ShowS

show :: MRU k -> String

showList :: [MRU k] -> ShowS

newMRU :: MRU k

data RR k

Random Replacement cache. The seed is fixed to an StdGen since its both easily accessible & good enough for this purpose. Random replacement means exactly what it sounds like: when the cache fills up a random element is selected and evicted.

Instances

EvictionStrategy RR

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> RR k -> RR k

evict :: (Eq k, Hashable k, Ord k) => RR k -> (RR k, Maybe k)

Eq k => Eq (RR k)

Methods

(==) :: RR k -> RR k -> Bool

(/=) :: RR k -> RR k -> Bool

Show k => Show (RR k)

Methods

showsPrec :: Int -> RR k -> ShowS

show :: RR k -> String

showList :: [RR k] -> ShowS

newRR :: StdGen -> Int -> RR k

Generate a new Random Replacement cache using the provided seed & size.

Least Frequently Used Cache

data LFU k

Evict the least frequently used element from the cache. This means as an element is accessed, its "score" increases and the element is more likely to survive eviction once the cache fills up.

Instances

EvictionStrategy LFU

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> LFU k -> LFU k

evict :: (Eq k, Hashable k, Ord k) => LFU k -> (LFU k, Maybe k)

(Ord k, Hashable k) => Eq (LFU k)

Methods

(==) :: LFU k -> LFU k -> Bool

(/=) :: LFU k -> LFU k -> Bool

Show k => Show (LFU k)

Methods

showsPrec :: Int -> LFU k -> ShowS

show :: LFU k -> String

showList :: [LFU k] -> ShowS

newLFU :: LFU k

First in First Out Cache (a queue)

data FIFO k

A First in First Out eviction strategy. Items are evicted based on order added, regardless of usage patterns.

Instances

EvictionStrategy FIFO

Methods

recordLookup :: (Eq k, Hashable k, Ord k) => k -> FIFO k -> FIFO k

evict :: (Eq k, Hashable k, Ord k) => FIFO k -> (FIFO k, Maybe k)

Eq k => Eq (FIFO k)

Methods

(==) :: FIFO k -> FIFO k -> Bool

(/=) :: FIFO k -> FIFO k -> Bool

Show k => Show (FIFO k)

Methods

showsPrec :: Int -> FIFO k -> ShowS

show :: FIFO k -> String

showList :: [FIFO k] -> ShowS

newFIFO :: FIFO k