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

Safe HaskellSafe-Inferred
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