-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Various trie implementations in Haskell
--   
--   Please see the README on Github at
--   <a>https://git.localcooking.com/tooling/tries#readme</a>
@package tries
@version 0.0.5

module Data.Trie.Class

-- | Class representing tries with single-threaded insertion, deletion, and
--   lookup. <tt>forall ts ps a. isJust $ lookupPath ps (insertPath ps a
--   ts)</tt> <tt>forall ts ps. isNothing $ lookupPath ps (deletePath ps
--   ts)</tt>
class Trie p s t | t -> p
lookup :: Trie p s t => p s -> t s a -> Maybe a
insert :: Trie p s t => p s -> a -> t s a -> t s a
delete :: Trie p s t => p s -> t s a -> t s a
member :: Trie p s t => p s -> t s a -> Bool
notMember :: Trie p s t => p s -> t s a -> Bool
fromFoldable :: (Foldable f, Monoid (t s a), Trie p s t) => f (p s, a) -> t s a

-- | Embeds an empty ByteString passed around for type inference.
newtype BSTrie q a
BSTrie :: (q, Trie a) -> BSTrie q a
[unBSTrie] :: BSTrie q a -> (q, Trie a)
makeBSTrie :: Trie a -> BSTrie ByteString a
getBSTrie :: BSTrie ByteString a -> Trie a
instance Data.Trie.Class.Trie Data.Functor.Identity.Identity Data.ByteString.Internal.ByteString Data.Trie.Class.BSTrie

module Data.Trie.HashMap
data HashMapChildren c p a
HashMapChildren :: !(Maybe a) -> !(Maybe (c p a)) -> HashMapChildren c p a
[hashMapNode] :: HashMapChildren c p a -> !(Maybe a)
[hashMapChildren] :: HashMapChildren c p a -> !(Maybe (c p a))
newtype HashMapStep c p a
HashMapStep :: HashMap p (HashMapChildren c p a) -> HashMapStep c p a
[unHashMapStep] :: HashMapStep c p a -> HashMap p (HashMapChildren c p a)
insert :: (Hashable p, Eq p, Trie NonEmpty p c, Monoid (c p a)) => NonEmpty p -> a -> HashMapStep c p a -> HashMapStep c p a
empty :: HashMapStep c p a
singleton :: Hashable p => p -> a -> HashMapStep c p a
newtype HashMapTrie p a
HashMapTrie :: HashMapStep HashMapTrie p a -> HashMapTrie p a
[unHashMapTrie] :: HashMapTrie p a -> HashMapStep HashMapTrie p a
keys :: (Hashable p, Eq p) => HashMapTrie p a -> [NonEmpty p]
elems :: HashMapTrie p a -> [a]
subtrie :: (Hashable p, Eq p) => NonEmpty p -> HashMapTrie p a -> Maybe (HashMapTrie p a)
match :: (Hashable p, Eq p) => NonEmpty p -> HashMapTrie p a -> Maybe (NonEmpty p, a, [p])

-- | 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.
matches :: (Hashable p, Eq p) => NonEmpty p -> HashMapTrie p a -> [(NonEmpty p, a, [p])]
instance (GHC.Classes.Eq p, Data.Hashable.Class.Hashable p, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary a) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.HashMap.HashMapTrie p a)
instance (GHC.Classes.Eq p, Data.Hashable.Class.Hashable p) => GHC.Base.Monoid (Data.Trie.HashMap.HashMapTrie p a)
instance Data.Traversable.Traversable (Data.Trie.HashMap.HashMapTrie p)
instance Data.Foldable.Foldable (Data.Trie.HashMap.HashMapTrie p)
instance GHC.Base.Functor (Data.Trie.HashMap.HashMapTrie p)
instance (GHC.Classes.Eq a, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.Trie.HashMap.HashMapTrie p a)
instance (GHC.Show.Show a, GHC.Show.Show p) => GHC.Show.Show (Data.Trie.HashMap.HashMapTrie p a)
instance (Data.Hashable.Class.Hashable p, GHC.Classes.Eq p, Data.Data.Data (c p a), Data.Data.Data a, Data.Data.Data p, Data.Typeable.Internal.Typeable c) => Data.Data.Data (Data.Trie.HashMap.HashMapStep c p a)
instance GHC.Generics.Generic (Data.Trie.HashMap.HashMapStep c p a)
instance Data.Traversable.Traversable (c p) => Data.Traversable.Traversable (Data.Trie.HashMap.HashMapStep c p)
instance Data.Foldable.Foldable (c p) => Data.Foldable.Foldable (Data.Trie.HashMap.HashMapStep c p)
instance GHC.Base.Functor (c p) => GHC.Base.Functor (Data.Trie.HashMap.HashMapStep c p)
instance (GHC.Classes.Eq (c p a), GHC.Classes.Eq a, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.Trie.HashMap.HashMapStep c p a)
instance (GHC.Show.Show (c p a), GHC.Show.Show a, GHC.Show.Show p) => GHC.Show.Show (Data.Trie.HashMap.HashMapStep c p a)
instance (Data.Data.Data (c p a), Data.Data.Data a, Data.Typeable.Internal.Typeable p, Data.Typeable.Internal.Typeable c) => Data.Data.Data (Data.Trie.HashMap.HashMapChildren c p a)
instance GHC.Generics.Generic (Data.Trie.HashMap.HashMapChildren c p a)
instance Data.Traversable.Traversable (c p) => Data.Traversable.Traversable (Data.Trie.HashMap.HashMapChildren c p)
instance Data.Foldable.Foldable (c p) => Data.Foldable.Foldable (Data.Trie.HashMap.HashMapChildren c p)
instance GHC.Base.Functor (c p) => GHC.Base.Functor (Data.Trie.HashMap.HashMapChildren c p)
instance (GHC.Classes.Eq (c p a), GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Trie.HashMap.HashMapChildren c p a)
instance (GHC.Show.Show (c p a), GHC.Show.Show a) => GHC.Show.Show (Data.Trie.HashMap.HashMapChildren c p a)
instance (Data.Hashable.Class.Hashable p, GHC.Classes.Eq p) => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p Data.Trie.HashMap.HashMapTrie
instance (Data.Hashable.Class.Hashable p, GHC.Classes.Eq p) => Data.Key.Lookup (Data.Trie.HashMap.HashMapTrie p)
instance (Control.DeepSeq.NFData (c p a), Control.DeepSeq.NFData p, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Trie.HashMap.HashMapStep c p a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary (c p a), Data.Hashable.Class.Hashable p, GHC.Classes.Eq p) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.HashMap.HashMapStep c p a)
instance (Data.Hashable.Class.Hashable p, GHC.Classes.Eq p, Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p c) => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p (Data.Trie.HashMap.HashMapStep c)
instance (Data.Hashable.Class.Hashable p, GHC.Classes.Eq p, GHC.Base.Monoid (c p a)) => GHC.Base.Monoid (Data.Trie.HashMap.HashMapStep c p a)
instance (Control.DeepSeq.NFData (c p a), Control.DeepSeq.NFData p, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Trie.HashMap.HashMapChildren c p a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary (c p a)) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.HashMap.HashMapChildren c p a)
instance GHC.Base.Monoid (c p a) => GHC.Base.Monoid (Data.Trie.HashMap.HashMapChildren c p a)

module Data.Trie.Knuth
newtype KnuthTrie s x
KnuthTrie :: KnuthForest (s, Maybe x) -> KnuthTrie s x
[unKnuthTrie] :: KnuthTrie s x -> KnuthForest (s, Maybe x)
instance (Data.Data.Data x, Data.Data.Data s) => Data.Data.Data (Data.Trie.Knuth.KnuthTrie s x)
instance GHC.Generics.Generic (Data.Trie.Knuth.KnuthTrie s x)
instance (Test.QuickCheck.Arbitrary.Arbitrary x, Test.QuickCheck.Arbitrary.Arbitrary s) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Knuth.KnuthTrie s x)
instance Data.Traversable.Traversable (Data.Trie.Knuth.KnuthTrie s)
instance Data.Foldable.Foldable (Data.Trie.Knuth.KnuthTrie s)
instance GHC.Base.Functor (Data.Trie.Knuth.KnuthTrie s)
instance (GHC.Classes.Eq x, GHC.Classes.Eq s) => GHC.Classes.Eq (Data.Trie.Knuth.KnuthTrie s x)
instance (GHC.Show.Show x, GHC.Show.Show s) => GHC.Show.Show (Data.Trie.Knuth.KnuthTrie s x)
instance (Control.DeepSeq.NFData s, Control.DeepSeq.NFData x) => Control.DeepSeq.NFData (Data.Trie.Knuth.KnuthTrie s x)
instance GHC.Classes.Eq s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.Knuth.KnuthTrie

module Data.Trie.List
newtype ListTrie t x
ListTrie :: Tree (t, Maybe x) -> ListTrie t x
[unListTrie] :: ListTrie t x -> Tree (t, Maybe x)
instance (Data.Data.Data x, Data.Data.Data t) => Data.Data.Data (Data.Trie.List.ListTrie t x)
instance GHC.Generics.Generic (Data.Trie.List.ListTrie t x)
instance (Test.QuickCheck.Arbitrary.Arbitrary x, Test.QuickCheck.Arbitrary.Arbitrary t) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.List.ListTrie t x)
instance Data.Traversable.Traversable (Data.Trie.List.ListTrie t)
instance Data.Foldable.Foldable (Data.Trie.List.ListTrie t)
instance GHC.Base.Functor (Data.Trie.List.ListTrie t)
instance (GHC.Classes.Eq x, GHC.Classes.Eq t) => GHC.Classes.Eq (Data.Trie.List.ListTrie t x)
instance (GHC.Show.Show x, GHC.Show.Show t) => GHC.Show.Show (Data.Trie.List.ListTrie t x)
instance (Control.DeepSeq.NFData t, Control.DeepSeq.NFData x) => Control.DeepSeq.NFData (Data.Trie.List.ListTrie t x)
instance GHC.Classes.Eq s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.List.ListTrie

module Data.Trie.Map
data MapChildren c p a
MapChildren :: !(Maybe a) -> !(Maybe (c p a)) -> MapChildren c p a
[mapNode] :: MapChildren c p a -> !(Maybe a)
[mapChildren] :: MapChildren c p a -> !(Maybe (c p a))
newtype MapStep c p a
MapStep :: Map p (MapChildren c p a) -> MapStep c p a
[unMapStep] :: MapStep c p a -> Map p (MapChildren c p a)

-- | No insertion instance - requires children nodes to be a monoid. Use
--   <tt>Data.Trie.Map.insert</tt> instead.
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
newtype MapTrie s a
MapTrie :: MapStep MapTrie s a -> MapTrie s a
[unMapTrie] :: MapTrie s a -> MapStep MapTrie s a
keys :: forall s a. Ord s => MapTrie s a -> [NonEmpty s]
elems :: MapTrie s a -> [a]
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])

-- | 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.
matches :: Ord s => NonEmpty s -> MapTrie s a -> [(NonEmpty s, a, [s])]
instance (GHC.Classes.Ord s, Test.QuickCheck.Arbitrary.Arbitrary s, Test.QuickCheck.Arbitrary.Arbitrary a) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Map.MapTrie s a)
instance GHC.Classes.Ord s => GHC.Base.Monoid (Data.Trie.Map.MapTrie s a)
instance Data.Traversable.Traversable (Data.Trie.Map.MapTrie s)
instance Data.Foldable.Foldable (Data.Trie.Map.MapTrie s)
instance GHC.Base.Functor (Data.Trie.Map.MapTrie s)
instance (GHC.Classes.Ord a, GHC.Classes.Ord s) => GHC.Classes.Ord (Data.Trie.Map.MapTrie s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq s) => GHC.Classes.Eq (Data.Trie.Map.MapTrie s a)
instance (GHC.Show.Show a, GHC.Show.Show s) => GHC.Show.Show (Data.Trie.Map.MapTrie s a)
instance (GHC.Classes.Ord p, Data.Data.Data (c p a), Data.Data.Data a, Data.Data.Data p, Data.Typeable.Internal.Typeable c) => Data.Data.Data (Data.Trie.Map.MapStep c p a)
instance GHC.Generics.Generic (Data.Trie.Map.MapStep c p a)
instance Data.Traversable.Traversable (c p) => Data.Traversable.Traversable (Data.Trie.Map.MapStep c p)
instance Data.Foldable.Foldable (c p) => Data.Foldable.Foldable (Data.Trie.Map.MapStep c p)
instance GHC.Base.Functor (c p) => GHC.Base.Functor (Data.Trie.Map.MapStep c p)
instance (GHC.Classes.Ord (c p a), GHC.Classes.Ord a, GHC.Classes.Ord p) => GHC.Classes.Ord (Data.Trie.Map.MapStep c p a)
instance (GHC.Classes.Eq (c p a), GHC.Classes.Eq a, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.Trie.Map.MapStep c p a)
instance (GHC.Show.Show (c p a), GHC.Show.Show a, GHC.Show.Show p) => GHC.Show.Show (Data.Trie.Map.MapStep c p a)
instance (Data.Data.Data (c p a), Data.Data.Data a, Data.Typeable.Internal.Typeable p, Data.Typeable.Internal.Typeable c) => Data.Data.Data (Data.Trie.Map.MapChildren c p a)
instance GHC.Generics.Generic (Data.Trie.Map.MapChildren c p a)
instance Data.Traversable.Traversable (c p) => Data.Traversable.Traversable (Data.Trie.Map.MapChildren c p)
instance Data.Foldable.Foldable (c p) => Data.Foldable.Foldable (Data.Trie.Map.MapChildren c p)
instance GHC.Base.Functor (c p) => GHC.Base.Functor (Data.Trie.Map.MapChildren c p)
instance (GHC.Classes.Ord (c p a), GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Trie.Map.MapChildren c p a)
instance (GHC.Classes.Eq (c p a), GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Trie.Map.MapChildren c p a)
instance (GHC.Show.Show (c p a), GHC.Show.Show a) => GHC.Show.Show (Data.Trie.Map.MapChildren c p a)
instance GHC.Classes.Ord s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.Map.MapTrie
instance GHC.Classes.Ord s => Data.Key.Lookup (Data.Trie.Map.MapTrie s)
instance (Control.DeepSeq.NFData (c p a), Control.DeepSeq.NFData p, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Trie.Map.MapStep c p a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary (c p a), GHC.Classes.Ord p) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Map.MapStep c p a)
instance (GHC.Classes.Ord p, Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p c) => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p (Data.Trie.Map.MapStep c)
instance (GHC.Classes.Ord s, GHC.Base.Monoid (c s a)) => GHC.Base.Monoid (Data.Trie.Map.MapStep c s a)
instance (Control.DeepSeq.NFData (c p a), Control.DeepSeq.NFData p, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Trie.Map.MapChildren c p a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary (c p a)) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Map.MapChildren c p a)
instance GHC.Base.Monoid (c p a) => GHC.Base.Monoid (Data.Trie.Map.MapChildren c p a)

module Data.Trie.Pseudo

-- | Tagged rose tree with explicit emptyness
data PseudoTrie t a
More :: t -> (Maybe a) -> (NonEmpty (PseudoTrie t a)) -> PseudoTrie t a
Rest :: (NonEmpty t) -> a -> PseudoTrie t a
Nil :: PseudoTrie t a

-- | Overwriting instance
beginsWith :: (Eq t) => PseudoTrie t a -> t -> Bool

-- | Provides a form of deletion by setting a path to <tt>Nothing</tt>, but
--   doesn't cleanup like <tt>prune</tt>
assign :: (Eq t) => NonEmpty t -> Maybe a -> PseudoTrie t a -> PseudoTrie t a

-- | Overwrite the LHS point-wise with the RHS's contents
merge :: (Eq t) => PseudoTrie t a -> PseudoTrie t a -> PseudoTrie t a
add :: (Eq t) => NonEmpty t -> PseudoTrie t a -> PseudoTrie t a -> PseudoTrie t a
toAssocs :: PseudoTrie t a -> [(NonEmpty t, a)]
fromAssocs :: (Eq t) => [(NonEmpty t, a)] -> PseudoTrie t a
lookup :: (Eq t) => NonEmpty t -> PseudoTrie t a -> Maybe a

-- | Simple test on the heads of two tries
areDisjoint :: (Eq t) => PseudoTrie t a -> PseudoTrie t a -> Bool

-- | The meet of two <tt>PseudoTrie</tt>s
intersectionWith :: (Eq t) => (a -> b -> c) -> PseudoTrie t a -> PseudoTrie t b -> PseudoTrie t c

-- | Needless intermediary elements are turned into shortcuts,
--   <tt>Nil</tt>'s in subtrees are also removed.
prune :: PseudoTrie t a -> PseudoTrie t a
instance Data.Traversable.Traversable (Data.Trie.Pseudo.PseudoTrie t)
instance Data.Foldable.Foldable (Data.Trie.Pseudo.PseudoTrie t)
instance GHC.Base.Functor (Data.Trie.Pseudo.PseudoTrie t)
instance (GHC.Classes.Eq a, GHC.Classes.Eq t) => GHC.Classes.Eq (Data.Trie.Pseudo.PseudoTrie t a)
instance (GHC.Show.Show a, GHC.Show.Show t) => GHC.Show.Show (Data.Trie.Pseudo.PseudoTrie t a)
instance GHC.Classes.Eq t => GHC.Base.Monoid (Data.Trie.Pseudo.PseudoTrie t a)
