Ternary Trees

I ran across an interesting data structure, the ternary tree. Unlike binary trees, a ternary tree splits three ways at every branch. I went ahead and implemented it in Haskell. It should be able to store dictionary type data, or variable name-value look ups.

The basic idea is that a tree consists of branches, leafs, leafy branches, and stubs. Having a leafy branch allows for words to be prefixes of other words, as in the example.

Methods

newTrie a b :: (Ord a) => [a] b -> Trie a b
Create a tree from a single word [a] and associate a value b with it.

insert :: Ord a => [a] -> b -> Trie a b -> Trie a b
Insert a word [a] and a value b into a tree. Insert will return an error if the word already is part of the tree.

lookup :: Ord a => [a] -> Trie a b -> Maybe b
Find the value b associated with a word [a].

map :: (b -> c) -> Trie a b -> Trie a c
Apply a function (b -> c) to all the values b in a tree.

toList :: Ord a => Trie a b -> [([a],b)]
Convert a tree to a list of word-value pairs.

fromList :: Ord a => [([a],b)] -> Trie a b
Convert a list of word-value pairs to a tree.

instance (Binary a, Binary b) => Binary (Trie a b)
An instance of binary for efficient storage of trees. Example: encodeFile "filename" tree

Ternary.hs