pred-trie: Predicative tries

[ benchmark, bsd3, data, library ] [ Propose Tags ]
Versions 0.0.1, 0.0.2, 0.0.3, 0.0.4, 0.0.5, 0.0.6,, 0.0.7,, 0.0.8,, 0.0.9, 0.0.10,,, 0.0.11, 0.0.12, 0.1, 0.2.0, 0.2.1, 0.2.3, 0.2.4, 0.3.0, 0.4.0, 0.4.1, 0.5.0, 0.5.1,,, 0.6.0, (info)
Dependencies base (>=4.8 && <5.0), containers, deepseq, hashable, hashtables, mtl, poly‑arity (>=0.0.7), pred‑set, QuickCheck (>=2.9.2), semigroups, strict, tries (>=0.0.5), unordered‑containers [details]
License BSD-3-Clause
Copyright 2018 Athan Clark
Author Athan Clark
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by athanclark at Sat Mar 17 16:20:20 UTC 2018
Distributions LTSHaskell:, NixOS:, openSUSE:
Downloads 7890 total (114 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-03-17 [all 1 reports]
Hackage Matrix CI

Please see the README on Github at

[Skip to Readme]




Maintainer's Corner

For package maintainers and hackage trustees

Readme for pred-trie-

[back to package description]


A predicative trie library - use predicates instead of literal match to capture classes of results, instead of enumerating distinguished ones.


The predicates are existentially quantified such that a predicate creates an unknown type, while it's result must have the necessary arity, matching the quantified type, to fulfill the lookup:

PredTrie s a
  = PNil
  | forall t. PCons
      { predicate :: s -> Maybe t
      , result    :: t -> a


I broke the lookup phases into "steps", like the tries package, and used the fastest-lookup HashMapStep trie implementation for the literal lookups. For more info, read the code :D

How to run tests

stack test


stack bench --benchmark-arguments="--output profile.html"