typerep-map

Efficient implementation of a dependent map with types as keys

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

Version on this page:0.3.3.0
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

MPL-2.0 licensed by Veronika Romashkina, Vladislav Zavialov, Dmitrii Kovanikov
Maintained by Kowainik
This version can be pinned in stack with:typerep-map-0.3.3.0@sha256:20510efab770158414ac7828d1eca063d795bcc724ac634dd13bc7a50b476f42,4681

Module documentation for 0.3.3.0

typerep-map

logo

GitHub CI Build status Windows build status Hackage Stackage LTS Stackage Nightly MPL-2.0 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 the following 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 ghc-8.8.3 ghc-8.10.1
DMap TypeRep 517.5 ns 779.9 ns 1.559 μs 1.786 μs
typerep-map 205.3 ns 187.2 ns 190.1 ns 169.1 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

Changelog

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

0.3.3.0 — Apr 18, 2020

  • #83: Support GHC-8.10.
  • #80: Build on 32-bit platforms.
  • #78: Support GHC-8.8.3.
  • #63: Add invariant check.

0.3.2 — Mar 27, 2019

  • #47: Add Eq instance for TypeRepMap using -XQuantifiedConstraints.
  • #70: Bump up to dependent-sum-0.5.

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.