| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Generics.Fixplate.Trie
Description
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.
Synopsis
- 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