[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
--------------------------------------------

Homepage:
     http://code.haskell.org/~wren/

Hackage:

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring-trie

Darcs:
     http://code.haskell.org/~wren/bytestring-trie/

Haddock (Darcs version):

http://code.haskell.org/~wren/bytestring-trie/dist/doc/html/bytestring-trie/

-- 
Live well,
~wren


More information about the Haskell-Cafe mailing list