{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE Trustworthy #-} -- coerce
{-# LANGUAGE CPP #-} -- MProxy on ghc >= 8
{-# LANGUAGE EmptyCase #-}
#if __GLASGOW_HASKELL__ >= 810
{-# LANGUAGE StandaloneKindSignatures #-}
#endif
#if MIN_VERSION_base(4,9,0)
{-# LANGUAGE DataKinds #-} -- Meta
#endif

-- | Unstable implementation details
module Data.GenericTrie.Internal
  ( TrieKey(..)
  , ShowTrieKey(..)
  , Trie(..)
  , OrdKey(..)
  , toList
  -- * Generic derivation implementation
  , 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

-- | Types that may be used as the key of a 'Trie'.
--
-- For @data@ declarations, the instance can be automatically derived from
-- a 'Generic' instance.
class TrieKey k where

  -- | Type of the representation of tries for this key.
#if MIN_VERSION_base(4,9,0)
  type TrieRep k :: Type -> Type
#else
  type TrieRep k :: * -> *
#endif

  -- | Construct an empty trie
  trieEmpty :: Trie k a

  -- | Test for an empty trie
  trieNull :: Trie k a -> Bool

  -- | Lookup element from trie
  trieLookup :: k -> Trie k a -> Maybe a

  -- | Insert element into trie
  trieInsert :: k -> a -> Trie k a -> Trie k a

  -- | Delete element from trie
  trieDelete :: k -> Trie k a -> Trie k a

  -- | Insert, modify, or remove an element in a trie
  trieAlter :: k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a

  -- | Construct a trie holding a single value
  trieSingleton :: k -> a -> Trie k a

  -- | Apply a function to all values stored in a trie
  trieMap :: (a -> b) -> Trie k a -> Trie k b

  -- | Traverse the values stored in a trie
  trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b)

  -- | Apply a function to the values of a 'Trie' and keep the elements
  -- of the trie that result in a 'Just' value.
  trieMapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b

  -- | Fold a trie with a function of both key and value.
  trieFoldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r

  -- | Traverse a trie with a function of both key and value.
  trieTraverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b)

  -- | Traverse a trie with a function of both key and value, and keep the elements
  -- of the trie that result in a 'Just' value.
  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


  -- Defaults using 'Generic'

  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

-- | A map from keys of type @k@, to values of type @a@.
newtype Trie k a = MkTrie (TrieRep k a)

-- | Transform a trie to an association list.
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
  -- | Show a representation of the internal structure of a trie
  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


------------------------------------------------------------------------------
-- Manually derived instances for base types
------------------------------------------------------------------------------

-- | 'Int' tries are implemented with 'IntMap'.
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 #-}

-- | 'Integer' tries are implemented with 'Map'.
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)
-- | 'Natural' tries are implemented with 'Map'.
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

-- | 'Word' tries are implemented with 'IntMap'.
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 #-}

-- | 'Char' tries are implemented with 'IntMap'.
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 #-}

-- | Tries indexed by 'OrdKey' will be represented as an ordinary 'Map'
-- and the keys will be compared based on the 'Ord' instance for @k@.
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)

-- | 'OrdKey' tries are implemented with 'Map', this is
-- intended for cases where it is better for some reason
-- to force the use of a 'Map' than to use the generically
-- derived structure.
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 #-}

------------------------------------------------------------------------------
-- Automatically derived instances for common types
------------------------------------------------------------------------------

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

------------------------------------------------------------------------------
-- Generic 'TrieKey' method implementations
------------------------------------------------------------------------------

-- | Generic implementation of 'lookup'. This is the default implementation.
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 #-}

-- | Generic implementation of 'trieNull'. This is the default implementation.
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 #-}

-- | Generic implementation of 'singleton'. This is the default implementation.
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 #-}

-- | Generic implementation of 'empty'. This is the default implementation.
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 #-}

-- | Generic implementation of 'insert'. This is the default implementation.
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 #-}

-- | Generic implementation of 'delete'. This is the default implementation.
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 #-}

-- | Generic implementation of 'alter'. This is the default implementation.
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 #-}

-- | Generic implementation of 'trieMap'. This is the default implementation.
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 #-}


-- | Generic implementation of 'trieTraverse'. This is the default implementation.
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 #-}

-- | Generic implementation of 'trieShowsPrec'. This is the default implementation.
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 #-}

-- | Generic implementation of 'mapMaybe'. This is the default implementation.
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 #-}

-- | Generic implementation of 'foldWithKey'. This is the default implementation.
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 #-}

-- | Generic implementation of 'traverseWithKey'. This is the default implementation.
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 #-}

-- | Generic implementation of 'traverseMaybeWithKey'. This is the default implementation.
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 #-}

-- | Generic implementation of 'mergeWithKey'. This is the default implementation.
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


------------------------------------------------------------------------------
-- Generic implementation class
------------------------------------------------------------------------------

-- | The default implementation of a 'TrieRep' is 'GTrie' wrapped in
-- a 'Maybe'. This wrapping is due to the 'GTrie' being a non-empty
-- trie allowing all the of the "emptiness" to be represented at the
-- top level for any given generically implemented key.
data TrieRepDefault k a = EmptyTrie | NonEmptyTrie !(GTrie (Rep k) a)

-- | Mapping of generic representation of keys to trie structures.
#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

-- | TrieKey operations on Generic representations used to provide
-- the default implementations of tries.
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)

-- | The 'GTrieKeyShow' class provides generic implementations
-- of 'showsPrec'. This class is separate due to its implementation
-- varying for different kinds of metadata.
class GTrieKeyShow f where
  gtrieShowsPrec :: Show a => Int -> GTrie f a -> ShowS

------------------------------------------------------------------------------
-- Generic implementation for metadata
------------------------------------------------------------------------------

-- | Generic metadata is skipped in trie representation and operations.
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

------------------------------------------------------------------------------
-- Generic implementation for fields
------------------------------------------------------------------------------

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

-- | Generic fields are represented by tries of the field type.
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

------------------------------------------------------------------------------
-- Generic implementation for products
------------------------------------------------------------------------------

-- | Generic products are represented by tries of tries.
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
  -- The "impossible" error is unfortunate. We *could* add another function
  --
  --   ginsertChange :: f i -> (Maybe a -> a) -> GTrie i a -> GTrie i a
  --
  -- and use that, but that would only push the "impossible" errors to the
  -- implementations using `Map` and `IntMap`, which doesn't seem to help.
                                            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) -> 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) -> 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) -> 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


------------------------------------------------------------------------------
-- Generic implementation for sums
------------------------------------------------------------------------------

-- | Generic sums are represented by up to a pair of sub-tries.
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

------------------------------------------------------------------------------
-- Generic implementation for units
------------------------------------------------------------------------------

-- | Tries of constructors without fields are represented by a single value.
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

------------------------------------------------------------------------------
-- Generic implementation for empty types
------------------------------------------------------------------------------

-- | Tries of types without constructors are represented by an empty type.
instance GTrieKey V1 where
-- Why is this represented by an empty type? One might expect it would
-- be represented by a unit type, as there is exactly one total function
-- from any empty type to any other type. First, remember that
-- TrieRepDefault offers an EmptyTrie constructor. So a TrieMap Void x
-- will be represented by that. Next, note that while the generic Rep
-- types can be put together in arbitrary ways, derived Generic instances (which
-- are the only ones that matter) are always structured as sums of products,
-- and only use V1 at the outermost level. That is, V1 will only appear in a
-- generic representation if it is the only thing there (aside from M1
-- wrappers). In particular, the only GTrie types that contain V1 are ones
-- for empty types, which are adequately represented by EmptyTrie. Indeed,
-- if we offered an inhabited GTrie for a Void type, we'd run into trouble,
-- because then we'd falsely claim that the TrieMap from Void isn't null!
  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
"()"


------------------------------------------------------------------------------
-- Various instances for Trie
------------------------------------------------------------------------------

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