LRU-0.1.1: Implements an LRU data structureSource codeContentsIndex
Data.LRU
Description

This module implements a least-recently-used structure. Conceptually, it's a list of values where the head of the list is the most recently used value. When a value is used, it's moved from its place in the list to the head of the list. The last element in the list is thus the least-recently-used value.

This structure is often used in caches to decide which values to evict when the cache becomes full.

This module uses a Map to implement the LRU efficiently and thus there's the requirement that the elements of the LRU be instances of Ord, which a more general (but slower) LRU implementation could avoid.

Synopsis
data Ord a => LRU a
empty :: Ord a => LRU a
null :: Ord a => LRU a -> Bool
size :: Ord a => LRU a -> Int
hit :: Ord a => a -> LRU a -> LRU a
delete :: Ord a => a -> LRU a -> LRU a
toList :: Ord a => LRU a -> [a]
member :: Ord a => a -> LRU a -> Bool
pop :: Ord a => LRU a -> LRU a
last :: (Ord a, Monad m) => LRU a -> m a
Documentation
data Ord a => LRU a Source
An LRU. Contains the head element, last element and the map from elements to their Items
show/hide Instances
(Ord a, Show a) => Show (LRU a)
empty :: Ord a => LRU aSource
Returns an empty LRU. O(1)
null :: Ord a => LRU a -> BoolSource
Returns True iff the LRU is empty. O(1)
size :: Ord a => LRU a -> IntSource
Returns the number of elements in the LRU. O(1)
hit :: Ord a => a -> LRU a -> LRU aSource
Insert a value into an LRU. If the value is already in the LRU, it's moved to the head of the list. O(log n)
delete :: Ord a => a -> LRU a -> LRU aSource
Removes an element from the LRU, if it exists. O(log n)
toList :: Ord a => LRU a -> [a]Source
Returns a list of the members of the LRU in order, newest first. O(n(log n))
member :: Ord a => a -> LRU a -> BoolSource
Returns true iff the given element is in the LRU. O(log n)
pop :: Ord a => LRU a -> LRU aSource
Remove the last element of the LRU. Errors out if the LRU is empty. O(log n)
last :: (Ord a, Monad m) => LRU a -> m aSource
Return the last element of the LRU. O(1)
Produced by Haddock version 2.1.0