Data.Trie.Map

One Step

data MapChildren c p a

Constructors

MapChildren

Fields

• mapNode :: !(Maybe a)
• mapChildren :: !(Maybe (c p a))

Instances

Functor (c p) => Functor (MapChildren c p)

Defined in Data.Trie.Map

Methods

fmap :: (a -> b) -> MapChildren c p a -> MapChildren c p b

(<$) :: a -> MapChildren c p b -> MapChildren c p a

Foldable (c p) => Foldable (MapChildren c p)

Defined in Data.Trie.Map

Methods

fold :: Monoid m => MapChildren c p m -> m

foldMap :: Monoid m => (a -> m) -> MapChildren c p a -> m

foldr :: (a -> b -> b) -> b -> MapChildren c p a -> b

foldr' :: (a -> b -> b) -> b -> MapChildren c p a -> b

foldl :: (b -> a -> b) -> b -> MapChildren c p a -> b

foldl' :: (b -> a -> b) -> b -> MapChildren c p a -> b

foldr1 :: (a -> a -> a) -> MapChildren c p a -> a

foldl1 :: (a -> a -> a) -> MapChildren c p a -> a

toList :: MapChildren c p a -> [a]

null :: MapChildren c p a -> Bool

length :: MapChildren c p a -> Int

elem :: Eq a => a -> MapChildren c p a -> Bool

maximum :: Ord a => MapChildren c p a -> a

minimum :: Ord a => MapChildren c p a -> a

sum :: Num a => MapChildren c p a -> a

product :: Num a => MapChildren c p a -> a

Traversable (c p) => Traversable (MapChildren c p)

Defined in Data.Trie.Map

Methods

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

sequenceA :: Applicative f => MapChildren c p (f a) -> f (MapChildren c p a)

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

sequence :: Monad m => MapChildren c p (m a) -> m (MapChildren c p a)

(Eq a, Eq (c p a)) => Eq (MapChildren c p a)

Defined in Data.Trie.Map

Methods

(==) :: MapChildren c p a -> MapChildren c p a -> Bool

(/=) :: MapChildren c p a -> MapChildren c p a -> Bool

(Typeable c, Typeable p, Data a, Data (c p a)) => Data (MapChildren c p a)

Defined in Data.Trie.Map

Methods

gfoldl :: (forall d b. Data d => c0 (d -> b) -> d -> c0 b) -> (forall g. g -> c0 g) -> MapChildren c p a -> c0 (MapChildren c p a)

gunfold :: (forall b r. Data b => c0 (b -> r) -> c0 r) -> (forall r. r -> c0 r) -> Constr -> c0 (MapChildren c p a)

toConstr :: MapChildren c p a -> Constr

dataTypeOf :: MapChildren c p a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c0 (t d)) -> Maybe (c0 (MapChildren c p a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c0 (t d e)) -> Maybe (c0 (MapChildren c p a))

gmapT :: (forall b. Data b => b -> b) -> MapChildren c p a -> MapChildren c p a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MapChildren c p a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MapChildren c p a -> r

gmapQ :: (forall d. Data d => d -> u) -> MapChildren c p a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> MapChildren c p a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> MapChildren c p a -> m (MapChildren c p a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MapChildren c p a -> m (MapChildren c p a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MapChildren c p a -> m (MapChildren c p a)

(Ord a, Ord (c p a)) => Ord (MapChildren c p a)

Defined in Data.Trie.Map

Methods

compare :: MapChildren c p a -> MapChildren c p a -> Ordering

(<) :: MapChildren c p a -> MapChildren c p a -> Bool

(<=) :: MapChildren c p a -> MapChildren c p a -> Bool

(>) :: MapChildren c p a -> MapChildren c p a -> Bool

(>=) :: MapChildren c p a -> MapChildren c p a -> Bool

max :: MapChildren c p a -> MapChildren c p a -> MapChildren c p a

min :: MapChildren c p a -> MapChildren c p a -> MapChildren c p a

(Show a, Show (c p a)) => Show (MapChildren c p a)

Defined in Data.Trie.Map

Methods

showsPrec :: Int -> MapChildren c p a -> ShowS

show :: MapChildren c p a -> String

showList :: [MapChildren c p a] -> ShowS

Generic (MapChildren c p a)

Defined in Data.Trie.Map

Associated Types

type Rep (MapChildren c p a) :: Type -> Type

Methods

from :: MapChildren c p a -> Rep (MapChildren c p a) x

to :: Rep (MapChildren c p a) x -> MapChildren c p a

Semigroup (c p a) => Semigroup (MapChildren c p a)

Defined in Data.Trie.Map

Methods

(<>) :: MapChildren c p a -> MapChildren c p a -> MapChildren c p a

sconcat :: NonEmpty (MapChildren c p a) -> MapChildren c p a

stimes :: Integral b => b -> MapChildren c p a -> MapChildren c p a

Monoid (c p a) => Monoid (MapChildren c p a)

Defined in Data.Trie.Map

Methods

mempty :: MapChildren c p a

mappend :: MapChildren c p a -> MapChildren c p a -> MapChildren c p a

mconcat :: [MapChildren c p a] -> MapChildren c p a

(Arbitrary a, Arbitrary p, Arbitrary (c p a)) => Arbitrary (MapChildren c p a)

Defined in Data.Trie.Map

Methods

arbitrary :: Gen (MapChildren c p a)

shrink :: MapChildren c p a -> [MapChildren c p a]

(NFData (c p a), NFData p, NFData a) => NFData (MapChildren c p a)

Defined in Data.Trie.Map

Methods

rnf :: MapChildren c p a -> ()

type Rep (MapChildren c p a)

Defined in Data.Trie.Map

type Rep (MapChildren c p a) = D1 (MetaData "MapChildren" "Data.Trie.Map" "tries-0.0.6.1-Bv92dt7msP1Givg7qeJP0r" False) (C1 (MetaCons "MapChildren" PrefixI True) (S1 (MetaSel (Just "mapNode") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Maybe a)) :*: S1 (MetaSel (Just "mapChildren") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Maybe (c p a)))))

newtype MapStep c p a

Constructors

MapStep

Fields

• unMapStep :: Map p (MapChildren c p a)

Instances

(Ord p, Trie NonEmpty p c) => Trie NonEmpty p (MapStep c)

No insertion instance - requires children nodes to be a monoid. Use Data.Trie.Map.insert instead.

Defined in Data.Trie.Map

Methods

lookup :: NonEmpty p -> MapStep c p a -> Maybe a

insert :: NonEmpty p -> a -> MapStep c p a -> MapStep c p a

delete :: NonEmpty p -> MapStep c p a -> MapStep c p a

Functor (c p) => Functor (MapStep c p)

Defined in Data.Trie.Map

Methods

fmap :: (a -> b) -> MapStep c p a -> MapStep c p b

(<$) :: a -> MapStep c p b -> MapStep c p a

Foldable (c p) => Foldable (MapStep c p)

Defined in Data.Trie.Map

Methods

fold :: Monoid m => MapStep c p m -> m

foldMap :: Monoid m => (a -> m) -> MapStep c p a -> m

foldr :: (a -> b -> b) -> b -> MapStep c p a -> b

foldr' :: (a -> b -> b) -> b -> MapStep c p a -> b

foldl :: (b -> a -> b) -> b -> MapStep c p a -> b

foldl' :: (b -> a -> b) -> b -> MapStep c p a -> b

foldr1 :: (a -> a -> a) -> MapStep c p a -> a

foldl1 :: (a -> a -> a) -> MapStep c p a -> a

toList :: MapStep c p a -> [a]

null :: MapStep c p a -> Bool

length :: MapStep c p a -> Int

elem :: Eq a => a -> MapStep c p a -> Bool

maximum :: Ord a => MapStep c p a -> a

minimum :: Ord a => MapStep c p a -> a

sum :: Num a => MapStep c p a -> a

product :: Num a => MapStep c p a -> a

Traversable (c p) => Traversable (MapStep c p)

Defined in Data.Trie.Map

Methods

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

sequenceA :: Applicative f => MapStep c p (f a) -> f (MapStep c p a)

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

sequence :: Monad m => MapStep c p (m a) -> m (MapStep c p a)

(Eq p, Eq a, Eq (c p a)) => Eq (MapStep c p a)

Defined in Data.Trie.Map

Methods

(==) :: MapStep c p a -> MapStep c p a -> Bool

(/=) :: MapStep c p a -> MapStep c p a -> Bool

(Typeable c, Data p, Data a, Data (c p a), Ord p) => Data (MapStep c p a)

Defined in Data.Trie.Map

Methods

gfoldl :: (forall d b. Data d => c0 (d -> b) -> d -> c0 b) -> (forall g. g -> c0 g) -> MapStep c p a -> c0 (MapStep c p a)

gunfold :: (forall b r. Data b => c0 (b -> r) -> c0 r) -> (forall r. r -> c0 r) -> Constr -> c0 (MapStep c p a)

toConstr :: MapStep c p a -> Constr

dataTypeOf :: MapStep c p a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c0 (t d)) -> Maybe (c0 (MapStep c p a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c0 (t d e)) -> Maybe (c0 (MapStep c p a))

gmapT :: (forall b. Data b => b -> b) -> MapStep c p a -> MapStep c p a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MapStep c p a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MapStep c p a -> r

gmapQ :: (forall d. Data d => d -> u) -> MapStep c p a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> MapStep c p a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> MapStep c p a -> m (MapStep c p a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MapStep c p a -> m (MapStep c p a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MapStep c p a -> m (MapStep c p a)

(Ord p, Ord a, Ord (c p a)) => Ord (MapStep c p a)

Defined in Data.Trie.Map

Methods

compare :: MapStep c p a -> MapStep c p a -> Ordering

(<) :: MapStep c p a -> MapStep c p a -> Bool

(<=) :: MapStep c p a -> MapStep c p a -> Bool

(>) :: MapStep c p a -> MapStep c p a -> Bool

(>=) :: MapStep c p a -> MapStep c p a -> Bool

max :: MapStep c p a -> MapStep c p a -> MapStep c p a

min :: MapStep c p a -> MapStep c p a -> MapStep c p a

(Show p, Show a, Show (c p a)) => Show (MapStep c p a)

Defined in Data.Trie.Map

Methods

showsPrec :: Int -> MapStep c p a -> ShowS

show :: MapStep c p a -> String

showList :: [MapStep c p a] -> ShowS

Generic (MapStep c p a)

Defined in Data.Trie.Map

Associated Types

type Rep (MapStep c p a) :: Type -> Type

Methods

from :: MapStep c p a -> Rep (MapStep c p a) x

to :: Rep (MapStep c p a) x -> MapStep c p a

(Ord s, Semigroup (c s a)) => Semigroup (MapStep c s a)

Defined in Data.Trie.Map

Methods

(<>) :: MapStep c s a -> MapStep c s a -> MapStep c s a

sconcat :: NonEmpty (MapStep c s a) -> MapStep c s a

stimes :: Integral b => b -> MapStep c s a -> MapStep c s a

(Ord s, Monoid (c s a)) => Monoid (MapStep c s a)

Defined in Data.Trie.Map

Methods

mempty :: MapStep c s a

mappend :: MapStep c s a -> MapStep c s a -> MapStep c s a

mconcat :: [MapStep c s a] -> MapStep c s a

(Arbitrary a, Arbitrary p, Arbitrary (c p a), Ord p) => Arbitrary (MapStep c p a)

Defined in Data.Trie.Map

Methods

arbitrary :: Gen (MapStep c p a)

shrink :: MapStep c p a -> [MapStep c p a]

(NFData (c p a), NFData p, NFData a) => NFData (MapStep c p a)

Defined in Data.Trie.Map

Methods

rnf :: MapStep c p a -> ()

type Rep (MapStep c p a)

Defined in Data.Trie.Map

type Rep (MapStep c p a) = D1 (MetaData "MapStep" "Data.Trie.Map" "tries-0.0.6.1-Bv92dt7msP1Givg7qeJP0r" True) (C1 (MetaCons "MapStep" PrefixI True) (S1 (MetaSel (Just "unMapStep") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map p (MapChildren c p a)))))

insert :: (Ord p, Trie NonEmpty p c, Monoid (c p a)) => NonEmpty p -> a -> MapStep c p a -> MapStep c p a

empty :: MapStep c s a

singleton :: s -> a -> MapStep c s a

Fixpoint of Steps

newtype MapTrie s a

Constructors

MapTrie

Fields

• unMapTrie :: MapStep MapTrie s a

Instances

Ord s => Trie NonEmpty s MapTrie

Defined in Data.Trie.Map

Methods

lookup :: NonEmpty s -> MapTrie s a -> Maybe a

insert :: NonEmpty s -> a -> MapTrie s a -> MapTrie s a

delete :: NonEmpty s -> MapTrie s a -> MapTrie s a

Functor (MapTrie s)

Defined in Data.Trie.Map

Methods

fmap :: (a -> b) -> MapTrie s a -> MapTrie s b

(<$) :: a -> MapTrie s b -> MapTrie s a

Foldable (MapTrie s)

Defined in Data.Trie.Map

Methods

fold :: Monoid m => MapTrie s m -> m

foldMap :: Monoid m => (a -> m) -> MapTrie s a -> m

foldr :: (a -> b -> b) -> b -> MapTrie s a -> b

foldr' :: (a -> b -> b) -> b -> MapTrie s a -> b

foldl :: (b -> a -> b) -> b -> MapTrie s a -> b

foldl' :: (b -> a -> b) -> b -> MapTrie s a -> b

foldr1 :: (a -> a -> a) -> MapTrie s a -> a

foldl1 :: (a -> a -> a) -> MapTrie s a -> a

toList :: MapTrie s a -> [a]

null :: MapTrie s a -> Bool

length :: MapTrie s a -> Int

elem :: Eq a => a -> MapTrie s a -> Bool

maximum :: Ord a => MapTrie s a -> a

minimum :: Ord a => MapTrie s a -> a

sum :: Num a => MapTrie s a -> a

product :: Num a => MapTrie s a -> a

Traversable (MapTrie s)

Defined in Data.Trie.Map

Methods

traverse :: Applicative f => (a -> f b) -> MapTrie s a -> f (MapTrie s b)

sequenceA :: Applicative f => MapTrie s (f a) -> f (MapTrie s a)

mapM :: Monad m => (a -> m b) -> MapTrie s a -> m (MapTrie s b)

sequence :: Monad m => MapTrie s (m a) -> m (MapTrie s a)

Ord s => Lookup (MapTrie s)

Defined in Data.Trie.Map

Methods

lookup :: Key (MapTrie s) -> MapTrie s a -> Maybe a

(Eq s, Eq a) => Eq (MapTrie s a)

Defined in Data.Trie.Map

Methods

(==) :: MapTrie s a -> MapTrie s a -> Bool

(/=) :: MapTrie s a -> MapTrie s a -> Bool

(Ord s, Ord a) => Ord (MapTrie s a)

Defined in Data.Trie.Map

Methods

compare :: MapTrie s a -> MapTrie s a -> Ordering

(<) :: MapTrie s a -> MapTrie s a -> Bool

(<=) :: MapTrie s a -> MapTrie s a -> Bool

(>) :: MapTrie s a -> MapTrie s a -> Bool

(>=) :: MapTrie s a -> MapTrie s a -> Bool

max :: MapTrie s a -> MapTrie s a -> MapTrie s a

min :: MapTrie s a -> MapTrie s a -> MapTrie s a

(Show s, Show a) => Show (MapTrie s a)

Defined in Data.Trie.Map

Methods

showsPrec :: Int -> MapTrie s a -> ShowS

show :: MapTrie s a -> String

showList :: [MapTrie s a] -> ShowS

Ord s => Semigroup (MapTrie s a)

Defined in Data.Trie.Map

Methods

(<>) :: MapTrie s a -> MapTrie s a -> MapTrie s a

sconcat :: NonEmpty (MapTrie s a) -> MapTrie s a

stimes :: Integral b => b -> MapTrie s a -> MapTrie s a

Ord s => Monoid (MapTrie s a)

Defined in Data.Trie.Map

Methods

mempty :: MapTrie s a

mappend :: MapTrie s a -> MapTrie s a -> MapTrie s a

mconcat :: [MapTrie s a] -> MapTrie s a

(Arbitrary a, Arbitrary s, Ord s) => Arbitrary (MapTrie s a)

Defined in Data.Trie.Map

Methods

arbitrary :: Gen (MapTrie s a)

shrink :: MapTrie s a -> [MapTrie s a]

type Key (MapTrie s)

Defined in Data.Trie.Map

type Key (MapTrie s) = NonEmpty s

Conversion

keys :: forall s a. Ord s => MapTrie s a -> [NonEmpty s]

elems :: MapTrie s a -> [a]

Query

subtrie :: Ord s => NonEmpty s -> MapTrie s a -> Maybe (MapTrie s a)

match :: Ord s => NonEmpty s -> MapTrie s a -> Maybe (NonEmpty s, a, [s])

matches :: Ord s => NonEmpty s -> MapTrie s a -> [(NonEmpty s, a, [s])]

Returns a list of all the nodes along the path to the furthest point in the query, in order of the path walked from the root to the furthest point.