trie-simple: 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].
[Skip to Readme]
Modules
[Index] [Quick Jump]
Downloads
- trie-simple-0.4.2.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
| Versions [RSS] | 0.4.1.1, 0.4.2 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.14 && <4.21), containers (>=0.5.7.1 && <0.8), deepseq (>=1.4.2.0 && <1.6), hashable (>=1.3 && <1.6), indexed-traversable (>=0.1.1 && <0.2), matchable (>=0.1.2 && <0.2), mtl (>=2.2.1 && <2.4), semialign (>=1.3 && <1.4), these (>=1 && <2), witherable (>=0.4 && <0.6) [details] |
| Tested with | ghc ==8.10.7, ghc ==9.0.2, ghc ==9.2.7, ghc ==9.4.5, ghc ==9.6.2 |
| License | BSD-3-Clause |
| Copyright | Koji Miyazato |
| Author | Koji Miyazato |
| Maintainer | viercc@gmail.com |
| Revised | Revision 5 made by viercc at 2024-07-12T11:52:07Z |
| Category | Data Structures |
| Source repo | head: git clone https://github.com/viercc/trie-simple -b master |
| Uploaded | by viercc at 2023-06-08T05:02:12Z |
| Distributions | LTSHaskell:0.4.2, NixOS:0.4.2, Stackage:0.4.2 |
| Reverse Dependencies | 1 direct, 1 indirect [details] |
| Downloads | 1966 total (22 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs available [build log] Last success reported on 2023-06-08 [all 1 reports] |
Readme for trie-simple-0.4.2
[back to package description]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, andsuffixessupport- 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.