Data.Trie.Set.Internal

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

• Subtrees of an TSet should not be empty.

For example, consider following tree structure which is valid:

> fromList ["a", "aa", "bc"]
Root -> False
  'a' -> True
    'a' -> True
  'b' -> False
    'c' -> True

Adding redundant node which represents empty set does not change what an TSet represents.

Root -> False
  'a' -> True
    'a' -> True
  'b' -> False
    'c' -> True
  'd' -> False
    'e' -> False
      'f' -> False

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

Documentation

newtype TSet c

Constructors

TSet

Fields

• getNode :: Node c (TSet c)

Instances

Eq1 TSet

Defined in Data.Trie.Set.Hidden

Methods

liftEq :: (a -> b -> Bool) -> TSet a -> TSet b -> Bool

Ord1 TSet

Defined in Data.Trie.Set.Hidden

Methods

liftCompare :: (a -> b -> Ordering) -> TSet a -> TSet b -> Ordering

Show1 TSet

Defined in Data.Trie.Set.Hidden

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> TSet a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [TSet a] -> ShowS

Hashable1 TSet

Defined in Data.Trie.Set.Hidden

Methods

liftHashWithSalt :: (Int -> a -> Int) -> Int -> TSet a -> Int

Ord c => Monoid (TSet c)

Monoid(empty, union)

Defined in Data.Trie.Set.Hidden

Methods

mempty :: TSet c

mappend :: TSet c -> TSet c -> TSet c

mconcat :: [TSet c] -> TSet c

Ord c => Semigroup (TSet c)

Semigroup(union)

Defined in Data.Trie.Set.Hidden

Methods

(<>) :: TSet c -> TSet c -> TSet c

sconcat :: NonEmpty (TSet c) -> TSet c

stimes :: Integral b => b -> TSet c -> TSet c

Ord c => IsList (TSet c)

Defined in Data.Trie.Set.Hidden

Associated Types

type Item (TSet c)

Methods

fromList :: [Item (TSet c)] -> TSet c

fromListN :: Int -> [Item (TSet c)] -> TSet c

toList :: TSet c -> [Item (TSet c)]

Show c => Show (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

showsPrec :: Int -> TSet c -> ShowS

show :: TSet c -> String

showList :: [TSet c] -> ShowS

NFData c => NFData (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

rnf :: TSet c -> ()

Eq c => Eq (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

(==) :: TSet c -> TSet c -> Bool

(/=) :: TSet c -> TSet c -> Bool

Ord c => Ord (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

compare :: TSet c -> TSet c -> Ordering

(<) :: TSet c -> TSet c -> Bool

(<=) :: TSet c -> TSet c -> Bool

(>) :: TSet c -> TSet c -> Bool

(>=) :: TSet c -> TSet c -> Bool

max :: TSet c -> TSet c -> TSet c

min :: TSet c -> TSet c -> TSet c

Hashable c => Hashable (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

hashWithSalt :: Int -> TSet c -> Int

hash :: TSet c -> Int

type Item (TSet c)

Defined in Data.Trie.Set.Hidden

type Item (TSet c) = [c]

data Node c r

Constructors

Node !Bool !(Map c r)

Instances

Foldable (Node c)

Defined in Data.Trie.Set.Hidden

Methods

fold :: Monoid m => Node c m -> m

foldMap :: Monoid m => (a -> m) -> Node c a -> m

foldMap' :: Monoid m => (a -> m) -> Node c a -> m

foldr :: (a -> b -> b) -> b -> Node c a -> b

foldr' :: (a -> b -> b) -> b -> Node c a -> b

foldl :: (b -> a -> b) -> b -> Node c a -> b

foldl' :: (b -> a -> b) -> b -> Node c a -> b

foldr1 :: (a -> a -> a) -> Node c a -> a

foldl1 :: (a -> a -> a) -> Node c a -> a

toList :: Node c a -> [a]

null :: Node c a -> Bool

length :: Node c a -> Int

elem :: Eq a => a -> Node c a -> Bool

maximum :: Ord a => Node c a -> a

minimum :: Ord a => Node c a -> a

sum :: Num a => Node c a -> a

product :: Num a => Node c a -> a

Traversable (Node c)

Defined in Data.Trie.Set.Hidden

Methods

traverse :: Applicative f => (a -> f b) -> Node c a -> f (Node c b)

sequenceA :: Applicative f => Node c (f a) -> f (Node c a)

mapM :: Monad m => (a -> m b) -> Node c a -> m (Node c b)

sequence :: Monad m => Node c (m a) -> m (Node c a)

Functor (Node c)

Defined in Data.Trie.Set.Hidden

Methods

fmap :: (a -> b) -> Node c a -> Node c b

(<$) :: a -> Node c b -> Node c a

(Show c, Show r) => Show (Node c r)

Defined in Data.Trie.Set.Hidden

Methods

showsPrec :: Int -> Node c r -> ShowS

show :: Node c r -> String

showList :: [Node c r] -> ShowS

(NFData c, NFData r) => NFData (Node c r)

Defined in Data.Trie.Set.Hidden

Methods

rnf :: Node c r -> ()

(Eq c, Eq r) => Eq (Node c r)

Defined in Data.Trie.Set.Hidden

Methods

(==) :: Node c r -> Node c r -> Bool

(/=) :: Node c r -> Node c r -> Bool

(Ord c, Ord r) => Ord (Node c r)

Defined in Data.Trie.Set.Hidden

Methods

compare :: Node c r -> Node c r -> Ordering

(<) :: Node c r -> Node c r -> Bool

(<=) :: Node c r -> Node c r -> Bool

(>) :: Node c r -> Node c r -> Bool

(>=) :: Node c r -> Node c r -> Bool

max :: Node c r -> Node c r -> Node c r

min :: Node c r -> Node c r -> Node c r

foldTSet :: (Node c r -> r) -> TSet c -> r

paraTSet :: (Node c (TSet c, r) -> r) -> TSet c -> r