{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE EmptyCase #-}
#if __GLASGOW_HASKELL__ >= 810
{-# LANGUAGE StandaloneKindSignatures #-}
#endif
#if MIN_VERSION_base(4,9,0)
{-# LANGUAGE DataKinds #-}
#endif
module Data.GenericTrie.Internal
( TrieKey(..)
, ShowTrieKey(..)
, Trie(..)
, OrdKey(..)
, toList
, genericTrieNull
, genericTrieMap
, genericTrieTraverse
, genericTrieShowsPrec
, genericInsert
, genericLookup
, genericDelete
, genericAlter
, genericMapMaybeWithKey
, genericSingleton
, genericEmpty
, genericFoldWithKey
, genericTraverseWithKey
, genericTraverseMaybeWithKey
, TrieRepDefault
, GTrieKey(..)
, GTrie(..)
) where
import Data.Char (chr, ord)
import Data.Coerce (coerce)
import Data.IntMap (IntMap)
#if MIN_VERSION_base(4,9,0)
import Data.Kind (Type)
#endif
import Data.Map (Map)
import Data.Maybe (isNothing)
import GHC.Generics
import qualified Data.Foldable as Foldable
import qualified Data.Traversable as Traversable
import qualified Data.IntMap as IntMap
import qualified Data.Map as Map
import Prelude
#if MIN_VERSION_base(4,8,0)
import Data.Void (Void)
#endif
#if MIN_VERSION_base(4,8,0)
import Numeric.Natural
#endif
class TrieKey k where
#if MIN_VERSION_base(4,9,0)
type TrieRep k :: Type -> Type
#else
type TrieRep k :: * -> *
#endif
trieEmpty :: Trie k a
trieNull :: Trie k a -> Bool
trieLookup :: k -> Trie k a -> Maybe a
trieInsert :: k -> a -> Trie k a -> Trie k a
trieDelete :: k -> Trie k a -> Trie k a
trieAlter :: k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
trieSingleton :: k -> a -> Trie k a
trieMap :: (a -> b) -> Trie k a -> Trie k b
trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b)
trieMapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b
trieFoldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r
trieTraverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b)
trieTraverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
trieMergeWithKey :: (k -> a -> b -> Maybe c) ->
(Trie k a -> Trie k c) ->
(Trie k b -> Trie k c) ->
Trie k a -> Trie k b -> Trie k c
type instance TrieRep k = TrieRepDefault k
default trieEmpty :: ( TrieRep k ~ TrieRepDefault k) => Trie k a
trieEmpty = forall k a. (TrieRep k ~ TrieRepDefault k) => Trie k a
genericEmpty
default trieSingleton ::
( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a
trieSingleton = forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a
genericSingleton
default trieNull ::
( TrieRep k ~ TrieRepDefault k) =>
Trie k a -> Bool
trieNull = forall k a. (TrieRep k ~ TrieRepDefault k) => Trie k a -> Bool
genericTrieNull
default trieLookup ::
( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Maybe a
trieLookup = forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Maybe a
genericLookup
default trieInsert ::
( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a -> Trie k a
trieInsert = forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a -> Trie k a
genericInsert
default trieDelete ::
( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Trie k a
trieDelete = forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Trie k a
genericDelete
default trieAlter ::
( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
trieAlter = forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
genericAlter
default trieMap ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k) =>
(a -> b) -> Trie k a -> Trie k b
trieMap = forall k a b.
(GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k) =>
(a -> b) -> Trie k a -> Trie k b
genericTrieMap
default trieTraverse ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k , Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
trieTraverse = forall k (f :: * -> *) a b.
(GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k, Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
genericTrieTraverse
default trieMapMaybeWithKey ::
( GTrieKey (Rep k) , Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
trieMapMaybeWithKey = forall k a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
genericMapMaybeWithKey
default trieFoldWithKey ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k) =>
(k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey = forall k a r.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> r -> r) -> r -> Trie k a -> r
genericFoldWithKey
default trieTraverseWithKey ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k, Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
trieTraverseWithKey = forall k (f :: * -> *) a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k,
Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
genericTraverseWithKey
default trieTraverseMaybeWithKey ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k, Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
trieTraverseMaybeWithKey = forall k (f :: * -> *) a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k,
Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
genericTraverseMaybeWithKey
default trieMergeWithKey ::
( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k ) =>
(k -> a -> b -> Maybe c) ->
(Trie k a -> Trie k c) ->
(Trie k b -> Trie k c) ->
Trie k a -> Trie k b -> Trie k c
trieMergeWithKey = forall k a b c.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
genericMergeWithKey
newtype Trie k a = MkTrie (TrieRep k a)
toList :: TrieKey k => Trie k a -> [(k,a)]
toList :: forall k a. TrieKey k => Trie k a -> [(k, a)]
toList = forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey (\k
k a
v [(k, a)]
xs -> (k
k,a
v) forall a. a -> [a] -> [a]
: [(k, a)]
xs) []
class TrieKey k => ShowTrieKey k where
trieShowsPrec :: Show a => Int -> Trie k a -> ShowS
default trieShowsPrec ::
( Show a, GTrieKeyShow (Rep k) , TrieRep k ~ TrieRepDefault k) =>
Int -> Trie k a -> ShowS
trieShowsPrec = forall a k.
(Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) =>
Int -> Trie k a -> ShowS
genericTrieShowsPrec
instance TrieKey Int where
type TrieRep Int = IntMap
trieLookup :: forall a. Int -> Trie Int a -> Maybe a
trieLookup Int
k (MkTrie TrieRep Int a
x) = forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
k TrieRep Int a
x
trieInsert :: forall a. Int -> a -> Trie Int a -> Trie Int a
trieInsert Int
k a
v (MkTrie TrieRep Int a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert Int
k a
v TrieRep Int a
t)
trieDelete :: forall a. Int -> Trie Int a -> Trie Int a
trieDelete Int
k (MkTrie TrieRep Int a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> IntMap a -> IntMap a
IntMap.delete Int
k TrieRep Int a
t)
trieAlter :: forall a. Int -> (Maybe a -> Maybe a) -> Trie Int a -> Trie Int a
trieAlter Int
k Maybe a -> Maybe a
f (MkTrie TrieRep Int a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
IntMap.alter Maybe a -> Maybe a
f Int
k TrieRep Int a
t)
trieEmpty :: forall a. Trie Int a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall a. IntMap a
IntMap.empty
trieSingleton :: forall a. Int -> a -> Trie Int a
trieSingleton Int
k a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
trieNull :: forall a. Trie Int a -> Bool
trieNull (MkTrie TrieRep Int a
x) = forall a. IntMap a -> Bool
IntMap.null TrieRep Int a
x
trieMap :: forall a b. (a -> b) -> Trie Int a -> Trie Int b
trieMap a -> b
f (MkTrie TrieRep Int a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f TrieRep Int a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie Int a -> f (Trie Int b)
trieTraverse a -> f b
f (MkTrie TrieRep Int a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep Int a
x)
trieMapMaybeWithKey :: forall a b. (Int -> a -> Maybe b) -> Trie Int a -> Trie Int b
trieMapMaybeWithKey Int -> a -> Maybe b
f (MkTrie TrieRep Int a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey Int -> a -> Maybe b
f TrieRep Int a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f (Maybe b)) -> Trie Int a -> f (Trie Int b)
trieTraverseMaybeWithKey Int -> a -> f (Maybe b)
f (MkTrie TrieRep Int a
x) =
#if MIN_VERSION_containers (0,6,4)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap b)
IntMap.traverseMaybeWithKey Int -> a -> f (Maybe b)
f TrieRep Int a
x
#else
MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey f x
#endif
trieFoldWithKey :: forall a r. (Int -> a -> r -> r) -> r -> Trie Int a -> r
trieFoldWithKey Int -> a -> r -> r
f r
z (MkTrie TrieRep Int a
x) = forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey Int -> a -> r -> r
f r
z TrieRep Int a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f b) -> Trie Int a -> f (Trie Int b)
trieTraverseWithKey Int -> a -> f b
f (MkTrie TrieRep Int a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey Int -> a -> f b
f TrieRep Int a
x)
trieMergeWithKey :: forall a b c.
(Int -> a -> b -> Maybe c)
-> (Trie Int a -> Trie Int c)
-> (Trie Int b -> Trie Int c)
-> Trie Int a
-> Trie Int b
-> Trie Int c
trieMergeWithKey Int -> a -> b -> Maybe c
f Trie Int a -> Trie Int c
g Trie Int b -> Trie Int c
h (MkTrie TrieRep Int a
x) (MkTrie TrieRep Int b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IntMap.mergeWithKey Int -> a -> b -> Maybe c
f (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Int a -> Trie Int c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Int b -> Trie Int c
h) TrieRep Int a
x TrieRep Int b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
instance ShowTrieKey Int where
trieShowsPrec :: forall a. Show a => Int -> Trie Int a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Int a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p TrieRep Int a
x
{-# INLINABLE trieShowsPrec #-}
instance TrieKey Integer where
type TrieRep Integer = Map Integer
trieLookup :: forall a. Integer -> Trie Integer a -> Maybe a
trieLookup Integer
k (MkTrie TrieRep Integer a
t) = forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Integer
k TrieRep Integer a
t
trieInsert :: forall a. Integer -> a -> Trie Integer a -> Trie Integer a
trieInsert Integer
k a
v (MkTrie TrieRep Integer a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert Integer
k a
v TrieRep Integer a
t)
trieDelete :: forall a. Integer -> Trie Integer a -> Trie Integer a
trieDelete Integer
k (MkTrie TrieRep Integer a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Integer
k TrieRep Integer a
t)
trieAlter :: forall a.
Integer -> (Maybe a -> Maybe a) -> Trie Integer a -> Trie Integer a
trieAlter Integer
k Maybe a -> Maybe a
f (MkTrie TrieRep Integer a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe a -> Maybe a
f Integer
k TrieRep Integer a
t)
trieEmpty :: forall a. Trie Integer a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. Map k a
Map.empty
trieSingleton :: forall a. Integer -> a -> Trie Integer a
trieSingleton Integer
k a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. k -> a -> Map k a
Map.singleton Integer
k a
v)
trieNull :: forall a. Trie Integer a -> Bool
trieNull (MkTrie TrieRep Integer a
x) = forall k a. Map k a -> Bool
Map.null TrieRep Integer a
x
trieMap :: forall a b. (a -> b) -> Trie Integer a -> Trie Integer b
trieMap a -> b
f (MkTrie TrieRep Integer a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f TrieRep Integer a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie Integer a -> f (Trie Integer b)
trieTraverse a -> f b
f (MkTrie TrieRep Integer a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep Integer a
x)
trieMapMaybeWithKey :: forall a b.
(Integer -> a -> Maybe b) -> Trie Integer a -> Trie Integer b
trieMapMaybeWithKey Integer -> a -> Maybe b
f (MkTrie TrieRep Integer a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey Integer -> a -> Maybe b
f TrieRep Integer a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Integer -> a -> f (Maybe b))
-> Trie Integer a -> f (Trie Integer b)
trieTraverseMaybeWithKey Integer -> a -> f (Maybe b)
f (MkTrie TrieRep Integer a
x) =
#if MIN_VERSION_containers (0,5,8)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey Integer -> a -> f (Maybe b)
f TrieRep Integer a
x
#else
MkTrie . Map.mapMaybe id <$> Map.traverseWithKey f x
#endif
trieFoldWithKey :: forall a r. (Integer -> a -> r -> r) -> r -> Trie Integer a -> r
trieFoldWithKey Integer -> a -> r -> r
f r
z (MkTrie TrieRep Integer a
x) = forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey Integer -> a -> r -> r
f r
z TrieRep Integer a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Integer -> a -> f b) -> Trie Integer a -> f (Trie Integer b)
trieTraverseWithKey Integer -> a -> f b
f (MkTrie TrieRep Integer a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.traverseWithKey Integer -> a -> f b
f TrieRep Integer a
x)
trieMergeWithKey :: forall a b c.
(Integer -> a -> b -> Maybe c)
-> (Trie Integer a -> Trie Integer c)
-> (Trie Integer b -> Trie Integer c)
-> Trie Integer a
-> Trie Integer b
-> Trie Integer c
trieMergeWithKey Integer -> a -> b -> Maybe c
f Trie Integer a -> Trie Integer c
g Trie Integer b -> Trie Integer c
h (MkTrie TrieRep Integer a
x) (MkTrie TrieRep Integer b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey Integer -> a -> b -> Maybe c
f (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Integer a -> Trie Integer c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Integer b -> Trie Integer c
h) TrieRep Integer a
x TrieRep Integer b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
instance ShowTrieKey Integer where
trieShowsPrec :: forall a. Show a => Int -> Trie Integer a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Integer a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p TrieRep Integer a
x
{-# INLINABLE trieShowsPrec #-}
#if MIN_VERSION_base(4,8,0)
instance TrieKey Natural where
type TrieRep Natural = Map Natural
trieLookup :: forall a. Natural -> Trie Natural a -> Maybe a
trieLookup Natural
k (MkTrie TrieRep Natural a
t) = forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Natural
k TrieRep Natural a
t
trieInsert :: forall a. Natural -> a -> Trie Natural a -> Trie Natural a
trieInsert Natural
k a
v (MkTrie TrieRep Natural a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert Natural
k a
v TrieRep Natural a
t)
trieDelete :: forall a. Natural -> Trie Natural a -> Trie Natural a
trieDelete Natural
k (MkTrie TrieRep Natural a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Natural
k TrieRep Natural a
t)
trieAlter :: forall a.
Natural -> (Maybe a -> Maybe a) -> Trie Natural a -> Trie Natural a
trieAlter Natural
k Maybe a -> Maybe a
f (MkTrie TrieRep Natural a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe a -> Maybe a
f Natural
k TrieRep Natural a
t)
trieEmpty :: forall a. Trie Natural a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. Map k a
Map.empty
trieSingleton :: forall a. Natural -> a -> Trie Natural a
trieSingleton Natural
k a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. k -> a -> Map k a
Map.singleton Natural
k a
v)
trieNull :: forall a. Trie Natural a -> Bool
trieNull (MkTrie TrieRep Natural a
x) = forall k a. Map k a -> Bool
Map.null TrieRep Natural a
x
trieMap :: forall a b. (a -> b) -> Trie Natural a -> Trie Natural b
trieMap a -> b
f (MkTrie TrieRep Natural a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f TrieRep Natural a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie Natural a -> f (Trie Natural b)
trieTraverse a -> f b
f (MkTrie TrieRep Natural a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep Natural a
x)
trieMapMaybeWithKey :: forall a b.
(Natural -> a -> Maybe b) -> Trie Natural a -> Trie Natural b
trieMapMaybeWithKey Natural -> a -> Maybe b
f (MkTrie TrieRep Natural a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey Natural -> a -> Maybe b
f TrieRep Natural a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Natural -> a -> f (Maybe b))
-> Trie Natural a -> f (Trie Natural b)
trieTraverseMaybeWithKey Natural -> a -> f (Maybe b)
f (MkTrie TrieRep Natural a
x) =
#if MIN_VERSION_containers (0,5,8)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey Natural -> a -> f (Maybe b)
f TrieRep Natural a
x
#else
MkTrie . Map.mapMaybe id <$> Map.traverseWithKey f x
#endif
trieFoldWithKey :: forall a r. (Natural -> a -> r -> r) -> r -> Trie Natural a -> r
trieFoldWithKey Natural -> a -> r -> r
f r
z (MkTrie TrieRep Natural a
x) = forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey Natural -> a -> r -> r
f r
z TrieRep Natural a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Natural -> a -> f b) -> Trie Natural a -> f (Trie Natural b)
trieTraverseWithKey Natural -> a -> f b
f (MkTrie TrieRep Natural a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.traverseWithKey Natural -> a -> f b
f TrieRep Natural a
x)
trieMergeWithKey :: forall a b c.
(Natural -> a -> b -> Maybe c)
-> (Trie Natural a -> Trie Natural c)
-> (Trie Natural b -> Trie Natural c)
-> Trie Natural a
-> Trie Natural b
-> Trie Natural c
trieMergeWithKey Natural -> a -> b -> Maybe c
f Trie Natural a -> Trie Natural c
g Trie Natural b -> Trie Natural c
h (MkTrie TrieRep Natural a
x) (MkTrie TrieRep Natural b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey Natural -> a -> b -> Maybe c
f (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Natural a -> Trie Natural c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Natural b -> Trie Natural c
h) TrieRep Natural a
x TrieRep Natural b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
instance ShowTrieKey Natural where
trieShowsPrec :: forall a. Show a => Int -> Trie Natural a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Natural a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p TrieRep Natural a
x
{-# INLINABLE trieShowsPrec #-}
#endif
instance TrieKey Word where
type TrieRep Word = IntMap
trieLookup :: forall a. Word -> Trie Word a -> Maybe a
trieLookup Word
k (MkTrie TrieRep Word a
t) = forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) TrieRep Word a
t
trieDelete :: forall a. Word -> Trie Word a -> Trie Word a
trieDelete Word
k (MkTrie TrieRep Word a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> IntMap a -> IntMap a
IntMap.delete (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) TrieRep Word a
t)
trieInsert :: forall a. Word -> a -> Trie Word a -> Trie Word a
trieInsert Word
k a
v (MkTrie TrieRep Word a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) a
v TrieRep Word a
t)
trieAlter :: forall a.
Word -> (Maybe a -> Maybe a) -> Trie Word a -> Trie Word a
trieAlter Word
k Maybe a -> Maybe a
f (MkTrie TrieRep Word a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
IntMap.alter Maybe a -> Maybe a
f (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) TrieRep Word a
t)
trieEmpty :: forall a. Trie Word a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall a. IntMap a
IntMap.empty
trieSingleton :: forall a. Word -> a -> Trie Word a
trieSingleton Word
k a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a
IntMap.singleton (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) a
v)
trieNull :: forall a. Trie Word a -> Bool
trieNull (MkTrie TrieRep Word a
x) = forall a. IntMap a -> Bool
IntMap.null TrieRep Word a
x
trieMap :: forall a b. (a -> b) -> Trie Word a -> Trie Word b
trieMap a -> b
f (MkTrie TrieRep Word a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f TrieRep Word a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie Word a -> f (Trie Word b)
trieTraverse a -> f b
f (MkTrie TrieRep Word a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep Word a
x)
trieMapMaybeWithKey :: forall a b. (Word -> a -> Maybe b) -> Trie Word a -> Trie Word b
trieMapMaybeWithKey Word -> a -> Maybe b
f (MkTrie TrieRep Word a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey (Word -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) TrieRep Word a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Word -> a -> f (Maybe b)) -> Trie Word a -> f (Trie Word b)
trieTraverseMaybeWithKey Word -> a -> f (Maybe b)
f (MkTrie TrieRep Word a
x) =
#if MIN_VERSION_containers (0,6,4)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap b)
IntMap.traverseMaybeWithKey (Word -> a -> f (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) TrieRep Word a
x
#else
MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey (f . fromIntegral) x
#endif
trieFoldWithKey :: forall a r. (Word -> a -> r -> r) -> r -> Trie Word a -> r
trieFoldWithKey Word -> a -> r -> r
f r
z (MkTrie TrieRep Word a
x) = forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey (Word -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) r
z TrieRep Word a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Word -> a -> f b) -> Trie Word a -> f (Trie Word b)
trieTraverseWithKey Word -> a -> f b
f (MkTrie TrieRep Word a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Word -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) TrieRep Word a
x)
trieMergeWithKey :: forall a b c.
(Word -> a -> b -> Maybe c)
-> (Trie Word a -> Trie Word c)
-> (Trie Word b -> Trie Word c)
-> Trie Word a
-> Trie Word b
-> Trie Word c
trieMergeWithKey Word -> a -> b -> Maybe c
f Trie Word a -> Trie Word c
g Trie Word b -> Trie Word c
h (MkTrie TrieRep Word a
x) (MkTrie TrieRep Word b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IntMap.mergeWithKey (Word -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Word a -> Trie Word c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Word b -> Trie Word c
h) TrieRep Word a
x TrieRep Word b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
instance ShowTrieKey Word where
trieShowsPrec :: forall a. Show a => Int -> Trie Word a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Word a
x) =
Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) (String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows [(forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k :: Word, a
v) | (Int
k,a
v) <- forall a. IntMap a -> [(Int, a)]
IntMap.toList TrieRep Word a
x])
{-# INLINABLE trieShowsPrec #-}
instance TrieKey Char where
type TrieRep Char = IntMap
trieLookup :: forall a. Char -> Trie Char a -> Maybe a
trieLookup Char
k (MkTrie TrieRep Char a
t) = forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (Char -> Int
ord Char
k) TrieRep Char a
t
trieDelete :: forall a. Char -> Trie Char a -> Trie Char a
trieDelete Char
k (MkTrie TrieRep Char a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> IntMap a -> IntMap a
IntMap.delete (Char -> Int
ord Char
k) TrieRep Char a
t)
trieInsert :: forall a. Char -> a -> Trie Char a -> Trie Char a
trieInsert Char
k a
v (MkTrie TrieRep Char a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert (Char -> Int
ord Char
k) a
v TrieRep Char a
t)
trieAlter :: forall a.
Char -> (Maybe a -> Maybe a) -> Trie Char a -> Trie Char a
trieAlter Char
k Maybe a -> Maybe a
f (MkTrie TrieRep Char a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
IntMap.alter Maybe a -> Maybe a
f (Char -> Int
ord Char
k) TrieRep Char a
t)
trieEmpty :: forall a. Trie Char a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall a. IntMap a
IntMap.empty
trieSingleton :: forall a. Char -> a -> Trie Char a
trieSingleton Char
k a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a. Int -> a -> IntMap a
IntMap.singleton (Char -> Int
ord Char
k) a
v)
trieNull :: forall a. Trie Char a -> Bool
trieNull (MkTrie TrieRep Char a
x) = forall a. IntMap a -> Bool
IntMap.null TrieRep Char a
x
trieMap :: forall a b. (a -> b) -> Trie Char a -> Trie Char b
trieMap a -> b
f (MkTrie TrieRep Char a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f TrieRep Char a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie Char a -> f (Trie Char b)
trieTraverse a -> f b
f (MkTrie TrieRep Char a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep Char a
x)
trieMapMaybeWithKey :: forall a b. (Char -> a -> Maybe b) -> Trie Char a -> Trie Char b
trieMapMaybeWithKey Char -> a -> Maybe b
f (MkTrie TrieRep Char a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey (Char -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) TrieRep Char a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Char -> a -> f (Maybe b)) -> Trie Char a -> f (Trie Char b)
trieTraverseMaybeWithKey Char -> a -> f (Maybe b)
f (MkTrie TrieRep Char a
x) =
#if MIN_VERSION_containers (0,6,4)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap b)
IntMap.traverseMaybeWithKey (Char -> a -> f (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) TrieRep Char a
x
#else
MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey (f . chr) x
#endif
trieFoldWithKey :: forall a r. (Char -> a -> r -> r) -> r -> Trie Char a -> r
trieFoldWithKey Char -> a -> r -> r
f r
z (MkTrie TrieRep Char a
x) = forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey (Char -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) r
z TrieRep Char a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Char -> a -> f b) -> Trie Char a -> f (Trie Char b)
trieTraverseWithKey Char -> a -> f b
f (MkTrie TrieRep Char a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Char -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) TrieRep Char a
x)
trieMergeWithKey :: forall a b c.
(Char -> a -> b -> Maybe c)
-> (Trie Char a -> Trie Char c)
-> (Trie Char b -> Trie Char c)
-> Trie Char a
-> Trie Char b
-> Trie Char c
trieMergeWithKey Char -> a -> b -> Maybe c
f Trie Char a -> Trie Char c
g Trie Char b -> Trie Char c
h (MkTrie TrieRep Char a
x) (MkTrie TrieRep Char b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IntMap.mergeWithKey (Char -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Char a -> Trie Char c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie Char b -> Trie Char c
h) TrieRep Char a
x TrieRep Char b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
instance ShowTrieKey Char where
trieShowsPrec :: forall a. Show a => Int -> Trie Char a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Char a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p TrieRep Char a
x
{-# INLINABLE trieShowsPrec #-}
newtype OrdKey k = OrdKey { forall k. OrdKey k -> k
getOrdKey :: k }
deriving (ReadPrec [OrdKey k]
ReadPrec (OrdKey k)
ReadS [OrdKey k]
forall k. Read k => ReadPrec [OrdKey k]
forall k. Read k => ReadPrec (OrdKey k)
forall k. Read k => Int -> ReadS (OrdKey k)
forall k. Read k => ReadS [OrdKey k]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [OrdKey k]
$creadListPrec :: forall k. Read k => ReadPrec [OrdKey k]
readPrec :: ReadPrec (OrdKey k)
$creadPrec :: forall k. Read k => ReadPrec (OrdKey k)
readList :: ReadS [OrdKey k]
$creadList :: forall k. Read k => ReadS [OrdKey k]
readsPrec :: Int -> ReadS (OrdKey k)
$creadsPrec :: forall k. Read k => Int -> ReadS (OrdKey k)
Read, Int -> OrdKey k -> ShowS
forall k. Show k => Int -> OrdKey k -> ShowS
forall k. Show k => [OrdKey k] -> ShowS
forall k. Show k => OrdKey k -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [OrdKey k] -> ShowS
$cshowList :: forall k. Show k => [OrdKey k] -> ShowS
show :: OrdKey k -> String
$cshow :: forall k. Show k => OrdKey k -> String
showsPrec :: Int -> OrdKey k -> ShowS
$cshowsPrec :: forall k. Show k => Int -> OrdKey k -> ShowS
Show, OrdKey k -> OrdKey k -> Bool
forall k. Eq k => OrdKey k -> OrdKey k -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: OrdKey k -> OrdKey k -> Bool
$c/= :: forall k. Eq k => OrdKey k -> OrdKey k -> Bool
== :: OrdKey k -> OrdKey k -> Bool
$c== :: forall k. Eq k => OrdKey k -> OrdKey k -> Bool
Eq, OrdKey k -> OrdKey k -> Bool
OrdKey k -> OrdKey k -> Ordering
OrdKey k -> OrdKey k -> OrdKey k
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {k}. Ord k => Eq (OrdKey k)
forall k. Ord k => OrdKey k -> OrdKey k -> Bool
forall k. Ord k => OrdKey k -> OrdKey k -> Ordering
forall k. Ord k => OrdKey k -> OrdKey k -> OrdKey k
min :: OrdKey k -> OrdKey k -> OrdKey k
$cmin :: forall k. Ord k => OrdKey k -> OrdKey k -> OrdKey k
max :: OrdKey k -> OrdKey k -> OrdKey k
$cmax :: forall k. Ord k => OrdKey k -> OrdKey k -> OrdKey k
>= :: OrdKey k -> OrdKey k -> Bool
$c>= :: forall k. Ord k => OrdKey k -> OrdKey k -> Bool
> :: OrdKey k -> OrdKey k -> Bool
$c> :: forall k. Ord k => OrdKey k -> OrdKey k -> Bool
<= :: OrdKey k -> OrdKey k -> Bool
$c<= :: forall k. Ord k => OrdKey k -> OrdKey k -> Bool
< :: OrdKey k -> OrdKey k -> Bool
$c< :: forall k. Ord k => OrdKey k -> OrdKey k -> Bool
compare :: OrdKey k -> OrdKey k -> Ordering
$ccompare :: forall k. Ord k => OrdKey k -> OrdKey k -> Ordering
Ord)
instance Ord k => TrieKey (OrdKey k) where
type TrieRep (OrdKey k) = Map k
trieLookup :: forall a. OrdKey k -> Trie (OrdKey k) a -> Maybe a
trieLookup (OrdKey k
k) (MkTrie TrieRep (OrdKey k) a
x) = forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k TrieRep (OrdKey k) a
x
trieInsert :: forall a. OrdKey k -> a -> Trie (OrdKey k) a -> Trie (OrdKey k) a
trieInsert (OrdKey k
k) a
v (MkTrie TrieRep (OrdKey k) a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k a
v TrieRep (OrdKey k) a
x)
trieDelete :: forall a. OrdKey k -> Trie (OrdKey k) a -> Trie (OrdKey k) a
trieDelete (OrdKey k
k) (MkTrie TrieRep (OrdKey k) a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k TrieRep (OrdKey k) a
x)
trieAlter :: forall a.
OrdKey k
-> (Maybe a -> Maybe a) -> Trie (OrdKey k) a -> Trie (OrdKey k) a
trieAlter (OrdKey k
k) Maybe a -> Maybe a
f (MkTrie TrieRep (OrdKey k) a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe a -> Maybe a
f k
k TrieRep (OrdKey k) a
x)
trieEmpty :: forall a. Trie (OrdKey k) a
trieEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. Map k a
Map.empty
trieSingleton :: forall a. OrdKey k -> a -> Trie (OrdKey k) a
trieSingleton (OrdKey k
k) a
v = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. k -> a -> Map k a
Map.singleton k
k a
v)
trieNull :: forall a. Trie (OrdKey k) a -> Bool
trieNull (MkTrie TrieRep (OrdKey k) a
x) = forall k a. Map k a -> Bool
Map.null TrieRep (OrdKey k) a
x
trieMap :: forall a b. (a -> b) -> Trie (OrdKey k) a -> Trie (OrdKey k) b
trieMap a -> b
f (MkTrie TrieRep (OrdKey k) a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f TrieRep (OrdKey k) a
x)
trieTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie (OrdKey k) a -> f (Trie (OrdKey k) b)
trieTraverse a -> f b
f (MkTrie TrieRep (OrdKey k) a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f TrieRep (OrdKey k) a
x)
trieMapMaybeWithKey :: forall a b.
(OrdKey k -> a -> Maybe b)
-> Trie (OrdKey k) a -> Trie (OrdKey k) b
trieMapMaybeWithKey OrdKey k -> a -> Maybe b
f (MkTrie TrieRep (OrdKey k) a
x) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey (OrdKey k -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. k -> OrdKey k
OrdKey) TrieRep (OrdKey k) a
x)
trieTraverseMaybeWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(OrdKey k -> a -> f (Maybe b))
-> Trie (OrdKey k) a -> f (Trie (OrdKey k) b)
trieTraverseMaybeWithKey OrdKey k -> a -> f (Maybe b)
f (MkTrie TrieRep (OrdKey k) a
x) =
#if MIN_VERSION_containers (0,5,8)
forall k a. TrieRep k a -> Trie k a
MkTrie forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey (OrdKey k -> a -> f (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. k -> OrdKey k
OrdKey) TrieRep (OrdKey k) a
x
#else
MkTrie . Map.mapMaybe id <$> Map.traverseWithKey (f . OrdKey) x
#endif
trieFoldWithKey :: forall a r.
(OrdKey k -> a -> r -> r) -> r -> Trie (OrdKey k) a -> r
trieFoldWithKey OrdKey k -> a -> r -> r
f r
z (MkTrie TrieRep (OrdKey k) a
x) = forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey (OrdKey k -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. k -> OrdKey k
OrdKey) r
z TrieRep (OrdKey k) a
x
trieTraverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(OrdKey k -> a -> f b)
-> Trie (OrdKey k) a -> f (Trie (OrdKey k) b)
trieTraverseWithKey OrdKey k -> a -> f b
f (MkTrie TrieRep (OrdKey k) a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k a. TrieRep k a -> Trie k a
MkTrie (forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.traverseWithKey (OrdKey k -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. k -> OrdKey k
OrdKey) TrieRep (OrdKey k) a
x)
trieMergeWithKey :: forall a b c.
(OrdKey k -> a -> b -> Maybe c)
-> (Trie (OrdKey k) a -> Trie (OrdKey k) c)
-> (Trie (OrdKey k) b -> Trie (OrdKey k) c)
-> Trie (OrdKey k) a
-> Trie (OrdKey k) b
-> Trie (OrdKey k) c
trieMergeWithKey OrdKey k -> a -> b -> Maybe c
f Trie (OrdKey k) a -> Trie (OrdKey k) c
g Trie (OrdKey k) b -> Trie (OrdKey k) c
h (MkTrie TrieRep (OrdKey k) a
x) (MkTrie TrieRep (OrdKey k) b
y) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey (OrdKey k -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. k -> OrdKey k
OrdKey) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie (OrdKey k) a -> Trie (OrdKey k) c
g) (coerce :: forall a b. Coercible a b => a -> b
coerce Trie (OrdKey k) b -> Trie (OrdKey k) c
h) TrieRep (OrdKey k) a
x TrieRep (OrdKey k) b
y)
{-# INLINABLE trieEmpty #-}
{-# INLINABLE trieInsert #-}
{-# INLINABLE trieLookup #-}
{-# INLINABLE trieDelete #-}
{-# INLINABLE trieAlter #-}
{-# INLINABLE trieSingleton #-}
{-# INLINABLE trieFoldWithKey #-}
{-# INLINABLE trieTraverse #-}
{-# INLINABLE trieTraverseWithKey #-}
{-# INLINABLE trieTraverseMaybeWithKey #-}
{-# INLINABLE trieNull #-}
{-# INLINABLE trieMap #-}
{-# INLINABLE trieMergeWithKey #-}
{-# INLINABLE trieMapMaybeWithKey #-}
instance (Show k, Ord k) => ShowTrieKey (OrdKey k) where
trieShowsPrec :: forall a. Show a => Int -> Trie (OrdKey k) a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep (OrdKey k) a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p TrieRep (OrdKey k) a
x
{-# INLINABLE trieShowsPrec #-}
#if MIN_VERSION_base(4,8,0)
instance TrieKey Void
instance ShowTrieKey Void
#endif
instance TrieKey ()
instance ShowTrieKey ()
instance TrieKey Bool
instance ShowTrieKey Bool
instance TrieKey Ordering
instance ShowTrieKey Ordering
instance TrieKey k => TrieKey (Maybe k)
instance ShowTrieKey k => ShowTrieKey (Maybe k)
instance (TrieKey a, TrieKey b) => TrieKey (Either a b)
instance (ShowTrieKey a, ShowTrieKey b) => ShowTrieKey (Either a b)
instance (TrieKey a, TrieKey b) => TrieKey (a,b)
instance (ShowTrieKey a, ShowTrieKey b) => ShowTrieKey (a,b)
instance (TrieKey a, TrieKey b, TrieKey c) => TrieKey (a,b,c)
instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c) => ShowTrieKey (a,b,c)
instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d) => TrieKey (a,b,c,d)
instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c, ShowTrieKey d) => ShowTrieKey (a,b,c,d)
instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d, TrieKey e) => TrieKey (a,b,c,d,e)
instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c, ShowTrieKey d, ShowTrieKey e) => ShowTrieKey (a,b,c,d,e)
instance TrieKey k => TrieKey [k]
instance ShowTrieKey k => ShowTrieKey [k]
genericLookup ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
k -> Trie k a -> Maybe a
genericLookup :: forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Maybe a
genericLookup k
k Trie k a
t = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup (forall a x. Generic a => a -> Rep a x
from k
k) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
t
{-# INLINABLE genericLookup #-}
genericTrieNull ::
( TrieRep k ~ TrieRepDefault k
) =>
Trie k a -> Bool
genericTrieNull :: forall k a. (TrieRep k ~ TrieRepDefault k) => Trie k a -> Bool
genericTrieNull = forall a. Maybe a -> Bool
isNothing forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap
{-# INLINABLE genericTrieNull #-}
genericSingleton ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
k -> a -> Trie k a
genericSingleton :: forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a
genericSingleton k
k a
v = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton (forall a x. Generic a => a -> Rep a x
from k
k) a
v
{-# INLINABLE genericSingleton #-}
genericEmpty ::
( TrieRep k ~ TrieRepDefault k
) =>
Trie k a
genericEmpty :: forall k a. (TrieRep k ~ TrieRepDefault k) => Trie k a
genericEmpty = forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. TrieRepDefault k a
EmptyTrie
{-# INLINABLE genericEmpty #-}
genericInsert ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
k -> a -> Trie k a -> Trie k a
genericInsert :: forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> a -> Trie k a -> Trie k a
genericInsert k
k a
v Trie k a
m = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap forall a b. (a -> b) -> a -> b
$
case forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m of
Maybe (GTrie (Rep k) a)
Nothing -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton (forall a x. Generic a => a -> Rep a x
from k
k) a
v
Just GTrie (Rep k) a
t -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert (forall a x. Generic a => a -> Rep a x
from k
k) a
v GTrie (Rep k) a
t
{-# INLINABLE genericInsert #-}
genericDelete ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
k -> Trie k a -> Trie k a
genericDelete :: forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Trie k a
genericDelete k
k Trie k a
m = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete (forall a x. Generic a => a -> Rep a x
from k
k) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m)
{-# INLINABLE genericDelete #-}
genericAlter ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
genericAlter :: forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
genericAlter k
k Maybe a -> Maybe a
f Trie k a
m = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter (forall a x. Generic a => a -> Rep a x
from k
k) Maybe a -> Maybe a
f forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m)
{-# INLINABLE genericAlter #-}
genericTrieMap ::
( GTrieKey (Rep k)
, TrieRep k ~ TrieRepDefault k
) =>
(a -> b) -> Trie k a -> Trie k b
genericTrieMap :: forall k a b.
(GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k) =>
(a -> b) -> Trie k a -> Trie k b
genericTrieMap a -> b
f Trie k a
x = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f) forall a b. (a -> b) -> a -> b
$! forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
x)
{-# INLINABLE genericTrieMap #-}
genericTrieTraverse ::
( GTrieKey (Rep k)
, TrieRep k ~ TrieRepDefault k
, Applicative f
) =>
(a -> f b) -> Trie k a -> f (Trie k b)
genericTrieTraverse :: forall k (f :: * -> *) a b.
(GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k, Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
genericTrieTraverse a -> f b
f Trie k a
x =
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> f b
f) (forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
x))
{-# INLINABLE genericTrieTraverse #-}
genericTrieShowsPrec ::
( Show a, GTrieKeyShow (Rep k)
, TrieRep k ~ TrieRepDefault k
) =>
Int -> Trie k a -> ShowS
genericTrieShowsPrec :: forall a k.
(Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) =>
Int -> Trie k a -> ShowS
genericTrieShowsPrec Int
p Trie k a
m =
case forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m of
Just GTrie (Rep k) a
x -> forall a. Show a => Int -> a -> ShowS
showsPrec Int
p GTrie (Rep k) a
x
Maybe (GTrie (Rep k) a)
Nothing -> String -> ShowS
showString String
"()"
{-# INLINABLE genericTrieShowsPrec #-}
genericMapMaybeWithKey ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
genericMapMaybeWithKey :: forall k a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
genericMapMaybeWithKey k -> a -> Maybe b
f Trie k a
x = forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey (k -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a x. Generic a => Rep a x -> a
to) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
x)
{-# INLINABLE genericMapMaybeWithKey #-}
genericFoldWithKey ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
(k -> a -> r -> r) -> r -> Trie k a -> r
genericFoldWithKey :: forall k a r.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> r -> r) -> r -> Trie k a -> r
genericFoldWithKey k -> a -> r -> r
f r
z Trie k a
m =
case forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m of
Maybe (GTrie (Rep k) a)
Nothing -> r
z
Just GTrie (Rep k) a
x -> forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey (k -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a x. Generic a => Rep a x -> a
to) r
z GTrie (Rep k) a
x
{-# INLINABLE genericFoldWithKey #-}
genericTraverseWithKey ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
, Applicative f
) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
genericTraverseWithKey :: forall k (f :: * -> *) a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k,
Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
genericTraverseWithKey k -> a -> f b
f Trie k a
m = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey (k -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a x. Generic a => Rep a x -> a
to)) (forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m))
{-# INLINABLE genericTraverseWithKey #-}
genericTraverseMaybeWithKey ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
, Applicative f
) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
genericTraverseMaybeWithKey :: forall k (f :: * -> *) a b.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k,
Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
genericTraverseMaybeWithKey k -> a -> f (Maybe b)
f Trie k a
m = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall b a. b -> (a -> b) -> Maybe a -> b
maybe (forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. TrieRepDefault k a
EmptyTrie) forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap) (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey (k -> a -> f (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a x. Generic a => Rep a x -> a
to)) (forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap Trie k a
m))
{-# INLINABLE genericTraverseMaybeWithKey #-}
genericMergeWithKey ::
( GTrieKey (Rep k), Generic k
, TrieRep k ~ TrieRepDefault k
) =>
(k -> a -> b -> Maybe c) -> (Trie k a -> Trie k c) -> (Trie k b -> Trie k c) ->
Trie k a -> Trie k b -> Trie k c
genericMergeWithKey :: forall k a b c.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
genericMergeWithKey k -> a -> b -> Maybe c
f Trie k a -> Trie k c
g Trie k b -> Trie k c
h (MkTrie TrieRep k a
x) (MkTrie TrieRep k b
y) =
case (TrieRep k a
x,TrieRep k b
y) of
(TrieRepDefault k a
EmptyTrie, TrieRepDefault k b
EmptyTrie) -> forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. TrieRepDefault k a
EmptyTrie
(NonEmptyTrie{} , TrieRepDefault k b
EmptyTrie) -> Trie k a -> Trie k c
g (forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k a
x)
(TrieRepDefault k a
EmptyTrie, NonEmptyTrie{} ) -> Trie k b -> Trie k c
h (forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k b
y)
(NonEmptyTrie GTrie (Rep k) a
x', NonEmptyTrie GTrie (Rep k) b
y') -> forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey (k -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a x. Generic a => Rep a x -> a
to) (forall {t} {t2} {k} {k} {a} {t1}.
(TrieRep t ~ TrieRepDefault t2, TrieRep k ~ TrieRepDefault k) =>
(Trie k a -> Trie t t1)
-> GTrie (Rep k) a -> Maybe (GTrie (Rep t2) t1)
aux Trie k a -> Trie k c
g) (forall {t} {t2} {k} {k} {a} {t1}.
(TrieRep t ~ TrieRepDefault t2, TrieRep k ~ TrieRepDefault k) =>
(Trie k a -> Trie t t1)
-> GTrie (Rep k) a -> Maybe (GTrie (Rep t2) t1)
aux Trie k b -> Trie k c
h) GTrie (Rep k) a
x' GTrie (Rep k) b
y')
where
aux :: (Trie k a -> Trie t t1)
-> GTrie (Rep k) a -> Maybe (GTrie (Rep t2) t1)
aux Trie k a -> Trie t t1
k GTrie (Rep k) a
t = forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap (Trie k a -> Trie t t1
k (forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. GTrie (Rep k) a -> TrieRepDefault k a
NonEmptyTrie GTrie (Rep k) a
t)))
{-# INLINABLE genericMergeWithKey #-}
wrap :: TrieRep k ~ TrieRepDefault k1 => Maybe (GTrie (Rep k1) a) -> Trie k a
wrap :: forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap Maybe (GTrie (Rep k1) a)
Nothing = forall k a. TrieRep k a -> Trie k a
MkTrie forall k a. TrieRepDefault k a
EmptyTrie
wrap (Just GTrie (Rep k1) a
t) = forall k a. TrieRep k a -> Trie k a
MkTrie (forall k a. GTrie (Rep k) a -> TrieRepDefault k a
NonEmptyTrie GTrie (Rep k1) a
t)
unwrap :: TrieRep t ~ TrieRepDefault t2 => Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap :: forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap (MkTrie TrieRepDefault t2 t1
TrieRep t t1
EmptyTrie) = forall a. Maybe a
Nothing
unwrap (MkTrie (NonEmptyTrie GTrie (Rep t2) t1
t)) = forall a. a -> Maybe a
Just GTrie (Rep t2) t1
t
data TrieRepDefault k a = EmptyTrie | NonEmptyTrie !(GTrie (Rep k) a)
#if __GLASGOW_HASKELL__ >= 810
type GTrie :: (Type -> Type) -> Type -> Type
data family GTrie f a
#elif MIN_VERSION_base(4,9,0)
data family GTrie (f :: Type -> Type) a
#else
data family GTrie (f :: * -> *) a
#endif
newtype instance GTrie (M1 i c f) a = MTrie (GTrie f a)
data instance GTrie (f :+: g) a = STrieL !(GTrie f a)
| STrieR !(GTrie g a)
| STrieB !(GTrie f a) !(GTrie g a)
newtype instance GTrie (f :*: g) a = PTrie (GTrie f (GTrie g a))
newtype instance GTrie (K1 i k) a = KTrie (Trie k a)
newtype instance GTrie U1 a = UTrie a
data instance GTrie V1 a
instance GTrieKey f => Functor (GTrie f) where
fmap :: forall a b. (a -> b) -> GTrie f a -> GTrie f b
fmap = forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap
class GTrieKey f where
gtrieLookup :: f p -> GTrie f a -> Maybe a
gtrieInsert :: f p -> a -> GTrie f a -> GTrie f a
gtrieSingleton :: f p -> a -> GTrie f a
gtrieDelete :: f p -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter :: f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieMap :: (a -> b) -> GTrie f a -> GTrie f b
gtrieTraverse :: Applicative m => (a -> m b) -> GTrie f a -> m (GTrie f b)
gmapMaybeWithKey :: (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gfoldWithKey :: (f p -> a -> r -> r) -> r -> GTrie f a -> r
gtraverseWithKey :: Applicative m => (f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseMaybeWithKey :: Applicative m => (f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gmergeWithKey :: (f p -> a -> b -> Maybe c) ->
(GTrie f a -> Maybe (GTrie f c)) ->
(GTrie f b -> Maybe (GTrie f c)) ->
GTrie f a -> GTrie f b -> Maybe (GTrie f c)
class GTrieKeyShow f where
gtrieShowsPrec :: Show a => Int -> GTrie f a -> ShowS
instance GTrieKey f => GTrieKey (M1 i c f) where
gtrieLookup :: forall p a. M1 i c f p -> GTrie (M1 i c f) a -> Maybe a
gtrieLookup (M1 f p
k) (MTrie GTrie f a
x) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
k GTrie f a
x
gtrieInsert :: forall p a.
M1 i c f p -> a -> GTrie (M1 i c f) a -> GTrie (M1 i c f) a
gtrieInsert (M1 f p
k) a
v (MTrie GTrie f a
t)= forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
k a
v GTrie f a
t)
gtrieSingleton :: forall p a. M1 i c f p -> a -> GTrie (M1 i c f) a
gtrieSingleton (M1 f p
k) a
v = forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
k a
v)
gtrieDelete :: forall p a.
M1 i c f p -> GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) a)
gtrieDelete (M1 f p
k) (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete f p
k GTrie f a
x)
gtrieAlter :: forall p a.
M1 i c f p
-> (Maybe a -> Maybe a)
-> GTrie (M1 i c f) a
-> Maybe (GTrie (M1 i c f) a)
gtrieAlter (M1 f p
k) Maybe a -> Maybe a
f (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
k Maybe a -> Maybe a
f GTrie f a
x)
gtrieMap :: forall a b. (a -> b) -> GTrie (M1 i c f) a -> GTrie (M1 i c f) b
gtrieMap a -> b
f (MTrie GTrie f a
x) = forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie f a
x)
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie (M1 i c f) a -> m (GTrie (M1 i c f) b)
gtrieTraverse a -> m b
f (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f GTrie f a
x)
gmapMaybeWithKey :: forall p a b.
(M1 i c f p -> a -> Maybe b)
-> GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) b)
gmapMaybeWithKey M1 i c f p -> a -> Maybe b
f (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey (M1 i c f p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
gfoldWithKey :: forall p a r.
(M1 i c f p -> a -> r -> r) -> r -> GTrie (M1 i c f) a -> r
gfoldWithKey M1 i c f p -> a -> r -> r
f r
z (MTrie GTrie f a
x) = forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey (M1 i c f p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) r
z GTrie f a
x
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(M1 i c f p -> a -> m b)
-> GTrie (M1 i c f) a -> m (GTrie (M1 i c f) b)
gtraverseWithKey M1 i c f p -> a -> m b
f (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey (M1 i c f p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(M1 i c f p -> a -> m (Maybe b))
-> GTrie (M1 i c f) a -> m (Maybe (GTrie (M1 i c f) b))
gtraverseMaybeWithKey M1 i c f p -> a -> m (Maybe b)
f (MTrie GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap coerce :: forall a b. Coercible a b => a -> b
coerce (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey (M1 i c f p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
gmergeWithKey :: forall p a b c.
(M1 i c f p -> a -> b -> Maybe c)
-> (GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) c))
-> (GTrie (M1 i c f) b -> Maybe (GTrie (M1 i c f) c))
-> GTrie (M1 i c f) a
-> GTrie (M1 i c f) b
-> Maybe (GTrie (M1 i c f) c)
gmergeWithKey M1 i c f p -> a -> b -> Maybe c
f GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) c)
g GTrie (M1 i c f) b -> Maybe (GTrie (M1 i c f) c)
h (MTrie GTrie f a
x) (MTrie GTrie f b
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey (M1 i c f p -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) (coerce :: forall a b. Coercible a b => a -> b
coerce GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) c)
g) (coerce :: forall a b. Coercible a b => a -> b
coerce GTrie (M1 i c f) b -> Maybe (GTrie (M1 i c f) c)
h) GTrie f a
x GTrie f b
y)
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieMap #-}
{-# INLINE gmapMaybeWithKey #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
#if MIN_VERSION_base(4,9,0)
data MProxy (c :: Meta) (f :: Type -> Type) a = MProxy
#else
data MProxy (c :: *) (f :: * -> *) a = MProxy
#endif
instance GTrieKeyShow f => GTrieKeyShow (M1 D d f) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (M1 D d f) a -> ShowS
gtrieShowsPrec Int
p (MTrie GTrie f a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p GTrie f a
x
instance (Constructor c, GTrieKeyShow f) => GTrieKeyShow (M1 C c f) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (M1 C c f) a -> ShowS
gtrieShowsPrec Int
p (MTrie GTrie f a
x) = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10)
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"Con "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall {k} (c :: k) k1 (t :: k -> (k1 -> *) -> k1 -> *)
(f :: k1 -> *) (a :: k1).
Constructor c =>
t c f a -> String
conName (forall (c :: Meta) (f :: * -> *) a. MProxy c f a
MProxy :: MProxy c f ()))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
instance GTrieKeyShow f => GTrieKeyShow (M1 S s f) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (M1 S s f) a -> ShowS
gtrieShowsPrec Int
p (MTrie GTrie f a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p GTrie f a
x
checkNull :: TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull :: forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull Trie k a
x
| forall k a. TrieKey k => Trie k a -> Bool
trieNull Trie k a
x = forall a. Maybe a
Nothing
| Bool
otherwise = forall a. a -> Maybe a
Just Trie k a
x
instance TrieKey k => GTrieKey (K1 i k) where
gtrieLookup :: forall p a. K1 i k p -> GTrie (K1 i k) a -> Maybe a
gtrieLookup (K1 k
k) (KTrie Trie k a
x) = forall k a. TrieKey k => k -> Trie k a -> Maybe a
trieLookup k
k Trie k a
x
gtrieInsert :: forall p a. K1 i k p -> a -> GTrie (K1 i k) a -> GTrie (K1 i k) a
gtrieInsert (K1 k
k) a
v (KTrie Trie k a
t) = forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
trieInsert k
k a
v Trie k a
t)
gtrieSingleton :: forall p a. K1 i k p -> a -> GTrie (K1 i k) a
gtrieSingleton (K1 k
k) a
v = forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => k -> a -> Trie k a
trieSingleton k
k a
v)
gtrieDelete :: forall p a.
K1 i k p -> GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) a)
gtrieDelete (K1 k
k) (KTrie Trie k a
t) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull (forall k a. TrieKey k => k -> Trie k a -> Trie k a
trieDelete k
k Trie k a
t))
gtrieAlter :: forall p a.
K1 i k p
-> (Maybe a -> Maybe a)
-> GTrie (K1 i k) a
-> Maybe (GTrie (K1 i k) a)
gtrieAlter (K1 k
k) Maybe a -> Maybe a
f (KTrie Trie k a
t) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull (forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
trieAlter k
k Maybe a -> Maybe a
f Trie k a
t))
gtrieMap :: forall a b. (a -> b) -> GTrie (K1 i k) a -> GTrie (K1 i k) b
gtrieMap a -> b
f (KTrie Trie k a
x) = forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a b. TrieKey k => (a -> b) -> Trie k a -> Trie k b
trieMap a -> b
f Trie k a
x)
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie (K1 i k) a -> m (GTrie (K1 i k) b)
gtrieTraverse a -> m b
f (KTrie Trie k a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
trieTraverse a -> m b
f Trie k a
x)
gmapMaybeWithKey :: forall p a b.
(K1 i k p -> a -> Maybe b)
-> GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) b)
gmapMaybeWithKey K1 i k p -> a -> Maybe b
f (KTrie Trie k a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull (forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
trieMapMaybeWithKey (K1 i k p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x))
gfoldWithKey :: forall p a r.
(K1 i k p -> a -> r -> r) -> r -> GTrie (K1 i k) a -> r
gfoldWithKey K1 i k p -> a -> r -> r
f r
z (KTrie Trie k a
x) = forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey (K1 i k p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i c (p :: k). c -> K1 i c p
K1) r
z Trie k a
x
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(K1 i k p -> a -> m b) -> GTrie (K1 i k) a -> m (GTrie (K1 i k) b)
gtraverseWithKey K1 i k p -> a -> m b
f (KTrie Trie k a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
trieTraverseWithKey (K1 i k p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x)
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(K1 i k p -> a -> m (Maybe b))
-> GTrie (K1 i k) a -> m (Maybe (GTrie (K1 i k) b))
gtraverseMaybeWithKey K1 i k p -> a -> m (Maybe b)
f (KTrie Trie k a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull) (forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
trieTraverseMaybeWithKey (K1 i k p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x)
gmergeWithKey :: forall p a b c.
(K1 i k p -> a -> b -> Maybe c)
-> (GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) c))
-> (GTrie (K1 i k) b -> Maybe (GTrie (K1 i k) c))
-> GTrie (K1 i k) a
-> GTrie (K1 i k) b
-> Maybe (GTrie (K1 i k) c)
gmergeWithKey K1 i k p -> a -> b -> Maybe c
f GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) c)
g GTrie (K1 i k) b -> Maybe (GTrie (K1 i k) c)
h (KTrie Trie k a
x) (KTrie Trie k b
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull (forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
trieMergeWithKey (K1 i k p -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k i c (p :: k). c -> K1 i c p
K1) Trie k a -> Trie k c
g' Trie k b -> Trie k c
h' Trie k a
x Trie k b
y))
where
g' :: Trie k a -> Trie k c
g' Trie k a
t = case GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) c)
g (forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie Trie k a
t) of
Just (KTrie Trie k c
t') -> Trie k c
t'
Maybe (GTrie (K1 i k) c)
Nothing -> forall k a. TrieKey k => Trie k a
trieEmpty
h' :: Trie k b -> Trie k c
h' Trie k b
t = case GTrie (K1 i k) b -> Maybe (GTrie (K1 i k) c)
h (forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie Trie k b
t) of
Just (KTrie Trie k c
t') -> Trie k c
t'
Maybe (GTrie (K1 i k) c)
Nothing -> forall k a. TrieKey k => Trie k a
trieEmpty
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieMap #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
{-# INLINE gmergeWithKey #-}
{-# INLINE gmapMaybeWithKey #-}
instance ShowTrieKey k => GTrieKeyShow (K1 i k) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (K1 i k) a -> ShowS
gtrieShowsPrec Int
p (KTrie Trie k a
x) = forall k a. (ShowTrieKey k, Show a) => Int -> Trie k a -> ShowS
trieShowsPrec Int
p Trie k a
x
instance (GTrieKey f, GTrieKey g) => GTrieKey (f :*: g) where
gtrieLookup :: forall p a. (:*:) f g p -> GTrie (f :*: g) a -> Maybe a
gtrieLookup (f p
i :*: g p
j) (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup g p
j forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g a)
x
gtrieInsert :: forall p a.
(:*:) f g p -> a -> GTrie (f :*: g) a -> GTrie (f :*: g) a
gtrieInsert (f p
i :*: g p
j) a
v (PTrie GTrie f (GTrie g a)
t) = case forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
i Maybe (GTrie g a) -> Maybe (GTrie g a)
f GTrie f (GTrie g a)
t of
Maybe (GTrie f (GTrie g a))
Nothing -> forall a. HasCallStack => String -> a
error String
"gtrieInsert: insertion produced an empty trie"
Just GTrie f (GTrie g a)
t' -> forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie GTrie f (GTrie g a)
t'
where
f :: Maybe (GTrie g a) -> Maybe (GTrie g a)
f Maybe (GTrie g a)
Nothing = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
j a
v
f (Just GTrie g a
u) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert g p
j a
v GTrie g a
u
gtrieDelete :: forall p a.
(:*:) f g p -> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a)
gtrieDelete (f p
i :*: g p
j) (PTrie GTrie f (GTrie g a)
t) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
i Maybe (GTrie g a) -> Maybe (GTrie g a)
f GTrie f (GTrie g a)
t)
where
f :: Maybe (GTrie g a) -> Maybe (GTrie g a)
f Maybe (GTrie g a)
Nothing = forall a. Maybe a
Nothing
f (Just GTrie g a
u) = forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete g p
j GTrie g a
u
gtrieAlter :: forall p a.
(:*:) f g p
-> (Maybe a -> Maybe a)
-> GTrie (f :*: g) a
-> Maybe (GTrie (f :*: g) a)
gtrieAlter (f p
i :*: g p
j) Maybe a -> Maybe a
f (PTrie GTrie f (GTrie g a)
t) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
i Maybe (GTrie g a) -> Maybe (GTrie g a)
g GTrie f (GTrie g a)
t)
where
g :: Maybe (GTrie g a) -> Maybe (GTrie g a)
g Maybe (GTrie g a)
Nothing =
case Maybe a -> Maybe a
f forall a. Maybe a
Nothing of
Maybe a
Nothing -> forall a. Maybe a
Nothing
Just a
v -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
j a
v
g (Just GTrie g a
u) = forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter g p
j Maybe a -> Maybe a
f GTrie g a
u
gtrieSingleton :: forall p a. (:*:) f g p -> a -> GTrie (f :*: g) a
gtrieSingleton (f p
i :*: g p
j) a
v = forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
j a
v))
gtrieMap :: forall a b. (a -> b) -> GTrie (f :*: g) a -> GTrie (f :*: g) b
gtrieMap a -> b
f (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f) GTrie f (GTrie g a)
x)
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie (f :*: g) a -> m (GTrie (f :*: g) b)
gtrieTraverse a -> m b
f (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f) GTrie f (GTrie g a)
x)
gmapMaybeWithKey :: forall p a b.
((:*:) f g p -> a -> Maybe b)
-> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) b)
gmapMaybeWithKey (:*:) f g p -> a -> Maybe b
f (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey (\f p
i -> forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey (\g p
j -> (:*:) f g p -> a -> Maybe b
f (f p
iforall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*:g p
j))) GTrie f (GTrie g a)
x)
gfoldWithKey :: forall p a r.
((:*:) f g p -> a -> r -> r) -> r -> GTrie (f :*: g) a -> r
gfoldWithKey (:*:) f g p -> a -> r -> r
f r
z (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey (\f p
i GTrie g a
m r
r -> forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey (\g p
j -> (:*:) f g p -> a -> r -> r
f (f p
iforall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*:g p
j)) r
r GTrie g a
m) r
z GTrie f (GTrie g a)
x
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
((:*:) f g p -> a -> m b)
-> GTrie (f :*: g) a -> m (GTrie (f :*: g) b)
gtraverseWithKey (:*:) f g p -> a -> m b
f (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey (\f p
i ->
forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey (\g p
j -> (:*:) f g p -> a -> m b
f (f p
i forall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*: g p
j))) GTrie f (GTrie g a)
x)
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
((:*:) f g p -> a -> m (Maybe b))
-> GTrie (f :*: g) a -> m (Maybe (GTrie (f :*: g) b))
gtraverseMaybeWithKey (:*:) f g p -> a -> m (Maybe b)
f (PTrie GTrie f (GTrie g a)
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie) (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey (\f p
i ->
forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey (\g p
j -> (:*:) f g p -> a -> m (Maybe b)
f (f p
i forall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*: g p
j))) GTrie f (GTrie g a)
x)
gmergeWithKey :: forall p a b c.
((:*:) f g p -> a -> b -> Maybe c)
-> (GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c))
-> (GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c))
-> GTrie (f :*: g) a
-> GTrie (f :*: g) b
-> Maybe (GTrie (f :*: g) c)
gmergeWithKey (:*:) f g p -> a -> b -> Maybe c
f GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c)
g GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c)
h (PTrie GTrie f (GTrie g a)
x) (PTrie GTrie f (GTrie g b)
y) =
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie forall a b. (a -> b) -> a -> b
$!
forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey
(\f p
i ->
forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey
(\g p
j -> (:*:) f g p -> a -> b -> Maybe c
f (f p
iforall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*:g p
j))
(f p -> GTrie g a -> Maybe (GTrie g c)
g' f p
i)
(f p -> GTrie g b -> Maybe (GTrie g c)
h' f p
i))
(coerce :: forall a b. Coercible a b => a -> b
coerce GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c)
g)
(coerce :: forall a b. Coercible a b => a -> b
coerce GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c)
h)
GTrie f (GTrie g a)
x
GTrie f (GTrie g b)
y
where
g' :: f p -> GTrie g a -> Maybe (GTrie g c)
g' f p
i GTrie g a
t = do PTrie GTrie f (GTrie g c)
t' <- GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c)
g (forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i GTrie g a
t))
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g c)
t'
h' :: f p -> GTrie g b -> Maybe (GTrie g c)
h' f p
i GTrie g b
t = do PTrie GTrie f (GTrie g c)
t' <- GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c)
h (forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i GTrie g b
t))
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g c)
t'
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieMap #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
{-# INLINE gmergeWithKey #-}
{-# INLINE gmapMaybeWithKey #-}
instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :*: g) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (f :*: g) a -> ShowS
gtrieShowsPrec Int
p (PTrie GTrie f (GTrie g a)
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p GTrie f (GTrie g a)
x
instance (GTrieKey f, GTrieKey g) => GTrieKey (f :+: g) where
gtrieLookup :: forall p a. (:+:) f g p -> GTrie (f :+: g) a -> Maybe a
gtrieLookup (L1 f p
k) (STrieL GTrie f a
x) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
k GTrie f a
x
gtrieLookup (L1 f p
k) (STrieB GTrie f a
x GTrie g a
_) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
k GTrie f a
x
gtrieLookup (R1 g p
k) (STrieR GTrie g a
y) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup g p
k GTrie g a
y
gtrieLookup (R1 g p
k) (STrieB GTrie f a
_ GTrie g a
y) = forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup g p
k GTrie g a
y
gtrieLookup (:+:) f g p
_ GTrie (f :+: g) a
_ = forall a. Maybe a
Nothing
gtrieInsert :: forall p a.
(:+:) f g p -> a -> GTrie (f :+: g) a -> GTrie (f :+: g) a
gtrieInsert (L1 f p
k) a
v (STrieL GTrie f a
x) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
k a
v GTrie f a
x)
gtrieInsert (L1 f p
k) a
v (STrieR GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
k a
v) GTrie g a
y
gtrieInsert (L1 f p
k) a
v (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
k a
v GTrie f a
x) GTrie g a
y
gtrieInsert (R1 g p
k) a
v (STrieL GTrie f a
x) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
k a
v)
gtrieInsert (R1 g p
k) a
v (STrieR GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert g p
k a
v GTrie g a
y)
gtrieInsert (R1 g p
k) a
v (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x (forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert g p
k a
v GTrie g a
y)
gtrieSingleton :: forall p a. (:+:) f g p -> a -> GTrie (f :+: g) a
gtrieSingleton (L1 f p
k) a
v = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
k a
v)
gtrieSingleton (R1 g p
k) a
v = forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
k a
v)
gtrieDelete :: forall p a.
(:+:) f g p -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
gtrieDelete (L1 f p
k) (STrieL GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete f p
k GTrie f a
x
gtrieDelete (L1 f p
_) (STrieR GTrie g a
y) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y
gtrieDelete (L1 f p
k) (STrieB GTrie f a
x GTrie g a
y) = case forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete f p
k GTrie f a
x of
Maybe (GTrie f a)
Nothing -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y
Just GTrie f a
x' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x' GTrie g a
y
gtrieDelete (R1 g p
_) (STrieL GTrie f a
x) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x
gtrieDelete (R1 g p
k) (STrieR GTrie g a
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete g p
k GTrie g a
y
gtrieDelete (R1 g p
k) (STrieB GTrie f a
x GTrie g a
y) = case forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete g p
k GTrie g a
y of
Maybe (GTrie g a)
Nothing -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x
Just GTrie g a
y' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x GTrie g a
y'
gtrieAlter :: forall p a.
(:+:) f g p
-> (Maybe a -> Maybe a)
-> GTrie (f :+: g) a
-> Maybe (GTrie (f :+: g) a)
gtrieAlter (L1 f p
k) Maybe a -> Maybe a
f (STrieL GTrie f a
x) = do
GTrie f a
x' <- forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
k Maybe a -> Maybe a
f GTrie f a
x
forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x'
gtrieAlter (L1 f p
k) Maybe a -> Maybe a
f t :: GTrie (f :+: g) a
t@(STrieR GTrie g a
y) = case Maybe a -> Maybe a
f forall a. Maybe a
Nothing of
Maybe a
Nothing -> forall a. a -> Maybe a
Just GTrie (f :+: g) a
t
Just a
v -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
k a
v) GTrie g a
y
gtrieAlter (L1 f p
k) Maybe a -> Maybe a
f (STrieB GTrie f a
x GTrie g a
y) = case forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter f p
k Maybe a -> Maybe a
f GTrie f a
x of
Just GTrie f a
x' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x' GTrie g a
y
Maybe (GTrie f a)
Nothing -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y
gtrieAlter (R1 g p
k) Maybe a -> Maybe a
f (STrieR GTrie g a
y) = do
GTrie g a
y' <- forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter g p
k Maybe a -> Maybe a
f GTrie g a
y
forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y'
gtrieAlter (R1 g p
k) Maybe a -> Maybe a
f t :: GTrie (f :+: g) a
t@(STrieL GTrie f a
x) = case Maybe a -> Maybe a
f forall a. Maybe a
Nothing of
Maybe a
Nothing -> forall a. a -> Maybe a
Just GTrie (f :+: g) a
t
Just a
v -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x (forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
k a
v)
gtrieAlter (R1 g p
k) Maybe a -> Maybe a
f (STrieB GTrie f a
x GTrie g a
y) = case forall (f :: * -> *) p a.
GTrieKey f =>
f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)
gtrieAlter g p
k Maybe a -> Maybe a
f GTrie g a
y of
Just GTrie g a
y' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x GTrie g a
y'
Maybe (GTrie g a)
Nothing -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x
gtrieMap :: forall a b. (a -> b) -> GTrie (f :+: g) a -> GTrie (f :+: g) b
gtrieMap a -> b
f (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie f a
x) (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie g a
y)
gtrieMap a -> b
f (STrieL GTrie f a
x) = forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie f a
x)
gtrieMap a -> b
f (STrieR GTrie g a
y) = forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie g a
y)
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie (f :+: g) a -> m (GTrie (f :+: g) b)
gtrieTraverse a -> m b
f (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f GTrie f a
x) (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f GTrie g a
y)
gtrieTraverse a -> m b
f (STrieL GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f GTrie f a
x)
gtrieTraverse a -> m b
f (STrieR GTrie g a
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> m b
f GTrie g a
y)
gmapMaybeWithKey :: forall p a b.
((:+:) f g p -> a -> Maybe b)
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) b)
gmapMaybeWithKey (:+:) f g p -> a -> Maybe b
f (STrieL GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey ((:+:) f g p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x
gmapMaybeWithKey (:+:) f g p -> a -> Maybe b
f (STrieR GTrie g a
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey ((:+:) f g p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y
gmapMaybeWithKey (:+:) f g p -> a -> Maybe b
f (STrieB GTrie f a
x GTrie g a
y) = case (forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey ((:+:) f g p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x, forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey ((:+:) f g p -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y) of
(Maybe (GTrie f b)
Nothing, Maybe (GTrie g b)
Nothing) -> forall a. Maybe a
Nothing
(Just GTrie f b
x', Maybe (GTrie g b)
Nothing) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f b
x'
(Maybe (GTrie f b)
Nothing, Just GTrie g b
y') -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g b
y'
(Just GTrie f b
x', Just GTrie g b
y') -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f b
x' GTrie g b
y'
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
((:+:) f g p -> a -> m (Maybe b))
-> GTrie (f :+: g) a -> m (Maybe (GTrie (f :+: g) b))
gtraverseMaybeWithKey (:+:) f g p -> a -> m (Maybe b)
f (STrieL GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey ((:+:) f g p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x
gtraverseMaybeWithKey (:+:) f g p -> a -> m (Maybe b)
f (STrieR GTrie g a
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey ((:+:) f g p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y
gtraverseMaybeWithKey (:+:) f g p -> a -> m (Maybe b)
f (STrieB GTrie f a
x GTrie g a
y) =
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 forall {f :: * -> *} {a} {g :: * -> *}.
Maybe (GTrie f a) -> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
finish (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey ((:+:) f g p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x) (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))
gtraverseMaybeWithKey ((:+:) f g p -> a -> m (Maybe b)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y)
where
finish :: Maybe (GTrie f a) -> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
finish Maybe (GTrie f a)
Nothing Maybe (GTrie g a)
Nothing = forall a. Maybe a
Nothing
finish (Just GTrie f a
x') Maybe (GTrie g a)
Nothing = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x'
finish Maybe (GTrie f a)
Nothing (Just GTrie g a
y') = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y'
finish (Just GTrie f a
x') (Just GTrie g a
y') = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x' GTrie g a
y'
gfoldWithKey :: forall p a r.
((:+:) f g p -> a -> r -> r) -> r -> GTrie (f :+: g) a -> r
gfoldWithKey (:+:) f g p -> a -> r -> r
f r
z (STrieL GTrie f a
x) = forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey ((:+:) f g p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) r
z GTrie f a
x
gfoldWithKey (:+:) f g p -> a -> r -> r
f r
z (STrieR GTrie g a
y) = forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey ((:+:) f g p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) r
z GTrie g a
y
gfoldWithKey (:+:) f g p -> a -> r -> r
f r
z (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey ((:+:) f g p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) (forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey ((:+:) f g p -> a -> r -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) r
z GTrie g a
y) GTrie f a
x
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
((:+:) f g p -> a -> m b)
-> GTrie (f :+: g) a -> m (GTrie (f :+: g) b)
gtraverseWithKey (:+:) f g p -> a -> m b
f (STrieL GTrie f a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey ((:+:) f g p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x)
gtraverseWithKey (:+:) f g p -> a -> m b
f (STrieR GTrie g a
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey ((:+:) f g p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y)
gtraverseWithKey (:+:) f g p -> a -> m b
f (STrieB GTrie f a
x GTrie g a
y) = forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey ((:+:) f g p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x)
(forall (f :: * -> *) (m :: * -> *) p a b.
(GTrieKey f, Applicative m) =>
(f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gtraverseWithKey ((:+:) f g p -> a -> m b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y)
gmergeWithKey :: forall p a b c.
((:+:) f g p -> a -> b -> Maybe c)
-> (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c))
-> (GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c))
-> GTrie (f :+: g) a
-> GTrie (f :+: g) b
-> Maybe (GTrie (f :+: g) c)
gmergeWithKey (:+:) f g p -> a -> b -> Maybe c
f GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c)
g GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c)
h GTrie (f :+: g) a
x0 GTrie (f :+: g) b
y0 =
case (forall {f :: * -> *} {g :: * -> *} {a}.
GTrie (f :+: g) a -> (Maybe (GTrie f a), Maybe (GTrie g a))
split GTrie (f :+: g) a
x0, forall {f :: * -> *} {g :: * -> *} {a}.
GTrie (f :+: g) a -> (Maybe (GTrie f a), Maybe (GTrie g a))
split GTrie (f :+: g) b
y0) of
((Maybe (GTrie f a)
xl,Maybe (GTrie g a)
xr),(Maybe (GTrie f b)
yl,Maybe (GTrie g b)
yr)) -> forall {f :: * -> *} {a} {g :: * -> *}.
Maybe (GTrie f a) -> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
build (Maybe (GTrie f a) -> Maybe (GTrie f b) -> Maybe (GTrie f c)
mergel Maybe (GTrie f a)
xl Maybe (GTrie f b)
yl) (Maybe (GTrie g a) -> Maybe (GTrie g b) -> Maybe (GTrie g c)
merger Maybe (GTrie g a)
xr Maybe (GTrie g b)
yr)
where
split :: GTrie (f :+: g) a -> (Maybe (GTrie f a), Maybe (GTrie g a))
split (STrieL GTrie f a
x) = (forall a. a -> Maybe a
Just GTrie f a
x, forall a. Maybe a
Nothing)
split (STrieR GTrie g a
y) = (forall a. Maybe a
Nothing, forall a. a -> Maybe a
Just GTrie g a
y)
split (STrieB GTrie f a
x GTrie g a
y) = (forall a. a -> Maybe a
Just GTrie f a
x, forall a. a -> Maybe a
Just GTrie g a
y)
build :: Maybe (GTrie f a) -> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
build (Just GTrie f a
x) (Just GTrie g a
y) = forall a. a -> Maybe a
Just (forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x GTrie g a
y)
build (Just GTrie f a
x) Maybe (GTrie g a)
Nothing = forall a. a -> Maybe a
Just (forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x)
build Maybe (GTrie f a)
Nothing (Just GTrie g a
y) = forall a. a -> Maybe a
Just (forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y)
build Maybe (GTrie f a)
Nothing Maybe (GTrie g a)
Nothing = forall a. Maybe a
Nothing
mergel :: Maybe (GTrie f a) -> Maybe (GTrie f b) -> Maybe (GTrie f c)
mergel Maybe (GTrie f a)
Nothing Maybe (GTrie f b)
Nothing = forall a. Maybe a
Nothing
mergel (Just GTrie f a
x) Maybe (GTrie f b)
Nothing = GTrie f a -> Maybe (GTrie f c)
gl GTrie f a
x
mergel Maybe (GTrie f a)
Nothing (Just GTrie f b
y) = GTrie f b -> Maybe (GTrie f c)
hl GTrie f b
y
mergel (Just GTrie f a
x) (Just GTrie f b
y) = forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey ((:+:) f g p -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a -> Maybe (GTrie f c)
gl GTrie f b -> Maybe (GTrie f c)
hl GTrie f a
x GTrie f b
y
merger :: Maybe (GTrie g a) -> Maybe (GTrie g b) -> Maybe (GTrie g c)
merger Maybe (GTrie g a)
Nothing Maybe (GTrie g b)
Nothing = forall a. Maybe a
Nothing
merger (Just GTrie g a
x) Maybe (GTrie g b)
Nothing = GTrie g a -> Maybe (GTrie g c)
gr GTrie g a
x
merger Maybe (GTrie g a)
Nothing (Just GTrie g b
y) = GTrie g b -> Maybe (GTrie g c)
hr GTrie g b
y
merger (Just GTrie g a
x) (Just GTrie g b
y) = forall (f :: * -> *) p a b c.
GTrieKey f =>
(f p -> a -> b -> Maybe c)
-> (GTrie f a -> Maybe (GTrie f c))
-> (GTrie f b -> Maybe (GTrie f c))
-> GTrie f a
-> GTrie f b
-> Maybe (GTrie f c)
gmergeWithKey ((:+:) f g p -> a -> b -> Maybe c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a -> Maybe (GTrie g c)
gr GTrie g b -> Maybe (GTrie g c)
hr GTrie g a
x GTrie g b
y
gl :: GTrie f a -> Maybe (GTrie f c)
gl GTrie f a
t = do STrieL GTrie f c
t' <- GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c)
g (forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
t)
forall (m :: * -> *) a. Monad m => a -> m a
return GTrie f c
t'
gr :: GTrie g a -> Maybe (GTrie g c)
gr GTrie g a
t = do STrieR GTrie g c
t' <- GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c)
g (forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
t)
forall (m :: * -> *) a. Monad m => a -> m a
return GTrie g c
t'
hl :: GTrie f b -> Maybe (GTrie f c)
hl GTrie f b
t = do STrieL GTrie f c
t' <- GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c)
h (forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f b
t)
forall (m :: * -> *) a. Monad m => a -> m a
return GTrie f c
t'
hr :: GTrie g b -> Maybe (GTrie g c)
hr GTrie g b
t = do STrieR GTrie g c
t' <- GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c)
h (forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g b
t)
forall (m :: * -> *) a. Monad m => a -> m a
return GTrie g c
t'
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gtrieMap #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
{-# INLINE gmergeWithKey #-}
{-# INLINE gmapMaybeWithKey #-}
instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :+: g) where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie (f :+: g) a -> ShowS
gtrieShowsPrec Int
p (STrieB GTrie f a
x GTrie g a
y) = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10)
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieB "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie g a
y
gtrieShowsPrec Int
p (STrieL GTrie f a
x) = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10)
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieL "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
gtrieShowsPrec Int
p (STrieR GTrie g a
y) = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10)
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieR "
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie g a
y
instance GTrieKey U1 where
gtrieLookup :: forall p a. U1 p -> GTrie U1 a -> Maybe a
gtrieLookup U1 p
_ (UTrie a
x) = forall a. a -> Maybe a
Just a
x
gtrieInsert :: forall p a. U1 p -> a -> GTrie U1 a -> GTrie U1 a
gtrieInsert U1 p
_ a
v GTrie U1 a
_ = forall a. a -> GTrie U1 a
UTrie a
v
gtrieDelete :: forall p a. U1 p -> GTrie U1 a -> Maybe (GTrie U1 a)
gtrieDelete U1 p
_ GTrie U1 a
_ = forall a. Maybe a
Nothing
gtrieAlter :: forall p a.
U1 p -> (Maybe a -> Maybe a) -> GTrie U1 a -> Maybe (GTrie U1 a)
gtrieAlter U1 p
_ Maybe a -> Maybe a
f (UTrie a
x) = case Maybe a -> Maybe a
f (forall a. a -> Maybe a
Just a
x) of
Maybe a
Nothing -> forall a. Maybe a
Nothing
Just a
x' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall a. a -> GTrie U1 a
UTrie a
x'
gtrieSingleton :: forall p a. U1 p -> a -> GTrie U1 a
gtrieSingleton U1 p
_ = forall a. a -> GTrie U1 a
UTrie
gtrieMap :: forall a b. (a -> b) -> GTrie U1 a -> GTrie U1 b
gtrieMap a -> b
f (UTrie a
x) = forall a. a -> GTrie U1 a
UTrie (a -> b
f a
x)
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie U1 a -> m (GTrie U1 b)
gtrieTraverse a -> m b
f (UTrie a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> GTrie U1 a
UTrie (a -> m b
f a
x)
gmapMaybeWithKey :: forall p a b.
(U1 p -> a -> Maybe b) -> GTrie U1 a -> Maybe (GTrie U1 b)
gmapMaybeWithKey U1 p -> a -> Maybe b
f (UTrie a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> GTrie U1 a
UTrie forall a b. (a -> b) -> a -> b
$! U1 p -> a -> Maybe b
f forall k (p :: k). U1 p
U1 a
x
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(U1 p -> a -> m (Maybe b)) -> GTrie U1 a -> m (Maybe (GTrie U1 b))
gtraverseMaybeWithKey U1 p -> a -> m (Maybe b)
f (UTrie a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> GTrie U1 a
UTrie) forall a b. (a -> b) -> a -> b
$! U1 p -> a -> m (Maybe b)
f forall k (p :: k). U1 p
U1 a
x
gfoldWithKey :: forall p a r. (U1 p -> a -> r -> r) -> r -> GTrie U1 a -> r
gfoldWithKey U1 p -> a -> r -> r
f r
z (UTrie a
x) = U1 p -> a -> r -> r
f forall k (p :: k). U1 p
U1 a
x r
z
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(U1 p -> a -> m b) -> GTrie U1 a -> m (GTrie U1 b)
gtraverseWithKey U1 p -> a -> m b
f (UTrie a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> GTrie U1 a
UTrie (U1 p -> a -> m b
f forall k (p :: k). U1 p
U1 a
x)
gmergeWithKey :: forall p a b c.
(U1 p -> a -> b -> Maybe c)
-> (GTrie U1 a -> Maybe (GTrie U1 c))
-> (GTrie U1 b -> Maybe (GTrie U1 c))
-> GTrie U1 a
-> GTrie U1 b
-> Maybe (GTrie U1 c)
gmergeWithKey U1 p -> a -> b -> Maybe c
f GTrie U1 a -> Maybe (GTrie U1 c)
_ GTrie U1 b -> Maybe (GTrie U1 c)
_ (UTrie a
x) (UTrie b
y) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> GTrie U1 a
UTrie forall a b. (a -> b) -> a -> b
$! U1 p -> a -> b -> Maybe c
f forall k (p :: k). U1 p
U1 a
x b
y
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gtrieMap #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
{-# INLINE gmergeWithKey #-}
{-# INLINE gmapMaybeWithKey #-}
instance GTrieKeyShow U1 where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie U1 a -> ShowS
gtrieShowsPrec Int
p (UTrie a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p a
x
instance GTrieKey V1 where
gtrieLookup :: forall p a. V1 p -> GTrie V1 a -> Maybe a
gtrieLookup V1 p
_ GTrie V1 a
t = case GTrie V1 a
t of
gtrieInsert :: forall p a. V1 p -> a -> GTrie V1 a -> GTrie V1 a
gtrieInsert V1 p
_ a
_ GTrie V1 a
t = case GTrie V1 a
t of
gtrieDelete :: forall p a. V1 p -> GTrie V1 a -> Maybe (GTrie V1 a)
gtrieDelete V1 p
_ GTrie V1 a
t = case GTrie V1 a
t of
gtrieAlter :: forall p a.
V1 p -> (Maybe a -> Maybe a) -> GTrie V1 a -> Maybe (GTrie V1 a)
gtrieAlter V1 p
_ Maybe a -> Maybe a
_ GTrie V1 a
t = case GTrie V1 a
t of
gtrieSingleton :: forall p a. V1 p -> a -> GTrie V1 a
gtrieSingleton V1 p
k a
_ = case V1 p
k of
gtrieMap :: forall a b. (a -> b) -> GTrie V1 a -> GTrie V1 b
gtrieMap a -> b
_ GTrie V1 a
t = case GTrie V1 a
t of
gtrieTraverse :: forall (m :: * -> *) a b.
Applicative m =>
(a -> m b) -> GTrie V1 a -> m (GTrie V1 b)
gtrieTraverse a -> m b
_ GTrie V1 a
t = case GTrie V1 a
t of
gmapMaybeWithKey :: forall p a b.
(V1 p -> a -> Maybe b) -> GTrie V1 a -> Maybe (GTrie V1 b)
gmapMaybeWithKey V1 p -> a -> Maybe b
_ GTrie V1 a
t = case GTrie V1 a
t of
gfoldWithKey :: forall p a r. (V1 p -> a -> r -> r) -> r -> GTrie V1 a -> r
gfoldWithKey V1 p -> a -> r -> r
_ r
_ GTrie V1 a
t = case GTrie V1 a
t of
gtraverseWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(V1 p -> a -> m b) -> GTrie V1 a -> m (GTrie V1 b)
gtraverseWithKey V1 p -> a -> m b
_ GTrie V1 a
t = case GTrie V1 a
t of
gtraverseMaybeWithKey :: forall (m :: * -> *) p a b.
Applicative m =>
(V1 p -> a -> m (Maybe b)) -> GTrie V1 a -> m (Maybe (GTrie V1 b))
gtraverseMaybeWithKey V1 p -> a -> m (Maybe b)
_ GTrie V1 a
t = case GTrie V1 a
t of
gmergeWithKey :: forall p a b c.
(V1 p -> a -> b -> Maybe c)
-> (GTrie V1 a -> Maybe (GTrie V1 c))
-> (GTrie V1 b -> Maybe (GTrie V1 c))
-> GTrie V1 a
-> GTrie V1 b
-> Maybe (GTrie V1 c)
gmergeWithKey V1 p -> a -> b -> Maybe c
_ GTrie V1 a -> Maybe (GTrie V1 c)
_ GTrie V1 b -> Maybe (GTrie V1 c)
_ GTrie V1 a
t GTrie V1 b
_ = case GTrie V1 a
t of
{-# INLINE gtrieLookup #-}
{-# INLINE gtrieInsert #-}
{-# INLINE gtrieDelete #-}
{-# INLINE gtrieAlter #-}
{-# INLINE gtrieSingleton #-}
{-# INLINE gtrieMap #-}
{-# INLINE gtrieTraverse #-}
{-# INLINE gfoldWithKey #-}
{-# INLINE gtraverseWithKey #-}
{-# INLINE gtraverseMaybeWithKey #-}
{-# INLINE gmergeWithKey #-}
{-# INLINE gmapMaybeWithKey #-}
instance GTrieKeyShow V1 where
gtrieShowsPrec :: forall a. Show a => Int -> GTrie V1 a -> ShowS
gtrieShowsPrec Int
_ GTrie V1 a
_ = String -> ShowS
showString String
"()"
instance (TrieKey k, Show k, Show a) => Show (Trie k a) where
showsPrec :: Int -> Trie k a -> ShowS
showsPrec Int
d Trie k a
m = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall k a. TrieKey k => Trie k a -> [(k, a)]
toList Trie k a
m)
instance (Show a, GTrieKeyShow f) => Show (GTrie f a) where
showsPrec :: Int -> GTrie f a -> ShowS
showsPrec = forall (f :: * -> *) a.
(GTrieKeyShow f, Show a) =>
Int -> GTrie f a -> ShowS
gtrieShowsPrec
instance TrieKey k => Functor (Trie k) where
fmap :: forall a b. (a -> b) -> Trie k a -> Trie k b
fmap = forall k a b. TrieKey k => (a -> b) -> Trie k a -> Trie k b
trieMap
instance TrieKey k => Foldable.Foldable (Trie k) where
foldMap :: forall m a. Monoid m => (a -> m) -> Trie k a -> m
foldMap = forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
Traversable.foldMapDefault
foldr :: forall a b. (a -> b -> b) -> b -> Trie k a -> b
foldr a -> b -> b
f = forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey (\k
_ -> a -> b -> b
f)
#if MIN_VERSION_base(4,8,0)
null :: forall a. Trie k a -> Bool
null = forall k a. TrieKey k => Trie k a -> Bool
trieNull
#endif
instance TrieKey k => Traversable (Trie k) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie k a -> f (Trie k b)
traverse = forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
trieTraverse