[Haskell-cafe] ANN: bytestring-trie 0.1.1 (bugfix)

wren ng thornton wren at freegeek.org
Sat Jan 3 22:42:54 EST 2009

-- bytestring-trie 0.1.1 (bugfix)

An efficient finite map from (byte)strings to values.

The implementation is based on big-endian patricia trees, like 
Data.IntMap. We first trie on the Word8 elements of a Data.ByteString, 
sharing string prefixes where possible, and then trie on the big-endian 
bit representation of those elements. Patricia trees have efficient 
algorithms for union and other merging operations, but they're also 
quick for lookups and insertions.

-- Changes

* Fixed a bug in lookupBy_ pointed out by Maxime Henrion. The bug 
affects all "lookup-like" functions when a prefix of the query matches 
only part of a shared prefix in the trie (e.g. looking for "fi" in a 
trie containing ["foo","bar","baz"], but not when looking up "fo", 
"food", or "bag").

* By popular demand Trie now has a Binary instance. This adds a new 
dependency on the binary package. The dependency shouldn't be onerous to 
anyone, but let me know if it is.

-- Links





Haddock (Darcs version):


Live well,

More information about the Haskell-Cafe mailing list