Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	GHC2021

HGeometry.Trie

Description

A Trie type

Synopsis

data TrieF (f :: k -> Type -> Type) (e :: k) v = Node v (f e (TrieF f e v))
root :: forall {k} (f1 :: k -> Type -> Type) (e :: k) v f2. Functor f2 => (v -> f2 v) -> TrieF f1 e v -> f2 (TrieF f1 e v)
mapWithEdgeLabels :: forall e (f :: Type -> Type -> Type) v v'. FunctorWithIndex e (f e) => (v -> v') -> (e -> v -> v') -> TrieF f e v -> TrieF f e v'
foldWithEdgeLabels :: forall e (f :: Type -> Type -> Type) m v. (FoldableWithIndex e (f e), Monoid m) => (v -> m) -> (e -> v -> m) -> TrieF f e v -> m
module HGeometry.Trie.Binary

Documentation

data TrieF (f :: k -> Type -> Type) (e :: k) v Source #

The Trie data type, parameterized by the data structure storing the children.

Constructors

Node v (f e (TrieF f e v))

Instances

Instances details

Bifoldable f => Bifoldable (TrieF f) Source #
Instance details Defined in HGeometry.Trie.Type Methods bifold :: Monoid m => TrieF f m m -> m # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> TrieF f a b -> m # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> TrieF f a b -> c # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> TrieF f a b -> c #
Bifunctor f => Bifunctor (TrieF f) Source #
Instance details Defined in HGeometry.Trie.Type Methods bimap :: (a -> b) -> (c -> d) -> TrieF f a c -> TrieF f b d # first :: (a -> b) -> TrieF f a c -> TrieF f b c # second :: (b -> c) -> TrieF f a b -> TrieF f a c #
Bitraversable f => Bitraversable (TrieF f) Source #
Instance details Defined in HGeometry.Trie.Type Methods bitraverse :: Applicative f0 => (a -> f0 c) -> (b -> f0 d) -> TrieF f a b -> f0 (TrieF f c d) #
Foldable (f e) => Foldable1 (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods fold1 :: Semigroup m => TrieF f e m -> m # foldMap1 :: Semigroup m => (a -> m) -> TrieF f e a -> m # foldMap1' :: Semigroup m => (a -> m) -> TrieF f e a -> m # toNonEmpty :: TrieF f e a -> NonEmpty a # maximum :: Ord a => TrieF f e a -> a # minimum :: Ord a => TrieF f e a -> a # head :: TrieF f e a -> a # last :: TrieF f e a -> a # foldrMap1 :: (a -> b) -> (a -> b -> b) -> TrieF f e a -> b # foldlMap1' :: (a -> b) -> (b -> a -> b) -> TrieF f e a -> b # foldlMap1 :: (a -> b) -> (b -> a -> b) -> TrieF f e a -> b # foldrMap1' :: (a -> b) -> (a -> b -> b) -> TrieF f e a -> b #
Functor (f e) => Functor (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods fmap :: (a -> b) -> TrieF f e a -> TrieF f e b # (<$) :: a -> TrieF f e b -> TrieF f e a #
Foldable (f e) => Foldable (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods fold :: Monoid m => TrieF f e m -> m # foldMap :: Monoid m => (a -> m) -> TrieF f e a -> m # foldMap' :: Monoid m => (a -> m) -> TrieF f e a -> m # foldr :: (a -> b -> b) -> b -> TrieF f e a -> b # foldr' :: (a -> b -> b) -> b -> TrieF f e a -> b # foldl :: (b -> a -> b) -> b -> TrieF f e a -> b # foldl' :: (b -> a -> b) -> b -> TrieF f e a -> b # foldr1 :: (a -> a -> a) -> TrieF f e a -> a # foldl1 :: (a -> a -> a) -> TrieF f e a -> a # toList :: TrieF f e a -> [a] # null :: TrieF f e a -> Bool # length :: TrieF f e a -> Int # elem :: Eq a => a -> TrieF f e a -> Bool # maximum :: Ord a => TrieF f e a -> a # minimum :: Ord a => TrieF f e a -> a # sum :: Num a => TrieF f e a -> a # product :: Num a => TrieF f e a -> a #
Traversable (f e) => Traversable (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods traverse :: Applicative f0 => (a -> f0 b) -> TrieF f e a -> f0 (TrieF f e b) # sequenceA :: Applicative f0 => TrieF f e (f0 a) -> f0 (TrieF f e a) # mapM :: Monad m => (a -> m b) -> TrieF f e a -> m (TrieF f e b) # sequence :: Monad m => TrieF f e (m a) -> m (TrieF f e a) #
Traversable (f e) => Traversable1 (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods traverse1 :: Apply f0 => (a -> f0 b) -> TrieF f e a -> f0 (TrieF f e b) Source # sequence1 :: Apply f0 => TrieF f e (f0 b) -> f0 (TrieF f e b) Source #
(Show v, Show e, Show2 f) => Show (TrieF f e v) Source #
Instance details Defined in HGeometry.Trie.Type Methods showsPrec :: Int -> TrieF f e v -> ShowS # show :: TrieF f e v -> String # showList :: [TrieF f e v] -> ShowS #
(Eq v, Eq e, Eq2 f) => Eq (TrieF f e v) Source #
Instance details Defined in HGeometry.Trie.Type Methods (==) :: TrieF f e v -> TrieF f e v -> Bool # (/=) :: TrieF f e v -> TrieF f e v -> Bool #
(Ord v, Ord e, Ord2 f) => Ord (TrieF f e v) Source #
Instance details Defined in HGeometry.Trie.Type Methods compare :: TrieF f e v -> TrieF f e v -> Ordering # (<) :: TrieF f e v -> TrieF f e v -> Bool # (<=) :: TrieF f e v -> TrieF f e v -> Bool # (>) :: TrieF f e v -> TrieF f e v -> Bool # (>=) :: TrieF f e v -> TrieF f e v -> Bool # max :: TrieF f e v -> TrieF f e v -> TrieF f e v # min :: TrieF f e v -> TrieF f e v -> TrieF f e v #

root :: forall {k} (f1 :: k -> Type -> Type) (e :: k) v f2. Functor f2 => (v -> f2 v) -> TrieF f1 e v -> f2 (TrieF f1 e v) Source #

mapWithEdgeLabels Source #

Arguments

:: forall e (f :: Type -> Type -> Type) v v'. FunctorWithIndex e (f e)
=> (v -> v')	function by which to transform the root
-> (e -> v -> v')
-> TrieF f e v
-> TrieF f e v'

A mapping function to transform the values of the trie, possibly using the edge labels. note that the root does not have an edge label, so it is transformed using a separate function.

foldWithEdgeLabels Source #

Arguments

:: forall e (f :: Type -> Type -> Type) m v. (FoldableWithIndex e (f e), Monoid m)
=> (v -> m)	function by which to transform the root
-> (e -> v -> m)
-> TrieF f e v
-> m

fold with the edge labels

module HGeometry.Trie.Binary