trie-simple

Simple Map-based Trie

Version on this page:0.4.2@rev:1
LTS Haskell 22.29:0.4.2@rev:5
Stackage Nightly 2024-07-16:0.4.2@rev:5
Latest on Hackage:0.4.2@rev:5

See all snapshots trie-simple appears in

BSD-3-Clause licensed by Koji Miyazato
Maintained by [email protected]
This version can be pinned in stack with:trie-simple-0.4.2@sha256:42293ff286752ef0a518642bf6c62be79ab86b81c61d33ccbf9d0a642c657723,3088

Module documentation for 0.4.2

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

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.

Changes

0.4.2

  • Compatibility changes

    • Drops GHC older than 8.10 (“base-4.14”)
  • API changes

    • Addition of Data.Trie.Map.fromListWith and Data.Trie.Map.fromAscListWith
    • The behavior of Data.Trie.Map.appendWith is fully specified now.
  • Additional instances

    • Eq1, Eq2, Ord1, Ord2, Show1, Show2 from “base”
    • IsList from “base” (for OverloadedLists GHC extension)
    • Hashable, Hashable1, Hashable2 from “hashable”
    • FunctorWithIndex, FoldableWithIndex, TraversableWithIndex from “indexed-traversable”
    • Filterable(WithIndex), Witherable(WithIndex) from “witherable”
    • Semialign, Align, Zip from “semialign”
    • Matchable from “matchable”

0.4.1.1

  • Initial release.