Data.Generics.Fixplate.Trie

Generalized tries. "Normal" tries encode finite maps from lists to arbitrary values, where the common prefixes are shared. Here we do the same for trees, generically.

See also

• Connelly, Morris: A generalization of the trie data structure
• Ralf Hinze: Generalizing Generalized Tries

This module should be imported qualified.

Documentation

data Trie f v

Trie is an efficient(?) implementation of finite maps from (Mu f) to an arbitrary type v.

Construction / deconstruction

empty :: (Functor f, Foldable f, OrdF f) => Trie f a

singleton :: (Functor f, Foldable f, OrdF f) => Mu f -> a -> Trie f a

fromList :: (Traversable f, OrdF f) => [(Mu f, a)] -> Trie f a

TODO: more efficient implementation?

toList :: (Traversable f, OrdF f) => Trie f a -> [(Mu f, a)]

Multisets

bag :: (Functor f, Foldable f, OrdF f) => [Mu f] -> Trie f Int

Creates a trie-multiset from a list of trees.

universeBag :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f Int

This is equivalent to

universeBag == bag . universe

TODO: more efficient implementation? and better name

christmasTree :: (Functor f, Foldable f, OrdF f) => Mu f -> Attr f (Trie f Int)

We attribute each node with the multiset of all its subtrees. TODO: better name

Lookup

lookup :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f a -> Maybe a

Insertion / deletion

insert :: (Functor f, Foldable f, OrdF f) => Mu f -> a -> Trie f a -> Trie f a

insertWith :: (Functor f, Foldable f, OrdF f) => (a -> b) -> (a -> b -> b) -> Mu f -> a -> Trie f b -> Trie f b

delete :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f a -> Trie f a

update :: (Functor f, Foldable f, OrdF f) => (a -> Maybe a) -> Mu f -> Trie f a -> Trie f a

Set operations

intersection :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f b -> Trie f a

intersectionWith :: (Functor f, Foldable f, OrdF f) => (a -> b -> c) -> Trie f a -> Trie f b -> Trie f c

union :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f a -> Trie f a

Union is left-biased:

union == unionWith const

unionWith :: (Functor f, Foldable f, OrdF f) => (a -> a -> a) -> Trie f a -> Trie f a -> Trie f a

difference :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f b -> Trie f a

differenceWith :: (Functor f, Foldable f, OrdF f) => (a -> b -> Maybe a) -> Trie f a -> Trie f b -> Trie f a