[ bsd3, library, unclassified ] [ Propose Tags ]

Please see the README on Github at https://github.com/githubuser/timemap#readme

[Skip to Readme]
Versions 0.0.0, 0.0.1, 0.0.2, 0.0.3, 0.0.4, 0.0.5, 0.0.6, 0.0.7 (info)
Dependencies base (>=4.8 && <5), containers, focus, hashable, list-t, stm, stm-containers, time, unordered-containers [details]
License BSD-3-Clause
Copyright Copyright (c) 2018 Athan Clark
Author Athan Clark
Maintainer athan.clark@localcooking.com
Home page https://github.com/athanclark/timemap#readme
Bug tracker https://github.com/athanclark/timemap/issues
Source repo head: git clone https://github.com/athanclark/timemap
Uploaded by athanclark at Fri Apr 6 07:58:04 UTC 2018
Distributions NixOS:0.0.7
Downloads 1497 total (115 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-04-14 [all 1 reports]
Hackage Matrix CI




Maintainer's Corner

For package maintainers and hackage trustees

Readme for timemap-0.0.7

[back to package description]


A mutable Data.HashMap-like structure, where each entity is implicitly indexed by their last-modified time. Useful for keyed caches.


import qualified Data.TimeMap as TM
import Control.Concurrent.STM

main :: IO ()
main = do
  -- create a new, empty reference
  mapRef <- atomically TM.newTimeMap

  -- insert a new key/value pair in the map. Note that
  -- `someKey` should implement `Hashable`. This also
  -- sets the creation time of the value to "now".
  TM.insert someKey 0 mapRef

  -- adjusts the value of `someKey` to `1`. Note that
  -- also resets the creation time of the value to "now".
  TM.adjust (+1) someKey mapRef

  -- wait a second
  threadDelay 1000000

  -- delete all values older than 1 second from now.
  atomically $ TM.filterFromNow 1 mapRef

  -- Will return `Nothing`
  atomically $ TM.lookup someKey mapRef

  return ()

How it works

There are two internal maps for a TimeMap k a:

  • a "time-indexed" map reference: TVar (Map UTCTime (HashSet k))
  • a mutable map of values: STMContainers.Map.Map k (UTCTime, a)


Inserting a new value first performs a lookup on the hashtable to see if the key already exists:

  • If it doesn't, insert the current time and the element that into the mutable map. Then, insert the key as the value, and the time as the key into the time-indexed multimap.
  • If it does, remove the entry from the time-indexed multimap for the old time, before doing the same thing as the first bullet.


This doesn't have to create new data, and thus doesn't need full IO. All it does is lookup the key in the mutable map.


To filter out all entries older than some time, you have to use the Data.Map.splitLookup function to split the time-indexed multimap into the entries you want to delete from the main container, and the ones you want to keep. You simply writeTVar the map you want to keep, but for the ones you want to delete, you need to get all the elems of that map. Then, for every key that we need to delete, we delete it from the main container. Suprisingly, this appears to operate in constant time, regardless of the size of the map.

How to run tests

stack test


stack bench --benchmark-arguments="--output profile.html"

You can also view the results on my box here.