typerep-map

Efficient implementation of a dependent map with types as keys

https://github.com/kowainik/typerep-map

Version on this page:0.3.1@rev:2
LTS Haskell 18.28:0.3.3.0
Stackage Nightly 2022-02-27:0.4.0.0
Latest on Hackage:0.6.0.0

See all snapshots typerep-map appears in

MIT licensed by Kowainik, Vladislav Zavialov
Maintained by [email protected]
This version can be pinned in stack with:typerep-map-0.3.1@sha256:68f0b2989430709d1a62958c4c1fb34190d09a64cef0665b8796cd91a7789b7d,4790

Module documentation for 0.3.1

Used by 1 package in lts-13.22(full list with versions):

typerep-map

electricity Hackage Build status MIT license

typerep-map introduces TMap and TypeRepMap — data structures like Map, but where types serve as keys, and values have the types specified in the corresponding key spots.

For the more details on the implementation see this blog post.

Usage example

ghci> import Data.TMap

ghci> tm = insert True $ one (42 :: Int)

ghci> size tm
2

ghci> res = lookup tm

ghci> res :: Maybe Int
Just 42

ghci> res :: Maybe Bool
Just True

ghci> res :: Maybe String
Nothing

ghci> lookup (insert "hello" tm) :: Maybe String
Just "hello"

ghci> member @Int tm
True

ghci> tm' = delete @Int tm

ghci> member @Int tm'
False

Benchmarks

Tables below contain comparision with DMap TypeRep of ten lookup operations on structure with size 10^4:

ghc-8.2.2 ghc-8.4.3
DMap TypeRep 517.5 ns 779.9 ns
typerep-map 205.3 ns 187.2 ns
ghc-8.2.2 ghc-8.4.3
DMap 8.2.2 DMap 8.4.3
TMap 8.2.2 TMap 8.4.3

Changes

Change log

typerep-map uses PVP Versioning. The change log is available on GitHub.

0.3.1

  • #64: Fix segfault in toList.
  • Support GHC 8.4.4 and 8.6.3.

0.3.0

  • #46: Make Show instance for TypeRepMap show keys. Add keys function.
  • #48: Add adjust function for TypeRepMap and TMap.
  • #30: Rewrite fromSortedList to use Array and MutableArray instead of IntMap.

0.2.0

  • #43: Implement IsList instance for TypeRepMap. Add hoistA function.
  • #39: Implement hoistWithKey function. Add map function for TMap.
  • Drop support for ghc-8.0.2.

0.1.0

  • Initially created.