slotmap: Pure Haskell slotmap implementation over ST or IO.

[ bsd3, data, library ] [ Propose Tags ] [ Report a vulnerability ]

Please see the README on GitHub at https://github.com/harporoeder/slotmap#readme


[Skip to Readme]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), primitive, vector [details]
License BSD-3-Clause
Copyright 2018 Harpo Roeder
Author Harpo Roeder
Maintainer roederharpo@protonmail.ch
Category Data
Home page https://github.com/harporoeder/slotmap#readme
Bug tracker https://github.com/harporoeder/slotmap/issues
Source repo head: git clone https://github.com/harporoeder/slotmap
Uploaded by HarpoRoeder at 2018-09-17T09:25:17Z
Distributions NixOS:0.1.0.0
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 799 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-0.1.0.0

[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
  M.map (*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.