Data.TST

Implementation of a Ternary Search Tree: https://en.wikipedia.org/wiki/Ternary_search_tree, which is a structure useful to store any list-like thing. It is quite resistant to non-random data without needing rebalancing and can be as fast or faster than hash tables.

The usual finite map operations are provided, plus utilities to match wildcarded words efficiently.

Types

data TST sym v

Instances

(Ord sym, Eq v) => Eq (TST sym v)

(Show sym, Ord sym, Show v) => Show (TST sym v)

Operations

empty :: Ord sym => TST sym v

singleton :: Ord sym => [sym] -> v -> TST sym v

insert :: Ord sym => [sym] -> v -> TST sym v -> TST sym v

insertWith :: Ord sym => (v -> v -> v) -> [sym] -> v -> TST sym v -> TST sym v

lookup :: Ord sym => [sym] -> TST sym v -> Maybe v

delete :: Ord sym => [sym] -> TST sym v -> TST sym v

We don't need this and it's slow. But you've got to have a delete!

toList :: Ord sym => TST sym v -> [([sym], v)]

fromList :: Ord sym => [([sym], v)] -> TST sym v

Wildcards

data WildCard a

Constructors

WildCard

El a

Instances

Eq a => Eq (WildCard a)

(Eq (WildCard a), Ord a) => Ord (WildCard a)

Show a => Show (WildCard a)

type WildList a = [WildCard a]

matchWL :: Ord sym => WildList sym -> TST sym v -> [([sym], v)]