Simple Map-based Trie.
A trie data structure TMap c v
, to hold a mapping from list of characters ([c]
) to something. In other words, a data structure isomorphic to Map [c] v
. It is more efficient to query compared to Map
. Also, it supports extra operations like prefix matching. This package contains TSet c
too, which is isomorphic to Set [c]
.
trie-simple
Trie data structure TMap
to hold mapping from list of characters to something, i.e. isomorphic to Map [c] v
. This package also contains TSet
, which is isomorphic to Set
of lists of characters.
This package implements these structures using Map
from containers package, and require the character type to be only Ord
.
Advantages of using this package over Map
or Set
are:
- 2x Faster
lookup
(member
) operation - Retrieving subset of map or set with given prefix
append
,prefixes
, andsuffixes
support- Can be more memory-efficient (but not always; needs benchmark anyway).
Benchmarks
Benchmarks compared against plain Map
and Set
.
Each of these benchmarks has two sets of point and errorbars, representing two datasets they are run against.
About License
LICENSE tells the licence of this project, EXCEPT one file for benchmark input data. See ABOUT for that file.
If you install trie-simple
from Hackage, that input data is not included in the distributed files.