list-tries: Tries and Patricia tries: finite sets and maps for list keys

[ bsd3, data, data-structures, library ] [ Propose Tags ]
Versions 0.0, 0.1, 0.2, 0.3, 0.4, 0.4.1, 0.4.2, 0.4.3, 0.5, 0.5.1, 0.5.2, 0.6.0, 0.6.1, 0.6.2, 0.6.3, 0.6.4, 0.6.5
Dependencies base (>=3 && <4.1), containers (>=0.2 && <0.4), dlist (==0.4.*) [details]
License BSD-3-Clause
Author Matti Niemenmaa
Maintainer Matti Niemenmaa <>
Category Data, Data Structures
Home page
Uploaded by MattiNiemenmaa at Tue Apr 21 20:46:03 UTC 2009
Distributions NixOS:0.6.5
Downloads 6009 total (73 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI

This library provides implementations of finite sets and maps for list keys using tries, both simple and of the Patricia kind. In most (or all? sorry, haven't benchmarked yet) cases, the Patricia tries will have better performance, so use them unless you have reasons not to.

The data types are parametrized over the map type they use internally to store the child nodes: this allows extending them to support different kinds of key types or increasing efficiency. Child maps are required to be instances of the Map class in Data.ListTrie.Base.Map. Some operations additionally require an OrdMap instance.

The Eq, Ord, and Enum modules contain ready structures for key types which are instances of those classes, using lists of pairs, Data.Map, and Data.IntMap respectively.





Assume that containers has a version number of at least 0.3. If false, some functionality cannot be implemented and is changed to call error instead. Defaults to False as such a version hasn't yet been released.


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainer's Corner

For package maintainers and hackage trustees