trie-simple: Simple Map-based Trie

[ bsd3, data-structure, library ] [ Propose Tags ]

Trie data structure TMap to hold mapping from list of characters to something, i.e. isomorphic to `Map [c] v`. It is more efficient to query compared to Map. Also, it supports extra operation like prefix matching. This package also contains TSet, which is isomorphic to Set of lists of characters.


[Skip to Readme]
Versions [faq] 0.4.1.1
Change log CHANGELOG.md
Dependencies base (>=4.9 && <4.13), containers (>=0.5.7.1 && <0.6), deepseq (>=1.4.2.0 && <1.5), mtl (>=2.2.1 && <2.3) [details]
License BSD-3-Clause
Copyright Koji Miyazato
Author Koji Miyazato
Maintainer viercc@gmail.com
Category Data Structure
Source repo head: git clone https://github.com/viercc/trie-simple -b master
Uploaded by viercc at Sat Dec 1 23:43:23 UTC 2018
Distributions NixOS:0.4.1.1
Downloads 180 total (23 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-12-01 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for trie-simple-0.4.1.1

[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, and suffixes support
  • Can be more memory-efficient (but not always; needs benchmark anyway).

Benchmarks

Benchmarks compared against plain Map and Set.

benchmark chart for TMap

benchmark chart for TSet

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.