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 whether it actually is any faster than lists or Data.Map. Of course, if it isn’t, I consider that a bug which needs to be fixed, since the whole point is to be faster.
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.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.1containers >= 0.3 && < 0.4dlist == 0.4.*binary >= 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.
containers–0.3
containers, however, is problematic. Version 0.3 has not been released yet (and it probably doesn’t have that version number in the Darcs repository it lives in, either). The latest Darcs version of containers has some patches I’ve contributed which will allow list-tries to compile and run properly: older versions, including the one shipped with the latest GHC as of this writing (6.10.3), will basically not work.
However, I have implemented a workaround. By default, list-tries will assume that you do not have a recent enough version of containers. A slightly crippled version of list-tries will result: 30 of my 1014 test cases then fail due to calls to error. If you do have a recent enough version, pass the cabal-install tool the -fcontainers03 argument: this way it will want containers >= 0.3 as described under Dependencies, and if it gets it you will get a “proper” version.