trie-simple-0.4.1.1: Simple Map-based Trie

Safe HaskellSafe
LanguageHaskell2010

Data.Trie.Map.Internal

Contents

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

Types

newtype TMap c a Source #

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

Constructors

TMap 

Fields

Instances
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 #

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 #

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 #

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) #

(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 #

(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 #

(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, 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 #

(NFData c, NFData a) => NFData (TMap c a) Source # 
Instance details

Defined in Data.Trie.Map.Hidden

Methods

rnf :: TMap c a -> () #

data Node c a r Source #

Constructors

Node !(Maybe a) !(Map c r) 
Instances
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 #

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 #

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 #

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) #

(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 #

(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 -> () #

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