fixplate-0.1.8: Uniplate-style generic traversals for optionally annotated fixed-point types.

Safe HaskellSafe
LanguageHaskell2010

Data.Generics.Fixplate.Trie

Contents

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

Documentation

data Trie f v Source #

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

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

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

TODO: more efficient implementation?

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

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

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

Insertion / deletion

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

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

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

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

Set operations

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

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

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

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

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