Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Trie.Map.Internal

Contents

Types

Description

This module exposes internal representation of TMap. TMap has one invariant condition:

Subtrees of an TMap should not be empty.

For example, consider following tree structure which is valid:

> fromList [("a",1), ("aa", 2), ("bc", 3)]
Root
  'a' -> 1
    'a' -> 2
  'b' ->
    'c' -> 3

Adding redundant node which represents empty map does not change what an TMap represents.

Root
  'a' -> 1
    'a' -> 2
  'b' ->
    'c' -> 3
  'd' ->
    'e' ->
      'f' ->

But such TMap should not exist because it confuses Eq and Ord instances and null function.

Synopsis

newtype TMap c a = TMap {
- getNode :: Node c a (TMap c a)
}
data Node c a r = Node !(Maybe a) !(Map c r)
foldTMap :: (Node c a r -> r) -> TMap c a -> r

Types

newtype TMap c a Source #

Mapping from [c] to a implemented as a trie. This type serves the almost same purpose of Map [c] a, but can be looked up more efficiently.

Constructors

TMap
Fields getNode :: Node c a (TMap c a)

Instances

Instances details

Eq2 TMap Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> TMap a c -> TMap b d -> Bool #
Ord2 TMap Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> TMap a c -> TMap b d -> Ordering #
Show2 TMap Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> TMap a b -> ShowS # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [TMap a b] -> ShowS #
Hashable2 TMap Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> TMap a b -> Int #
Foldable (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods fold :: Monoid m => TMap c m -> m # foldMap :: Monoid m => (a -> m) -> TMap c a -> m # foldMap' :: Monoid m => (a -> m) -> TMap c a -> m # foldr :: (a -> b -> b) -> b -> TMap c a -> b # foldr' :: (a -> b -> b) -> b -> TMap c a -> b # foldl :: (b -> a -> b) -> b -> TMap c a -> b # foldl' :: (b -> a -> b) -> b -> TMap c a -> b # foldr1 :: (a -> a -> a) -> TMap c a -> a # foldl1 :: (a -> a -> a) -> TMap c a -> a # toList :: TMap c a -> [a] # null :: TMap c a -> Bool # length :: TMap c a -> Int # elem :: Eq a => a -> TMap c a -> Bool # maximum :: Ord a => TMap c a -> a # minimum :: Ord a => TMap c a -> a # sum :: Num a => TMap c a -> a # product :: Num a => TMap c a -> a #
Eq c => Eq1 (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftEq :: (a -> b -> Bool) -> TMap c a -> TMap c b -> Bool #
Ord c => Ord1 (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftCompare :: (a -> b -> Ordering) -> TMap c a -> TMap c b -> Ordering #
Show c => Show1 (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> TMap c a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [TMap c a] -> ShowS #
Traversable (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods traverse :: Applicative f => (a -> f b) -> TMap c a -> f (TMap c b) # sequenceA :: Applicative f => TMap c (f a) -> f (TMap c a) # mapM :: Monad m => (a -> m b) -> TMap c a -> m (TMap c b) # sequence :: Monad m => TMap c (m a) -> m (TMap c a) #
Functor (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods fmap :: (a -> b) -> TMap c a -> TMap c b # (<$) :: a -> TMap c b -> TMap c a #
Hashable c => Hashable1 (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftHashWithSalt :: (Int -> a -> Int) -> Int -> TMap c a -> Int #
Eq c => Matchable (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods zipMatch :: TMap c a -> TMap c b -> Maybe (TMap c (a, b)) # zipMatchWith :: (a -> b -> Maybe c0) -> TMap c a -> TMap c b -> Maybe (TMap c c0) #
Ord c => Align (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods nil :: TMap c a #
Ord c => Semialign (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods align :: TMap c a -> TMap c b -> TMap c (These a b) # alignWith :: (These a b -> c0) -> TMap c a -> TMap c b -> TMap c c0 #
Ord c => Zip (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods zip :: TMap c a -> TMap c b -> TMap c (a, b) # zipWith :: (a -> b -> c0) -> TMap c a -> TMap c b -> TMap c c0 #
Ord c => Filterable (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods mapMaybe :: (a -> Maybe b) -> TMap c a -> TMap c b # catMaybes :: TMap c (Maybe a) -> TMap c a # filter :: (a -> Bool) -> TMap c a -> TMap c a # drain :: TMap c a -> TMap c b #
Ord c => Witherable (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods wither :: Applicative f => (a -> f (Maybe b)) -> TMap c a -> f (TMap c b) # witherM :: Monad m => (a -> m (Maybe b)) -> TMap c a -> m (TMap c b) # filterA :: Applicative f => (a -> f Bool) -> TMap c a -> f (TMap c a) # witherMap :: Applicative m => (TMap c b -> r) -> (a -> m (Maybe b)) -> TMap c a -> m r #
FoldableWithIndex [c] (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods ifoldMap :: Monoid m => ([c] -> a -> m) -> TMap c a -> m # ifoldMap' :: Monoid m => ([c] -> a -> m) -> TMap c a -> m # ifoldr :: ([c] -> a -> b -> b) -> b -> TMap c a -> b # ifoldl :: ([c] -> b -> a -> b) -> b -> TMap c a -> b # ifoldr' :: ([c] -> a -> b -> b) -> b -> TMap c a -> b # ifoldl' :: ([c] -> b -> a -> b) -> b -> TMap c a -> b #
FunctorWithIndex [c] (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods imap :: ([c] -> a -> b) -> TMap c a -> TMap c b #
TraversableWithIndex [c] (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods itraverse :: Applicative f => ([c] -> a -> f b) -> TMap c a -> f (TMap c b) #
Ord c => FilterableWithIndex [c] (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods imapMaybe :: ([c] -> a -> Maybe b) -> TMap c a -> TMap c b # ifilter :: ([c] -> a -> Bool) -> TMap c a -> TMap c a #
Ord c => WitherableWithIndex [c] (TMap c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods iwither :: Applicative f => ([c] -> a -> f (Maybe b)) -> TMap c a -> f (TMap c b) # iwitherM :: Monad m => ([c] -> a -> m (Maybe b)) -> TMap c a -> m (TMap c b) # ifilterA :: Applicative f => ([c] -> a -> f Bool) -> TMap c a -> f (TMap c a) #
(Ord c, Semigroup a) => Monoid (TMap c a) Source #	`unionWith`-based
Instance details Defined in Data.Trie.Map.Hidden Methods mempty :: TMap c a # mappend :: TMap c a -> TMap c a -> TMap c a # mconcat :: [TMap c a] -> TMap c a #
(Ord c, Semigroup a) => Semigroup (TMap c a) Source #	`unionWith`-based
Instance details Defined in Data.Trie.Map.Hidden Methods (<>) :: TMap c a -> TMap c a -> TMap c a # sconcat :: NonEmpty (TMap c a) -> TMap c a # stimes :: Integral b => b -> TMap c a -> TMap c a #
Ord c => IsList (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Associated Types type Item (TMap c a) # Methods fromList :: [Item (TMap c a)] -> TMap c a # fromListN :: Int -> [Item (TMap c a)] -> TMap c a # toList :: TMap c a -> [Item (TMap c a)] #
(Show c, Show a) => Show (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods showsPrec :: Int -> TMap c a -> ShowS # show :: TMap c a -> String # showList :: [TMap c a] -> ShowS #
(NFData c, NFData a) => NFData (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods rnf :: TMap c a -> () #
(Eq a, Eq c) => Eq (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods (==) :: TMap c a -> TMap c a -> Bool # (/=) :: TMap c a -> TMap c a -> Bool #
(Ord a, Ord c) => Ord (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods compare :: TMap c a -> TMap c a -> Ordering # (<) :: TMap c a -> TMap c a -> Bool # (<=) :: TMap c a -> TMap c a -> Bool # (>) :: TMap c a -> TMap c a -> Bool # (>=) :: TMap c a -> TMap c a -> Bool # max :: TMap c a -> TMap c a -> TMap c a # min :: TMap c a -> TMap c a -> TMap c a #
(Hashable c, Hashable a) => Hashable (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods hashWithSalt :: Int -> TMap c a -> Int # hash :: TMap c a -> Int #
type Item (TMap c a) Source #
Instance details Defined in Data.Trie.Map.Hidden type Item (TMap c a) = ([c], a)

data Node c a r Source #

Constructors

Node !(Maybe a) !(Map c r)

Instances

Instances details

Eq c => Eq2 (Node c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftEq2 :: (a -> b -> Bool) -> (c0 -> d -> Bool) -> Node c a c0 -> Node c b d -> Bool #
Ord c => Ord2 (Node c) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftCompare2 :: (a -> b -> Ordering) -> (c0 -> d -> Ordering) -> Node c a c0 -> Node c b d -> Ordering #
Foldable (Node c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods fold :: Monoid m => Node c a m -> m # foldMap :: Monoid m => (a0 -> m) -> Node c a a0 -> m # foldMap' :: Monoid m => (a0 -> m) -> Node c a a0 -> m # foldr :: (a0 -> b -> b) -> b -> Node c a a0 -> b # foldr' :: (a0 -> b -> b) -> b -> Node c a a0 -> b # foldl :: (b -> a0 -> b) -> b -> Node c a a0 -> b # foldl' :: (b -> a0 -> b) -> b -> Node c a a0 -> b # foldr1 :: (a0 -> a0 -> a0) -> Node c a a0 -> a0 # foldl1 :: (a0 -> a0 -> a0) -> Node c a a0 -> a0 # toList :: Node c a a0 -> [a0] # null :: Node c a a0 -> Bool # length :: Node c a a0 -> Int # elem :: Eq a0 => a0 -> Node c a a0 -> Bool # maximum :: Ord a0 => Node c a a0 -> a0 # minimum :: Ord a0 => Node c a a0 -> a0 # sum :: Num a0 => Node c a a0 -> a0 # product :: Num a0 => Node c a a0 -> a0 #
(Eq c, Eq a) => Eq1 (Node c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftEq :: (a0 -> b -> Bool) -> Node c a a0 -> Node c a b -> Bool #
(Ord c, Ord a) => Ord1 (Node c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods liftCompare :: (a0 -> b -> Ordering) -> Node c a a0 -> Node c a b -> Ordering #
Traversable (Node c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods traverse :: Applicative f => (a0 -> f b) -> Node c a a0 -> f (Node c a b) # sequenceA :: Applicative f => Node c a (f a0) -> f (Node c a a0) # mapM :: Monad m => (a0 -> m b) -> Node c a a0 -> m (Node c a b) # sequence :: Monad m => Node c a (m a0) -> m (Node c a a0) #
Functor (Node c a) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods fmap :: (a0 -> b) -> Node c a a0 -> Node c a b # (<$) :: a0 -> Node c a b -> Node c a a0 #
(Show a, Show c, Show r) => Show (Node c a r) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods showsPrec :: Int -> Node c a r -> ShowS # show :: Node c a r -> String # showList :: [Node c a r] -> ShowS #
(NFData c, NFData a, NFData r) => NFData (Node c a r) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods rnf :: Node c a r -> () #
(Eq a, Eq c, Eq r) => Eq (Node c a r) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods (==) :: Node c a r -> Node c a r -> Bool # (/=) :: Node c a r -> Node c a r -> Bool #
(Ord a, Ord c, Ord r) => Ord (Node c a r) Source #
Instance details Defined in Data.Trie.Map.Hidden Methods compare :: Node c a r -> Node c a r -> Ordering # (<) :: Node c a r -> Node c a r -> Bool # (<=) :: Node c a r -> Node c a r -> Bool # (>) :: Node c a r -> Node c a r -> Bool # (>=) :: Node c a r -> Node c a r -> Bool # max :: Node c a r -> Node c a r -> Node c a r # min :: Node c a r -> Node c a r -> Node c a r #

foldTMap :: (Node c a r -> r) -> TMap c a -> r Source #