[Haskell-cafe] ANN: TernaryTrees- - An efficient ternary tree implementation of Sets and Maps

Alex Mason axman6 at gmail.com
Mon Jun 29 13:29:45 EDT 2009

TernaryTrees is a package that extends Data.Set ad Data.Map with some  
ternary tree structures, based on the article [http://www.pcplus.co.uk/node/3074/ 
] .

So far there are three modules: Data.Set.TernarySet,  
Data.Map.TernaryMap and Data.Set.StringSet, which can hold `Ord a =>  
[a]`, Ord a => [a] keys with b values, and Strings respectively. The  
interfaces for these types are very much like those of Data.{Set,Map},  
though not wuite as featurefull.

Later releases will also have a StringMap, and I'll update the  
TernaryMap to match the Set implementations more closely in a not too  
distant update.

Ternary trees are supposed to be one of the more efficient ways of  
storing strings in a set, and my testing of this package seems to  
support this (being able to insert 230,000+ words, check that all  
those words are actually in the set, write the set out to disk using  
the Data.Binary instance, reading them back in, and checking the old  
and new sets are equal takes about 3.5 seconds on my machine).

Included is a small example program that runs through the above  
sequence, and then asks the user to enter words to see if they're in  
the set, called tdict.

Please give it a try and let me know what you think, it's my first  
(hopefully) useful hackage package, and I'd love some feedback. There  
is also a darcs repo [http://random.axman6.com/darcs/TernaryTrees/],  
and any patches are welcome.

Alex Mason (Axman6)

More information about the Haskell-Cafe mailing list