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.
- 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
An LRU. Contains the head element, last element and the map from elements to their Items
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)
Returns a list of the members of the LRU in order, newest first. O(n(log n))
Returns true iff the given element is in the LRU. O(log n)
Remove the last element of the LRU. Errors out if the LRU is empty. O(log n)