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

Latest on Hackage:0.6.5

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow to host generated Haddocks.

BSD3 licensed by Matti Niemenmaa
Maintained by Matti Niemenmaa

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.


2018-03-20, 0.6.5:
Updated dependencies and code for GHC 8.4.1 and QuickCheck-2.11, thanks
again to Mikhail Glushenkov.

2017-05-27, 0.6.4:
Updated dependencies for GHC 8.2.1 (release candidate 2) and
binary-0.9, thanks to Mikhail Glushenkov for helping with this.

Also a code change due to a newly problematic type inference.

2016-07-18, 0.6.3:
Dependency update to allow dlist-0.8.

2016-06-28, 0.6.2:
Updated dependencies for GHC 8.0.1.

Added Semigroup instances, bringing in a new dependency on semigroups
on pre-8.0 GHC versions.

2015-04-03, 0.6.1:
Fixed build on base < 4.8.

2015-03-28, 0.6.0:
Updated dependencies for GHC 7.10.

Fixed library vs. test executable dlist dependency mismatch.

Renamed Map.toList to toListKV to avoid conflicts with the new Foldable
class. Also renamed Map.fromList and Map.fromListWith to fromListKV and
fromListKVWith to match. Thanks to davean for the patch.

Added Cabal source-repository metadata, pointing to GitHub.

2014-03-20, 0.5.2:
Updated dependencies, for GHC 7.8 and other new packages.

2013-05-10, 0.5.1:
Fix cabal build.

Minor documentation clarification.

Update binary dependency.

2013-05-09, 0.5:
Added the 'lookupPrefix' and 'deleteSuffixes' functions, of which especially
the former was an embarrassing omission:

lookupPrefix :: [k] -> trie map k a -> trie map k a
deleteSuffixes :: [k] -> trie map k a -> trie map k a

Fixed the documentation headers to refer to 's' instead of 'k' as what we
use for the length of the given key.

Fixed documentation of 'deletePrefix': its complexity is O(s), not O(m).

Some dependency updates.

2012-10-18, 0.4.3:
Dependency updates for GHC 7.6 and otherwise.

2012-05-23, 0.4.2:
Dependency updates for GHC 7.4, thanks to Anders Kaseorg.

2011-03-17, 0.4.1:
Dependency update and Cabalization of the test executable, thanks to JP

2010-09-11, 0.4:
Fixed documentation of the 'deletePrefix' function: if the given key is not
a prefix of any key, an empty, not unchanged, map/set is returned. Thanks to
Brian Bloniarz for the bug report.

Fixed bug in the Patricia version of 'deletePrefix' causing it to not delete
anything if the prefix to be deleted was a proper prefix of the common

Changed 'children' to return the map as-is instead of converting it into a
list first:

children :: Trie trie st map k => trie map k a -> CMap trie map k a

Added the 'children1' function as a single-level equivalent of 'children',
more directly reflecting the structure of the non-Patricia tries. Requested
by Brian Bloniarz.

children1 :: Trie trie st map k => trie map k a -> CMap trie map k a

2010-09-09, 0.3:
Fixed strictness of the strict versions of the following non-Patricia
functions: insert, adjust, alter, union, difference, intersection,
mapInKeys; as well as the Patricia versions of insert and adjust. Thanks to
Brian Bloniarz for the bug report.

Applied the static argument transformation throughout, improving

Dropped support for containers < 0.3; GHC 6.12 has been out long enough, and
support for older versions is too crippled to make it worthwhile.

2010-04-06, 0.2:
Dependency update, nothing more.

2009-07-05, 0.1:
All tries are now instances of Binary, thanks to Gregory Crosswhite. Adds a
dependency on the 'binary' library as well as the following two methods to
the Map class in Base.Map:

serializeToList :: m k a -> [(k,a)]
deserializeFromList :: [(k,a)] -> m k a

2009-04-21, 0.0:
Initial release.
Depends on 4 packages:
comments powered byDisqus