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

HGeometry.Trie.Binary

Description

A Trie type

Synopsis

data TrieF (f :: k -> Type -> Type) (e :: k) v = Node v (f e (TrieF f e v))
type BinaryTrie e v = TrieF (KV AtMostTwoOriented) e v
pattern Leaf :: v -> BinaryTrie e v
pattern LeftNode :: v -> (e, BinaryTrie e v) -> BinaryTrie e v
pattern RightNode :: v -> (e, BinaryTrie e v) -> BinaryTrie e v
pattern TwoNode :: v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v
asBinaryTrie :: forall (f :: Type -> Type) e v. Traversable f => TrieF (KV f) e v -> Maybe (BinaryTrie e v)
data AtMostTwoOriented a
- = Zero
- | OneLeft !a
- | OneRight !a
- | Two !a !a

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 #

type BinaryTrie e v = TrieF (KV AtMostTwoOriented) e v Source #

A binary Trie type

pattern Leaf :: v -> BinaryTrie e v Source #

Pattern match on a leaf node

pattern LeftNode :: v -> (e, BinaryTrie e v) -> BinaryTrie e v Source #

Pattern match on a node with one child, namely on the left

pattern RightNode :: v -> (e, BinaryTrie e v) -> BinaryTrie e v Source #

Pattern match on a node with one child, namely on the left

pattern TwoNode :: v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v Source #

Pattern match on a node with two children

asBinaryTrie :: forall (f :: Type -> Type) e v. Traversable f => TrieF (KV f) e v -> Maybe (BinaryTrie e v) Source #

Trie to convert the trie into a binary trie. If we only have one element, we alwasy produce a left node.

data AtMostTwoOriented a Source #

At most two elements. A one element can either be left or right

Constructors

Zero
OneLeft !a
OneRight !a
Two !a !a

Instances

Instances details

Eq1 AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods liftEq :: (a -> b -> Bool) -> AtMostTwoOriented a -> AtMostTwoOriented b -> Bool #
Ord1 AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods liftCompare :: (a -> b -> Ordering) -> AtMostTwoOriented a -> AtMostTwoOriented b -> Ordering #
Show1 AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> AtMostTwoOriented a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [AtMostTwoOriented a] -> ShowS #
Functor AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods fmap :: (a -> b) -> AtMostTwoOriented a -> AtMostTwoOriented b # (<$) :: a -> AtMostTwoOriented b -> AtMostTwoOriented a #
Foldable AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods fold :: Monoid m => AtMostTwoOriented m -> m # foldMap :: Monoid m => (a -> m) -> AtMostTwoOriented a -> m # foldMap' :: Monoid m => (a -> m) -> AtMostTwoOriented a -> m # foldr :: (a -> b -> b) -> b -> AtMostTwoOriented a -> b # foldr' :: (a -> b -> b) -> b -> AtMostTwoOriented a -> b # foldl :: (b -> a -> b) -> b -> AtMostTwoOriented a -> b # foldl' :: (b -> a -> b) -> b -> AtMostTwoOriented a -> b # foldr1 :: (a -> a -> a) -> AtMostTwoOriented a -> a # foldl1 :: (a -> a -> a) -> AtMostTwoOriented a -> a # toList :: AtMostTwoOriented a -> [a] # null :: AtMostTwoOriented a -> Bool # length :: AtMostTwoOriented a -> Int # elem :: Eq a => a -> AtMostTwoOriented a -> Bool # maximum :: Ord a => AtMostTwoOriented a -> a # minimum :: Ord a => AtMostTwoOriented a -> a # sum :: Num a => AtMostTwoOriented a -> a # product :: Num a => AtMostTwoOriented a -> a #
Traversable AtMostTwoOriented Source #
Instance details Defined in HGeometry.Trie.Binary Methods traverse :: Applicative f => (a -> f b) -> AtMostTwoOriented a -> f (AtMostTwoOriented b) # sequenceA :: Applicative f => AtMostTwoOriented (f a) -> f (AtMostTwoOriented a) # mapM :: Monad m => (a -> m b) -> AtMostTwoOriented a -> m (AtMostTwoOriented b) # sequence :: Monad m => AtMostTwoOriented (m a) -> m (AtMostTwoOriented a) #
Read a => Read (AtMostTwoOriented a) Source #
Instance details Defined in HGeometry.Trie.Binary Methods readsPrec :: Int -> ReadS (AtMostTwoOriented a) # readList :: ReadS [AtMostTwoOriented a] # readPrec :: ReadPrec (AtMostTwoOriented a) # readListPrec :: ReadPrec [AtMostTwoOriented a] #
Show a => Show (AtMostTwoOriented a) Source #
Instance details Defined in HGeometry.Trie.Binary Methods showsPrec :: Int -> AtMostTwoOriented a -> ShowS # show :: AtMostTwoOriented a -> String # showList :: [AtMostTwoOriented a] -> ShowS #
Eq a => Eq (AtMostTwoOriented a) Source #
Instance details Defined in HGeometry.Trie.Binary Methods (==) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool # (/=) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool #
Ord a => Ord (AtMostTwoOriented a) Source #
Instance details Defined in HGeometry.Trie.Binary Methods compare :: AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering # (<) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool # (<=) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool # (>) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool # (>=) :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool # max :: AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a # min :: AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a #