list-tries is a Haskell library which implements the trie (Wikipedia article) and Patricia trie (Wikipedia article) data structures. It’s licensed under the 3-clause BSD license.
I decided to make it because I noted that much of the time of Coadjute was spent doing naïve list operations on sets of strings. I realized that Data.Map and such aren’t exactly optimal for strings since they involve many comparisons, so I decided I’d implement something more optimal because no such thing already existed. I’m not sure where I got tries from, in particular, but here we are.
Unfortunately school caught up with me and I haven’t got around to benchmarking it, so I don’t know how much faster it is than Data.Map—or even if there are some workloads under which it is slower. There shouldn’t be.
A bunch of tests are included with the package: as usual, feel free to contribute and/or complain.
The library’s interface is based on that of Data.Map and company: in addition, it provides a strict version for every operation for which it makes sense to be strict. This is still a 0.x version so I’m willing to do a complete API rewrite if it seems necessary.
Obtaining
Assuming you have the cabal-install tool installed and working, the easiest way to obtain list-tries is with the cabal install list-tries command.
Otherwise, you can download the source from Hackage, where you can also browse the documentation.
As a last resort, the source package for the latest version, 0.4.1, is also available here:
A changelog is also available for your reading pleasure:
Dependencies
The full list of dependencies, as listed in the .cabal file, is as follows:
base >= 3 && < 4.4containers >= 0.3 && < 0.5dlist >= 0.4 && < 0.6binary >= 0.5 && < 0.6
For the most part, these should be available in any reasonably up-to-date Haskell distribution, or via the cabal-install tool.