|
|
|
|
|
| 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 |
|
|
|
| Documentation |
|
| data LRU a |
| An LRU. Contains the head element, last element and the map from elements
to their Items
|  Instances | |
|
|
| empty :: Ord a => LRU a |
| Returns an empty LRU. O(1)
|
|
| null :: Ord a => LRU a -> Bool |
| Returns True iff the LRU is empty. O(1)
|
|
| size :: Ord a => LRU a -> Int |
| Returns the number of elements in the LRU. O(1)
|
|
| hit :: Ord a => a -> LRU a -> LRU a |
| 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 a |
| Removes an element from the LRU, if it exists. O(log n)
|
|
| toList :: Ord a => LRU a -> [a] |
| Returns a list of the members of the LRU in order, newest first. O(n(log n))
|
|
| member :: Ord a => a -> LRU a -> Bool |
| Returns true iff the given element is in the LRU. O(log n)
|
|
| pop :: Ord a => LRU a -> LRU a |
| 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 a |
| Return the last element of the LRU. O(1)
|
|
| Produced by Haddock version 0.8 |
