| Safe Haskell | Safe-Infered |
|---|
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.
- 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
- 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 aSource
TODO: more efficient implementation?
bag :: (Functor f, Foldable f, OrdF f) => [Mu f] -> Trie f IntSource
Creates a trie-multiset from a list of trees.
universeBag :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f IntSource
This is equivalent to
universeBag == bag . universe
TODO: more efficient implementation?
Lookup
Insertion / deletion
insertWith :: (Functor f, Foldable f, OrdF f) => (a -> b) -> (a -> b -> b) -> Mu f -> a -> Trie f b -> Trie f bSource
Set operations
intersectionWith :: (Functor f, Foldable f, OrdF f) => (a -> b -> c) -> Trie f a -> Trie f b -> Trie f cSource
union :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f a -> Trie f aSource
Union is left-biased:
union == unionWith const