hetero-dict: fast heterogeneous data structures

This package provide two flavor fast and easy to use heterogeneous data structures:

1. Dict which use boxed array, it's read-only with O(1) get.

2. DynDict which use linked-list(see module document for details).

Features simple api, good performance and good error message, Show and From/ToJSON instances are provided.

Example

> :set -XDataKinds -XQuasiQuotes
> :m + Data.Hetero.Dict
> let d = mkDict . add [key|foo|] 12 . add [key|bar|] "baz" $ emptyStore
> :t d
d :: Num v => Dict '["foo" ':= v, "bar" ':= [Char]]
> get [key|foo|] d
12
> get [key|bar|] d
"baz"
> get [key|qux|] d
 • Couldn't match type ‘'Index i1’ with ‘'NotFoundKey "qux"’
 ...

> :set -XDataKinds -XQuasiQuotes
> :m + Data.Hetero.DynDict
> let d =  add [key|foo|] 12 . add [key|bar|] "baz" $ empty
> get [key|foo|] d
12
> get [key|bar|] d
"baz"
> let d' = set [key|foo|] 13 d
> get [key|foo|] d'
13

Benchmark

We use hvect and vinyl as references.

benchmarking n = 3/Index Dict
time                 8.656 ns   (8.396 ns .. 9.040 ns)
                     0.987 R²   (0.964 R² .. 0.999 R²)
mean                 8.784 ns   (8.503 ns .. 9.318 ns)
std dev              1.322 ns   (767.5 ps .. 2.059 ns)
variance introduced by outliers: 97% (severely inflated)

benchmarking n = 3/Index DynDict
time                 6.400 ns   (6.340 ns .. 6.467 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 6.394 ns   (6.348 ns .. 6.454 ns)
std dev              183.8 ps   (153.3 ps .. 230.6 ps)
variance introduced by outliers: 49% (moderately inflated)

benchmarking n = 3/Index HVect
time                 14.12 ns   (13.99 ns .. 14.25 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 14.09 ns   (13.95 ns .. 14.25 ns)
std dev              520.1 ps   (445.4 ps .. 608.7 ps)
variance introduced by outliers: 60% (severely inflated)

benchmarking n = 3/Index Vinyl
time                 6.735 ns   (6.635 ns .. 6.849 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 6.706 ns   (6.656 ns .. 6.763 ns)
std dev              186.4 ps   (142.7 ps .. 252.2 ps)
variance introduced by outliers: 47% (moderately inflated)

benchmarking n = 15/Index Dict
time                 9.482 ns   (9.395 ns .. 9.564 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 9.460 ns   (9.387 ns .. 9.529 ns)
std dev              252.6 ps   (212.2 ps .. 328.3 ps)
variance introduced by outliers: 44% (moderately inflated)

benchmarking n = 15/Index DynDict
time                 10.66 ns   (10.47 ns .. 10.94 ns)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 10.52 ns   (10.43 ns .. 10.65 ns)
std dev              389.0 ps   (286.7 ps .. 575.8 ps)
variance introduced by outliers: 61% (severely inflated)

benchmarking n = 15/Index HVect
time                 14.35 ns   (14.24 ns .. 14.46 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 14.35 ns   (14.20 ns .. 14.51 ns)
std dev              513.6 ps   (395.2 ps .. 693.4 ps)
variance introduced by outliers: 59% (severely inflated)

benchmarking n = 15/Index Vinyl
time                 11.62 ns   (11.47 ns .. 11.75 ns)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 11.63 ns   (11.52 ns .. 11.74 ns)
std dev              373.0 ps   (314.5 ps .. 452.0 ps)
variance introduced by outliers: 54% (severely inflated)

benchmarking n = 15/Modify DynDict
time                 10.30 ns   (10.13 ns .. 10.50 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 10.26 ns   (10.18 ns .. 10.38 ns)
std dev              335.2 ps   (260.3 ps .. 427.1 ps)
variance introduced by outliers: 55% (severely inflated)

benchmarking n = 15/Modify Vinyl
time                 11.74 ns   (11.60 ns .. 11.86 ns)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 11.67 ns   (11.55 ns .. 11.79 ns)
std dev              398.9 ps   (330.5 ps .. 487.9 ps)
variance introduced by outliers: 56% (severely inflated)