slotmap: Pure Haskell slotmap implementation over ST or IO.

[ bsd3, data, library ] [ Propose Tags ]

Please see the README on GitHub at

[Skip to Readme]


[Index] [Quick Jump]


Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS]
Change log
Dependencies base (>=4.7 && <5), primitive, vector [details]
License BSD-3-Clause
Copyright 2018 Harpo Roeder
Author Harpo Roeder
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by HarpoRoeder at 2018-09-17T09:25:17Z
Distributions NixOS:
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 661 total (6 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-09-17 [all 1 reports]

Readme for slotmap-

[back to package description]

Haskell SlotMap

This package implements the SlotMap data structure. SlotMaps are popular in certain high performance situations. This implementation is generic over ST or IO. More information on SlotMaps can be found here.

Example Usage

module Main where

import Data.SlotMap as M

main :: IO ()
main = do
  -- Create SlotMap
  m <- M.empty

  -- Insert Elements
  a <- M.insert 3 m
  b <- M.insert 7 m
  c <- M.insert 9 m

  -- Print Elements
  M.lookup a m >>= putStrLn . show -- Just 3
  M.lookup b m >>= putStrLn . show -- Just 7
  M.lookup c m >>= putStrLn . show -- Just 9

  -- Mutate Elements
  M.delete a m
  M.update m (1+) b (*2) m

  -- Print Updated Elements
  M.lookup a m >>= putStrLn . show -- Just Nothing
  M.lookup b m >>= putStrLn . show -- Just 16
  M.lookup c m >>= putStrLn . show -- Just 18

Structure Properties

Keys are a weakly owning reference to the contents of the store. On insertion a unique key is returned. There is a generational index system such that when a storage slot is reused previous keys to the same slot do not incorrectly return a value.

Operation Complexity
Lookup O(1)
Map O(N)*1
Update O(1)
Delete O(1)
Insert O(1)*2
Size O(1)*3
  1. Where N = capacity NOT size.
  2. May initiate allocation if the capacity is full.
  3. Size != capacity. Capacity may never shrink.