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 Source # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> TrieF f a b -> m Source # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> TrieF f a b -> c Source # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> TrieF f a b -> c Source #
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 Source # first :: (a -> b) -> TrieF f a c -> TrieF f b c Source # second :: (b -> c) -> TrieF f a b -> TrieF f a c Source #
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) Source #
Foldable (f e) => Foldable1 (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods fold1 :: Semigroup m => TrieF f e m -> m Source # foldMap1 :: Semigroup m => (a -> m) -> TrieF f e a -> m Source # foldMap1' :: Semigroup m => (a -> m) -> TrieF f e a -> m Source # toNonEmpty :: TrieF f e a -> NonEmpty a Source # maximum :: Ord a => TrieF f e a -> a Source # minimum :: Ord a => TrieF f e a -> a Source # head :: TrieF f e a -> a Source # last :: TrieF f e a -> a Source # foldrMap1 :: (a -> b) -> (a -> b -> b) -> TrieF f e a -> b Source # foldlMap1' :: (a -> b) -> (b -> a -> b) -> TrieF f e a -> b Source # foldlMap1 :: (a -> b) -> (b -> a -> b) -> TrieF f e a -> b Source # foldrMap1' :: (a -> b) -> (a -> b -> b) -> TrieF f e a -> b Source #
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 Source # (<$) :: a -> TrieF f e b -> TrieF f e a Source #
Foldable (f e) => Foldable (TrieF f e) Source #
Instance details Defined in HGeometry.Trie.Type Methods fold :: Monoid m => TrieF f e m -> m Source # foldMap :: Monoid m => (a -> m) -> TrieF f e a -> m Source # foldMap' :: Monoid m => (a -> m) -> TrieF f e a -> m Source # foldr :: (a -> b -> b) -> b -> TrieF f e a -> b Source # foldr' :: (a -> b -> b) -> b -> TrieF f e a -> b Source # foldl :: (b -> a -> b) -> b -> TrieF f e a -> b Source # foldl' :: (b -> a -> b) -> b -> TrieF f e a -> b Source # foldr1 :: (a -> a -> a) -> TrieF f e a -> a Source # foldl1 :: (a -> a -> a) -> TrieF f e a -> a Source # toList :: TrieF f e a -> [a] Source # null :: TrieF f e a -> Bool Source # length :: TrieF f e a -> Int Source # elem :: Eq a => a -> TrieF f e a -> Bool Source # maximum :: Ord a => TrieF f e a -> a Source # minimum :: Ord a => TrieF f e a -> a Source # sum :: Num a => TrieF f e a -> a Source # product :: Num a => TrieF f e a -> a Source #
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) Source # sequenceA :: Applicative f0 => TrieF f e (f0 a) -> f0 (TrieF f e a) Source # mapM :: Monad m => (a -> m b) -> TrieF f e a -> m (TrieF f e b) Source # sequence :: Monad m => TrieF f e (m a) -> m (TrieF f e a) Source #
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 Source # show :: TrieF f e v -> String Source # showList :: [TrieF f e v] -> ShowS Source #
(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 Source # (/=) :: TrieF f e v -> TrieF f e v -> Bool Source #
(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 Source # (<) :: TrieF f e v -> TrieF f e v -> Bool Source # (<=) :: TrieF f e v -> TrieF f e v -> Bool Source # (>) :: TrieF f e v -> TrieF f e v -> Bool Source # (>=) :: TrieF f e v -> TrieF f e v -> Bool Source # max :: TrieF f e v -> TrieF f e v -> TrieF f e v Source # min :: TrieF f e v -> TrieF f e v -> TrieF f e v Source #

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