tst-0.1.1: BK-tree implementation

Safe HaskellSafe-Inferred

Data.TST

Contents

Description

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.

Synopsis

Types

data TST sym v Source

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 vSource

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

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

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

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

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

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)]Source

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

Wildcards

data WildCard a Source

Constructors

WildCard 
El a 

Instances

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

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