Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

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.

- data Trie f v
- 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
- toList :: (Traversable f, OrdF f) => Trie f a -> [(Mu f, a)]
- bag :: (Functor f, Foldable f, OrdF f) => [Mu f] -> Trie f Int
- universeBag :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f Int
- christmasTree :: (Functor f, Foldable f, OrdF f) => Mu f -> Attr f (Trie f Int)
- lookup :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f a -> Maybe a
- 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
- 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
- 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

# Documentation

`Trie`

is an efficient(?) implementation of finite maps from `(Mu f)`

to an arbitrary type `v`

.

# Construction / deconstruction

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

TODO: more efficient implementation?

# Multisets

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

Creates a trie-multiset from a list of trees.

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

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

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

# Lookup

# Insertion / deletion

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

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

# Set operations

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

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

Union is left-biased:

union == unionWith const