TernaryTrees: Efficient pure ternary tree Sets and Maps

[ bsd3, data-structures, library, program ] [ Propose Tags ]

Ternary trees are an efficient structure often used for storing strings for fast lookups. This package implements a generic tree for storing lists of Ord instances, and a specialised String implementation which is about 30% faster than the generic version.

An example program is provided what shows how to use the package as a dictionary program for spell checking, and how it can be used to serialise data with Don Stewart's Data.Binary package.

From my testing, using the /usr/share/dict/words file on my system (over 230,000 words), inserting all words, checking they all exist in the tree, writing them to a binary file, reading them back in and checking the read in result is the same as the original takes slightly over 3 seconds using the StringSet. The written file is also slightly smaller than the input (by over 40% in some cases).

New in this version:

© 2009 by Alex Mason (http://random.axman6.com/blog/). BSD3 license.

Versions [RSS] [faq] 0.0.1, 0.0.2,,,,,,,,,,,,,,,
Dependencies base (>= && <, binary (>=0.4.4) [details]
License BSD-3-Clause
Author Alex Mason
Maintainer Alex Mason (irc: Axman6) <axman6@gmail.com>
Category Data Structures
Uploaded by AlexMason at 2009-07-12T02:44:55Z
Distributions NixOS:
Executables tdict
Downloads 13038 total (78 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs not available [build log]
Last success reported on 2016-12-31 [all 9 reports]


  • Data
    • Map
      • Data.Map.TernaryMap
        • Data.Map.TernaryMap.Internal
    • Set
      • Data.Set.StringSet
        • Data.Set.StringSet.Internal
      • Data.Set.TernarySet
        • Data.Set.TernarySet.Internal


Maintainer's Corner

For package maintainers and hackage trustees