slotmap: Pure Haskell slotmap implementation over ST or IO.

[ bsd3, data, library ] [ Propose Tags ]

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


[Skip to Readme]
Versions [faq] 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 Mon Sep 17 09:25:17 UTC 2018
Distributions NixOS:0.1.0.0
Downloads 192 total (10 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-09-17 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


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.