{-# 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 MIN_VERSION_base(4,9,0)
{-# LANGUAGE DataKinds #-} -- Meta
#endif

{-# OPTIONS_GHC -Wno-unused-imports #-}

-- Copyright (c) 2014, Eric Mertens
--
-- All rights reserved.
--
-- Redistribution and use in source and binary forms, with or without
-- modification, are permitted provided that the following conditions are met:
--
--     * Redistributions of source code must retain the above copyright
--       notice, this list of conditions and the following disclaimer.
--
--     * Redistributions in binary form must reproduce the above
--       copyright notice, this list of conditions and the following
--       disclaimer in the documentation and/or other materials provided
--       with the distribution.
--
--     * Neither the name of Eric Mertens nor the names of other
--       contributors may be used to endorse or promote products derived
--       from this software without specific prior written permission.
--
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

-- | Unstable implementation details
module Data.GenericTrie.Internal
  ( TrieKey(..)
  , ShowTrieKey(..)
  , Trie(..)
  , OrdKey(..)
  -- * Generic derivation implementation
  , genericTrieNull
  , genericTrieMap
  , genericTrieTraverse
  , genericTrieShowsPrec
  , genericInsert
  , genericLookup
  , genericDelete
  , genericMapMaybeWithKey
  , genericSingleton
  , genericEmpty
  , genericFoldWithKey
  , genericTraverseWithKey
  , genericTraverseMaybeWithKey
  , TrieRepDefault
  , GTrieKey(..)
  , GTrie(..)
  ) where

import Control.Applicative (Applicative, liftA2)
import Data.Char (chr, ord)
import Data.Coerce (coerce)
import Data.Foldable (Foldable)
import Data.IntMap (IntMap)
import Data.Map (Map)
import Data.Maybe (isNothing)
import Data.Traversable (Traversable,traverse)
import Data.Word (Word)
import GHC.Generics
import qualified Data.Foldable as Foldable
import qualified Data.IntMap as IntMap
import qualified Data.Map as Map
import Prelude
import Data.Void (Void)
import Numeric.Natural

-- | 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.
  type TrieRep k :: * -> *

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

  -- | 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 = Trie k a
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 = k -> a -> Trie k a
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 = Trie k a -> Bool
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 = k -> Trie k a -> Maybe a
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 = k -> a -> Trie k a -> Trie k a
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 = k -> Trie k a -> Trie k a
forall k a.
(GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) =>
k -> Trie k a -> Trie k a
genericDelete

  default trieMap ::
    ( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k) =>
    (a -> b) -> Trie k a -> Trie k b
  trieMap = (a -> b) -> Trie k a -> Trie k b
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 = (a -> f b) -> Trie k a -> f (Trie k b)
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 = (k -> a -> Maybe b) -> Trie k a -> Trie k b
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 = (k -> a -> r -> r) -> r -> Trie k a -> r
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 = (k -> a -> f b) -> Trie k a -> f (Trie k b)
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 = (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
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 = (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
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)

class TrieKey k => ShowTrieKey k where
  -- | Show the representation 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 = Int -> Trie k a -> ShowS
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 :: Int -> Trie Int a -> Maybe a
trieLookup Int
k (MkTrie TrieRep Int a
x)       = Int -> IntMap a -> Maybe a
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
k IntMap a
TrieRep Int a
x
  trieInsert :: Int -> a -> Trie Int a -> Trie Int a
trieInsert Int
k a
v (MkTrie TrieRep Int a
t)     = TrieRep Int a -> Trie Int a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert Int
k a
v IntMap a
TrieRep Int a
t)
  trieDelete :: Int -> Trie Int a -> Trie Int a
trieDelete Int
k (MkTrie TrieRep Int a
t)       = TrieRep Int a -> Trie Int a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> IntMap a -> IntMap a
forall a. Int -> IntMap a -> IntMap a
IntMap.delete Int
k IntMap a
TrieRep Int a
t)
  trieEmpty :: Trie Int a
trieEmpty                     = TrieRep Int a -> Trie Int a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep Int a
forall a. IntMap a
IntMap.empty
  trieSingleton :: Int -> a -> Trie Int a
trieSingleton Int
k a
v             = TrieRep Int a -> Trie Int a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
  trieNull :: Trie Int a -> Bool
trieNull (MkTrie TrieRep Int a
x)           = IntMap a -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap a
TrieRep Int a
x
  trieMap :: (a -> b) -> Trie Int a -> Trie Int b
trieMap a -> b
f (MkTrie TrieRep Int a
x)          = TrieRep Int b -> Trie Int b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f IntMap a
TrieRep Int a
x)
  trieTraverse :: (a -> f b) -> Trie Int a -> f (Trie Int b)
trieTraverse a -> f b
f (MkTrie TrieRep Int a
x)     = (IntMap b -> Trie Int b) -> f (IntMap b) -> f (Trie Int b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Int b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f IntMap a
TrieRep Int a
x)
  trieMapMaybeWithKey :: (Int -> a -> Maybe b) -> Trie Int a -> Trie Int b
trieMapMaybeWithKey Int -> a -> Maybe b
f (MkTrie TrieRep Int a
x)  = TrieRep Int b -> Trie Int b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> Maybe b) -> IntMap a -> IntMap b
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey Int -> a -> Maybe b
f IntMap a
TrieRep Int a
x)
  trieTraverseMaybeWithKey :: (Int -> a -> f (Maybe b)) -> Trie Int a -> f (Trie Int b)
trieTraverseMaybeWithKey Int -> a -> f (Maybe b)
f (MkTrie TrieRep Int a
x)  = IntMap b -> Trie Int b
forall k a. TrieRep k a -> Trie k a
MkTrie (IntMap b -> Trie Int b)
-> (IntMap (Maybe b) -> IntMap b) -> IntMap (Maybe b) -> Trie Int b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe b -> Maybe b) -> IntMap (Maybe b) -> IntMap b
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybe Maybe b -> Maybe b
forall a. a -> a
id (IntMap (Maybe b) -> Trie Int b)
-> f (IntMap (Maybe b)) -> f (Trie Int b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap (Maybe b))
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey Int -> a -> f (Maybe b)
f IntMap a
TrieRep Int a
x
  trieFoldWithKey :: (Int -> a -> r -> r) -> r -> Trie Int a -> r
trieFoldWithKey Int -> a -> r -> r
f r
z (MkTrie TrieRep Int a
x)    = (Int -> a -> r -> r) -> r -> IntMap a -> r
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey Int -> a -> r -> r
f r
z IntMap a
TrieRep Int a
x
  trieTraverseWithKey :: (Int -> a -> f b) -> Trie Int a -> f (Trie Int b)
trieTraverseWithKey Int -> a -> f b
f (MkTrie TrieRep Int a
x)  = (IntMap b -> Trie Int b) -> f (IntMap b) -> f (Trie Int b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Int b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey Int -> a -> f b
f IntMap a
TrieRep Int a
x)
  trieMergeWithKey :: (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) = TrieRep Int c -> Trie Int c
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
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 ((Trie Int a -> Trie Int c) -> IntMap a -> IntMap c
coerce Trie Int a -> Trie Int c
g) ((Trie Int b -> Trie Int c) -> IntMap b -> IntMap c
coerce Trie Int b -> Trie Int c
h) IntMap a
TrieRep Int a
x IntMap b
TrieRep Int b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# INLINABLE trieSingleton #-}
  {-# INLINABLE trieFoldWithKey #-}
  {-# INLINABLE trieTraverse #-}
  {-# INLINABLE trieTraverseWithKey #-}
  {-# INLINABLE trieNull #-}
  {-# INLINABLE trieMap #-}
  {-# INLINABLE trieMergeWithKey #-}
  {-# INLINABLE trieMapMaybeWithKey #-}
  {-# INLINABLE trieTraverseMaybeWithKey #-}

instance ShowTrieKey Int where
  trieShowsPrec :: Int -> Trie Int a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Int a
x)    = Int -> IntMap a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
p IntMap a
TrieRep Int a
x
  {-# INLINABLE trieShowsPrec #-}

-- | 'Integer' tries are implemented with 'Map'.
instance TrieKey Integer where
  type TrieRep Integer              = Map Integer
  trieLookup :: Integer -> Trie Integer a -> Maybe a
trieLookup Integer
k (MkTrie TrieRep Integer a
t)           = Integer -> Map Integer a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Integer
k Map Integer a
TrieRep Integer a
t
  trieInsert :: Integer -> a -> Trie Integer a -> Trie Integer a
trieInsert Integer
k a
v (MkTrie TrieRep Integer a
t)         = TrieRep Integer a -> Trie Integer a
forall k a. TrieRep k a -> Trie k a
MkTrie (Integer -> a -> Map Integer a -> Map Integer a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert Integer
k a
v Map Integer a
TrieRep Integer a
t)
  trieDelete :: Integer -> Trie Integer a -> Trie Integer a
trieDelete Integer
k (MkTrie TrieRep Integer a
t)           = TrieRep Integer a -> Trie Integer a
forall k a. TrieRep k a -> Trie k a
MkTrie (Integer -> Map Integer a -> Map Integer a
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Integer
k Map Integer a
TrieRep Integer a
t)
  trieEmpty :: Trie Integer a
trieEmpty                         = TrieRep Integer a -> Trie Integer a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep Integer a
forall k a. Map k a
Map.empty
  trieSingleton :: Integer -> a -> Trie Integer a
trieSingleton Integer
k a
v                 = TrieRep Integer a -> Trie Integer a
forall k a. TrieRep k a -> Trie k a
MkTrie (Integer -> a -> Map Integer a
forall k a. k -> a -> Map k a
Map.singleton Integer
k a
v)
  trieNull :: Trie Integer a -> Bool
trieNull (MkTrie TrieRep Integer a
x)               = Map Integer a -> Bool
forall k a. Map k a -> Bool
Map.null Map Integer a
TrieRep Integer a
x
  trieMap :: (a -> b) -> Trie Integer a -> Trie Integer b
trieMap a -> b
f (MkTrie TrieRep Integer a
x)              = TrieRep Integer b -> Trie Integer b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> Map Integer a -> Map Integer b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f Map Integer a
TrieRep Integer a
x)
  trieTraverse :: (a -> f b) -> Trie Integer a -> f (Trie Integer b)
trieTraverse a -> f b
f (MkTrie TrieRep Integer a
x)         = (Map Integer b -> Trie Integer b)
-> f (Map Integer b) -> f (Trie Integer b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Integer b -> Trie Integer b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> Map Integer a -> f (Map Integer b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Map Integer a
TrieRep Integer a
x)
  trieMapMaybeWithKey :: (Integer -> a -> Maybe b) -> Trie Integer a -> Trie Integer b
trieMapMaybeWithKey Integer -> a -> Maybe b
f (MkTrie TrieRep Integer a
x)  = TrieRep Integer b -> Trie Integer b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Integer -> a -> Maybe b) -> Map Integer a -> Map Integer b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey Integer -> a -> Maybe b
f Map Integer a
TrieRep Integer a
x)
  trieTraverseMaybeWithKey :: (Integer -> a -> f (Maybe b))
-> Trie Integer a -> f (Trie Integer b)
trieTraverseMaybeWithKey Integer -> a -> f (Maybe b)
f (MkTrie TrieRep Integer a
x)  = Map Integer b -> Trie Integer b
forall k a. TrieRep k a -> Trie k a
MkTrie (Map Integer b -> Trie Integer b)
-> f (Map Integer b) -> f (Trie Integer b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Integer -> a -> f (Maybe b)) -> Map Integer a -> f (Map Integer 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 Map Integer a
TrieRep Integer a
x
  trieFoldWithKey :: (Integer -> a -> r -> r) -> r -> Trie Integer a -> r
trieFoldWithKey Integer -> a -> r -> r
f r
z (MkTrie TrieRep Integer a
x)    = (Integer -> a -> r -> r) -> r -> Map Integer a -> r
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey Integer -> a -> r -> r
f r
z Map Integer a
TrieRep Integer a
x
  trieTraverseWithKey :: (Integer -> a -> f b) -> Trie Integer a -> f (Trie Integer b)
trieTraverseWithKey Integer -> a -> f b
f (MkTrie TrieRep Integer a
x)  = (Map Integer b -> Trie Integer b)
-> f (Map Integer b) -> f (Trie Integer b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Integer b -> Trie Integer b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Integer -> a -> f b) -> Map Integer a -> f (Map Integer b)
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 Map Integer a
TrieRep Integer a
x)
  trieMergeWithKey :: (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) = TrieRep Integer c -> Trie Integer c
forall k a. TrieRep k a -> Trie k a
MkTrie ((Integer -> a -> b -> Maybe c)
-> (Map Integer a -> Map Integer c)
-> (Map Integer b -> Map Integer c)
-> Map Integer a
-> Map Integer b
-> Map Integer c
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 ((Trie Integer a -> Trie Integer c)
-> Map Integer a -> Map Integer c
coerce Trie Integer a -> Trie Integer c
g) ((Trie Integer b -> Trie Integer c)
-> Map Integer b -> Map Integer c
coerce Trie Integer b -> Trie Integer c
h) Map Integer a
TrieRep Integer a
x Map Integer b
TrieRep Integer b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# INLINABLE trieSingleton #-}
  {-# INLINABLE trieFoldWithKey #-}
  {-# INLINABLE trieTraverse #-}
  {-# INLINABLE trieTraverseWithKey #-}
  {-# INLINABLE trieTraverseMaybeWithKey #-}
  {-# INLINABLE trieNull #-}
  {-# INLINABLE trieMap #-}
  {-# INLINABLE trieMergeWithKey #-}
  {-# INLINABLE trieMapMaybeWithKey #-}

instance ShowTrieKey Integer where
  trieShowsPrec :: Int -> Trie Integer a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Integer a
x)        = Int -> Map Integer a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
p Map Integer a
TrieRep Integer a
x
  {-# INLINABLE trieShowsPrec #-}

-- | 'Natural' tries are implemented with 'Map'.
instance TrieKey Natural where
  type TrieRep Natural              = Map Natural
  trieLookup :: Natural -> Trie Natural a -> Maybe a
trieLookup Natural
k (MkTrie TrieRep Natural a
t)           = Natural -> Map Natural a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Natural
k Map Natural a
TrieRep Natural a
t
  trieInsert :: Natural -> a -> Trie Natural a -> Trie Natural a
trieInsert Natural
k a
v (MkTrie TrieRep Natural a
t)         = TrieRep Natural a -> Trie Natural a
forall k a. TrieRep k a -> Trie k a
MkTrie (Natural -> a -> Map Natural a -> Map Natural a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert Natural
k a
v Map Natural a
TrieRep Natural a
t)
  trieDelete :: Natural -> Trie Natural a -> Trie Natural a
trieDelete Natural
k (MkTrie TrieRep Natural a
t)           = TrieRep Natural a -> Trie Natural a
forall k a. TrieRep k a -> Trie k a
MkTrie (Natural -> Map Natural a -> Map Natural a
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Natural
k Map Natural a
TrieRep Natural a
t)
  trieEmpty :: Trie Natural a
trieEmpty                         = TrieRep Natural a -> Trie Natural a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep Natural a
forall k a. Map k a
Map.empty
  trieSingleton :: Natural -> a -> Trie Natural a
trieSingleton Natural
k a
v                 = TrieRep Natural a -> Trie Natural a
forall k a. TrieRep k a -> Trie k a
MkTrie (Natural -> a -> Map Natural a
forall k a. k -> a -> Map k a
Map.singleton Natural
k a
v)
  trieNull :: Trie Natural a -> Bool
trieNull (MkTrie TrieRep Natural a
x)               = Map Natural a -> Bool
forall k a. Map k a -> Bool
Map.null Map Natural a
TrieRep Natural a
x
  trieMap :: (a -> b) -> Trie Natural a -> Trie Natural b
trieMap a -> b
f (MkTrie TrieRep Natural a
x)              = TrieRep Natural b -> Trie Natural b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> Map Natural a -> Map Natural b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f Map Natural a
TrieRep Natural a
x)
  trieTraverse :: (a -> f b) -> Trie Natural a -> f (Trie Natural b)
trieTraverse a -> f b
f (MkTrie TrieRep Natural a
x)         = (Map Natural b -> Trie Natural b)
-> f (Map Natural b) -> f (Trie Natural b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Natural b -> Trie Natural b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> Map Natural a -> f (Map Natural b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Map Natural a
TrieRep Natural a
x)
  trieMapMaybeWithKey :: (Natural -> a -> Maybe b) -> Trie Natural a -> Trie Natural b
trieMapMaybeWithKey Natural -> a -> Maybe b
f (MkTrie TrieRep Natural a
x)  = TrieRep Natural b -> Trie Natural b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Natural -> a -> Maybe b) -> Map Natural a -> Map Natural b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey Natural -> a -> Maybe b
f Map Natural a
TrieRep Natural a
x)
  trieTraverseMaybeWithKey :: (Natural -> a -> f (Maybe b))
-> Trie Natural a -> f (Trie Natural b)
trieTraverseMaybeWithKey Natural -> a -> f (Maybe b)
f (MkTrie TrieRep Natural a
x)  = Map Natural b -> Trie Natural b
forall k a. TrieRep k a -> Trie k a
MkTrie (Map Natural b -> Trie Natural b)
-> f (Map Natural b) -> f (Trie Natural b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Natural -> a -> f (Maybe b)) -> Map Natural a -> f (Map Natural 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 Map Natural a
TrieRep Natural a
x
  trieFoldWithKey :: (Natural -> a -> r -> r) -> r -> Trie Natural a -> r
trieFoldWithKey Natural -> a -> r -> r
f r
z (MkTrie TrieRep Natural a
x)    = (Natural -> a -> r -> r) -> r -> Map Natural a -> r
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey Natural -> a -> r -> r
f r
z Map Natural a
TrieRep Natural a
x
  trieTraverseWithKey :: (Natural -> a -> f b) -> Trie Natural a -> f (Trie Natural b)
trieTraverseWithKey Natural -> a -> f b
f (MkTrie TrieRep Natural a
x)  = (Map Natural b -> Trie Natural b)
-> f (Map Natural b) -> f (Trie Natural b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Natural b -> Trie Natural b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Natural -> a -> f b) -> Map Natural a -> f (Map Natural b)
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 Map Natural a
TrieRep Natural a
x)
  trieMergeWithKey :: (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) = TrieRep Natural c -> Trie Natural c
forall k a. TrieRep k a -> Trie k a
MkTrie ((Natural -> a -> b -> Maybe c)
-> (Map Natural a -> Map Natural c)
-> (Map Natural b -> Map Natural c)
-> Map Natural a
-> Map Natural b
-> Map Natural c
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 ((Trie Natural a -> Trie Natural c)
-> Map Natural a -> Map Natural c
coerce Trie Natural a -> Trie Natural c
g) ((Trie Natural b -> Trie Natural c)
-> Map Natural b -> Map Natural c
coerce Trie Natural b -> Trie Natural c
h) Map Natural a
TrieRep Natural a
x Map Natural b
TrieRep Natural b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# INLINABLE trieSingleton #-}
  {-# INLINABLE trieFoldWithKey #-}
  {-# INLINABLE trieTraverse #-}
  {-# INLINABLE trieTraverseWithKey #-}
  {-# INLINABLE trieTraverseMaybeWithKey #-}
  {-# INLINABLE trieNull #-}
  {-# INLINABLE trieMap #-}
  {-# INLINABLE trieMergeWithKey #-}
  {-# INLINABLE trieMapMaybeWithKey #-}

instance ShowTrieKey Natural where
  trieShowsPrec :: Int -> Trie Natural a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Natural a
x)        = Int -> Map Natural a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
p Map Natural a
TrieRep Natural a
x
  {-# INLINABLE trieShowsPrec #-}

-- | 'Word' tries are implemented with 'IntMap'.
instance TrieKey Word where
  type TrieRep Word                 = IntMap
  trieLookup :: Word -> Trie Word a -> Maybe a
trieLookup Word
k (MkTrie TrieRep Word a
t)           = Int -> IntMap a -> Maybe a
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) IntMap a
TrieRep Word a
t
  trieDelete :: Word -> Trie Word a -> Trie Word a
trieDelete Word
k (MkTrie TrieRep Word a
t)           = TrieRep Word a -> Trie Word a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> IntMap a -> IntMap a
forall a. Int -> IntMap a -> IntMap a
IntMap.delete (Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) IntMap a
TrieRep Word a
t)
  trieInsert :: Word -> a -> Trie Word a -> Trie Word a
trieInsert Word
k a
v (MkTrie TrieRep Word a
t)         = TrieRep Word a -> Trie Word a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert (Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) a
v IntMap a
TrieRep Word a
t)
  trieEmpty :: Trie Word a
trieEmpty                         = TrieRep Word a -> Trie Word a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep Word a
forall a. IntMap a
IntMap.empty
  trieSingleton :: Word -> a -> Trie Word a
trieSingleton Word
k a
v                 = TrieRep Word a -> Trie Word a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton (Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
k) a
v)
  trieNull :: Trie Word a -> Bool
trieNull (MkTrie TrieRep Word a
x)               = IntMap a -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap a
TrieRep Word a
x
  trieMap :: (a -> b) -> Trie Word a -> Trie Word b
trieMap a -> b
f (MkTrie TrieRep Word a
x)              = TrieRep Word b -> Trie Word b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f IntMap a
TrieRep Word a
x)
  trieTraverse :: (a -> f b) -> Trie Word a -> f (Trie Word b)
trieTraverse a -> f b
f (MkTrie TrieRep Word a
x)         = (IntMap b -> Trie Word b) -> f (IntMap b) -> f (Trie Word b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Word b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f IntMap a
TrieRep Word a
x)
  trieMapMaybeWithKey :: (Word -> a -> Maybe b) -> Trie Word a -> Trie Word b
trieMapMaybeWithKey Word -> a -> Maybe b
f (MkTrie TrieRep Word a
x)  = TrieRep Word b -> Trie Word b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> Maybe b) -> IntMap a -> IntMap b
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey (Word -> a -> Maybe b
f (Word -> a -> Maybe b) -> (Int -> Word) -> Int -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral) IntMap a
TrieRep Word a
x)
  trieTraverseMaybeWithKey :: (Word -> a -> f (Maybe b)) -> Trie Word a -> f (Trie Word b)
trieTraverseMaybeWithKey Word -> a -> f (Maybe b)
f (MkTrie TrieRep Word a
x)  = IntMap b -> Trie Word b
forall k a. TrieRep k a -> Trie k a
MkTrie (IntMap b -> Trie Word b)
-> (IntMap (Maybe b) -> IntMap b)
-> IntMap (Maybe b)
-> Trie Word b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe b -> Maybe b) -> IntMap (Maybe b) -> IntMap b
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybe Maybe b -> Maybe b
forall a. a -> a
id (IntMap (Maybe b) -> Trie Word b)
-> f (IntMap (Maybe b)) -> f (Trie Word b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap (Maybe b))
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Word -> a -> f (Maybe b)
f (Word -> a -> f (Maybe b))
-> (Int -> Word) -> Int -> a -> f (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral) IntMap a
TrieRep Word a
x
  trieFoldWithKey :: (Word -> a -> r -> r) -> r -> Trie Word a -> r
trieFoldWithKey Word -> a -> r -> r
f r
z (MkTrie TrieRep Word a
x)    = (Int -> a -> r -> r) -> r -> IntMap a -> r
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey (Word -> a -> r -> r
f (Word -> a -> r -> r) -> (Int -> Word) -> Int -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral) r
z IntMap a
TrieRep Word a
x
  trieTraverseWithKey :: (Word -> a -> f b) -> Trie Word a -> f (Trie Word b)
trieTraverseWithKey Word -> a -> f b
f (MkTrie TrieRep Word a
x)  = (IntMap b -> Trie Word b) -> f (IntMap b) -> f (Trie Word b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Word b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Word -> a -> f b
f (Word -> a -> f b) -> (Int -> Word) -> Int -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral) IntMap a
TrieRep Word a
x)
  trieMergeWithKey :: (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) = TrieRep Word c -> Trie Word c
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
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 (Word -> a -> b -> Maybe c)
-> (Int -> Word) -> Int -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral) ((Trie Word a -> Trie Word c) -> IntMap a -> IntMap c
coerce Trie Word a -> Trie Word c
g) ((Trie Word b -> Trie Word c) -> IntMap b -> IntMap c
coerce Trie Word b -> Trie Word c
h) IntMap a
TrieRep Word a
x IntMap b
TrieRep Word b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# INLINABLE trieSingleton #-}
  {-# INLINABLE trieFoldWithKey #-}
  {-# INLINABLE trieTraverse #-}
  {-# INLINABLE trieTraverseWithKey #-}
  {-# INLINABLE trieTraverseMaybeWithKey #-}
  {-# INLINABLE trieNull #-}
  {-# INLINABLE trieMap #-}
  {-# INLINABLE trieMergeWithKey #-}
  {-# INLINABLE trieMapMaybeWithKey #-}

instance ShowTrieKey Word where
  trieShowsPrec :: Int -> Trie Word a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Word a
x) =
    Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Word, a)] -> ShowS
forall a. Show a => a -> ShowS
shows [(Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k :: Word, a
v) | (Int
k,a
v) <- IntMap a -> [(Int, a)]
forall a. IntMap a -> [(Int, a)]
IntMap.toList IntMap a
TrieRep Word a
x])
  {-# INLINABLE trieShowsPrec #-}

-- | 'Char' tries are implemented with 'IntMap'.
instance TrieKey Char where
  type TrieRep Char                 = IntMap
  trieLookup :: Char -> Trie Char a -> Maybe a
trieLookup Char
k (MkTrie TrieRep Char a
t)           = Int -> IntMap a -> Maybe a
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (Char -> Int
ord Char
k) IntMap a
TrieRep Char a
t
  trieDelete :: Char -> Trie Char a -> Trie Char a
trieDelete Char
k (MkTrie TrieRep Char a
t)           = TrieRep Char a -> Trie Char a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> IntMap a -> IntMap a
forall a. Int -> IntMap a -> IntMap a
IntMap.delete (Char -> Int
ord Char
k) IntMap a
TrieRep Char a
t)
  trieInsert :: Char -> a -> Trie Char a -> Trie Char a
trieInsert Char
k a
v (MkTrie TrieRep Char a
t)         = TrieRep Char a -> Trie Char a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert (Char -> Int
ord Char
k) a
v IntMap a
TrieRep Char a
t)
  trieEmpty :: Trie Char a
trieEmpty                         = TrieRep Char a -> Trie Char a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep Char a
forall a. IntMap a
IntMap.empty
  trieSingleton :: Char -> a -> Trie Char a
trieSingleton Char
k a
v                 = TrieRep Char a -> Trie Char a
forall k a. TrieRep k a -> Trie k a
MkTrie (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton (Char -> Int
ord Char
k) a
v)
  trieNull :: Trie Char a -> Bool
trieNull (MkTrie TrieRep Char a
x)               = IntMap a -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap a
TrieRep Char a
x
  trieMap :: (a -> b) -> Trie Char a -> Trie Char b
trieMap a -> b
f (MkTrie TrieRep Char a
x)              = TrieRep Char b -> Trie Char b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f IntMap a
TrieRep Char a
x)
  trieTraverse :: (a -> f b) -> Trie Char a -> f (Trie Char b)
trieTraverse a -> f b
f (MkTrie TrieRep Char a
x)         = (IntMap b -> Trie Char b) -> f (IntMap b) -> f (Trie Char b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Char b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f IntMap a
TrieRep Char a
x)
  trieMapMaybeWithKey :: (Char -> a -> Maybe b) -> Trie Char a -> Trie Char b
trieMapMaybeWithKey Char -> a -> Maybe b
f (MkTrie TrieRep Char a
x)  = TrieRep Char b -> Trie Char b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> Maybe b) -> IntMap a -> IntMap b
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybeWithKey (Char -> a -> Maybe b
f (Char -> a -> Maybe b) -> (Int -> Char) -> Int -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) IntMap a
TrieRep Char a
x)
  trieTraverseMaybeWithKey :: (Char -> a -> f (Maybe b)) -> Trie Char a -> f (Trie Char b)
trieTraverseMaybeWithKey Char -> a -> f (Maybe b)
f (MkTrie TrieRep Char a
x)  = IntMap b -> Trie Char b
forall k a. TrieRep k a -> Trie k a
MkTrie (IntMap b -> Trie Char b)
-> (IntMap (Maybe b) -> IntMap b)
-> IntMap (Maybe b)
-> Trie Char b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe b -> Maybe b) -> IntMap (Maybe b) -> IntMap b
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IntMap.mapMaybe Maybe b -> Maybe b
forall a. a -> a
id (IntMap (Maybe b) -> Trie Char b)
-> f (IntMap (Maybe b)) -> f (Trie Char b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> a -> f (Maybe b)) -> IntMap a -> f (IntMap (Maybe b))
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Char -> a -> f (Maybe b)
f (Char -> a -> f (Maybe b))
-> (Int -> Char) -> Int -> a -> f (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) IntMap a
TrieRep Char a
x
  trieFoldWithKey :: (Char -> a -> r -> r) -> r -> Trie Char a -> r
trieFoldWithKey Char -> a -> r -> r
f r
z (MkTrie TrieRep Char a
x)    = (Int -> a -> r -> r) -> r -> IntMap a -> r
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey (Char -> a -> r -> r
f (Char -> a -> r -> r) -> (Int -> Char) -> Int -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) r
z IntMap a
TrieRep Char a
x
  trieTraverseWithKey :: (Char -> a -> f b) -> Trie Char a -> f (Trie Char b)
trieTraverseWithKey Char -> a -> f b
f (MkTrie TrieRep Char a
x)  = (IntMap b -> Trie Char b) -> f (IntMap b) -> f (Trie Char b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap b -> Trie Char b
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) a b.
Applicative t =>
(Int -> a -> t b) -> IntMap a -> t (IntMap b)
IntMap.traverseWithKey (Char -> a -> f b
f (Char -> a -> f b) -> (Int -> Char) -> Int -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) IntMap a
TrieRep Char a
x)
  trieMergeWithKey :: (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) = TrieRep Char c -> Trie Char c
forall k a. TrieRep k a -> Trie k a
MkTrie ((Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
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 (Char -> a -> b -> Maybe c)
-> (Int -> Char) -> Int -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Char
chr) ((Trie Char a -> Trie Char c) -> IntMap a -> IntMap c
coerce Trie Char a -> Trie Char c
g) ((Trie Char b -> Trie Char c) -> IntMap b -> IntMap c
coerce Trie Char b -> Trie Char c
h) IntMap a
TrieRep Char a
x IntMap b
TrieRep Char b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# INLINABLE trieSingleton #-}
  {-# INLINABLE trieFoldWithKey #-}
  {-# INLINABLE trieTraverse #-}
  {-# INLINABLE trieTraverseWithKey #-}
  {-# INLINABLE trieTraverseMaybeWithKey #-}
  {-# INLINABLE trieNull #-}
  {-# INLINABLE trieMap #-}
  {-# INLINABLE trieMergeWithKey #-}
  {-# INLINABLE trieMapMaybeWithKey #-}

instance ShowTrieKey Char where
  trieShowsPrec :: Int -> Trie Char a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep Char a
x)        = Int -> IntMap a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
p IntMap a
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 { OrdKey k -> k
getOrdKey :: k }
  deriving (ReadPrec [OrdKey k]
ReadPrec (OrdKey k)
Int -> ReadS (OrdKey k)
ReadS [OrdKey k]
(Int -> ReadS (OrdKey k))
-> ReadS [OrdKey k]
-> ReadPrec (OrdKey k)
-> ReadPrec [OrdKey k]
-> Read (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
[OrdKey k] -> ShowS
OrdKey k -> String
(Int -> OrdKey k -> ShowS)
-> (OrdKey k -> String) -> ([OrdKey k] -> ShowS) -> Show (OrdKey k)
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
(OrdKey k -> OrdKey k -> Bool)
-> (OrdKey k -> OrdKey k -> Bool) -> Eq (OrdKey k)
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, Eq (OrdKey k)
Eq (OrdKey k)
-> (OrdKey k -> OrdKey k -> Ordering)
-> (OrdKey k -> OrdKey k -> Bool)
-> (OrdKey k -> OrdKey k -> Bool)
-> (OrdKey k -> OrdKey k -> Bool)
-> (OrdKey k -> OrdKey k -> Bool)
-> (OrdKey k -> OrdKey k -> OrdKey k)
-> (OrdKey k -> OrdKey k -> OrdKey k)
-> Ord (OrdKey k)
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
$cp1Ord :: forall k. Ord k => Eq (OrdKey k)
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 :: OrdKey k -> Trie (OrdKey k) a -> Maybe a
trieLookup (OrdKey k
k) (MkTrie TrieRep (OrdKey k) a
x)      = k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k a
TrieRep (OrdKey k) a
x
  trieInsert :: OrdKey k -> a -> Trie (OrdKey k) a -> Trie (OrdKey k) a
trieInsert (OrdKey k
k) a
v (MkTrie TrieRep (OrdKey k) a
x)    = TrieRep (OrdKey k) a -> Trie (OrdKey k) a
forall k a. TrieRep k a -> Trie k a
MkTrie (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k a
v Map k a
TrieRep (OrdKey k) a
x)
  trieDelete :: OrdKey k -> Trie (OrdKey k) a -> Trie (OrdKey k) a
trieDelete (OrdKey k
k) (MkTrie TrieRep (OrdKey k) a
x)      = TrieRep (OrdKey k) a -> Trie (OrdKey k) a
forall k a. TrieRep k a -> Trie k a
MkTrie (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k a
TrieRep (OrdKey k) a
x)
  trieEmpty :: Trie (OrdKey k) a
trieEmpty                             = TrieRep (OrdKey k) a -> Trie (OrdKey k) a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep (OrdKey k) a
forall k a. Map k a
Map.empty
  trieSingleton :: OrdKey k -> a -> Trie (OrdKey k) a
trieSingleton (OrdKey k
k) a
v            = TrieRep (OrdKey k) a -> Trie (OrdKey k) a
forall k a. TrieRep k a -> Trie k a
MkTrie (k -> a -> Map k a
forall k a. k -> a -> Map k a
Map.singleton k
k a
v)
  trieNull :: Trie (OrdKey k) a -> Bool
trieNull (MkTrie TrieRep (OrdKey k) a
x)                   = Map k a -> Bool
forall k a. Map k a -> Bool
Map.null Map k a
TrieRep (OrdKey k) a
x
  trieMap :: (a -> b) -> Trie (OrdKey k) a -> Trie (OrdKey k) b
trieMap a -> b
f (MkTrie TrieRep (OrdKey k) a
x)                  = TrieRep (OrdKey k) b -> Trie (OrdKey k) b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> b) -> Map k a -> Map k b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f Map k a
TrieRep (OrdKey k) a
x)
  trieTraverse :: (a -> f b) -> Trie (OrdKey k) a -> f (Trie (OrdKey k) b)
trieTraverse a -> f b
f (MkTrie TrieRep (OrdKey k) a
x)             = (Map k b -> Trie (OrdKey k) b)
-> f (Map k b) -> f (Trie (OrdKey k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map k b -> Trie (OrdKey k) b
forall k a. TrieRep k a -> Trie k a
MkTrie ((a -> f b) -> Map k a -> f (Map k b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Map k a
TrieRep (OrdKey k) a
x)
  trieMapMaybeWithKey :: (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)      = TrieRep (OrdKey k) b -> Trie (OrdKey k) b
forall k a. TrieRep k a -> Trie k a
MkTrie ((k -> a -> Maybe b) -> Map k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey (OrdKey k -> a -> Maybe b
f (OrdKey k -> a -> Maybe b) -> (k -> OrdKey k) -> k -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OrdKey k
forall k. k -> OrdKey k
OrdKey) Map k a
TrieRep (OrdKey k) a
x)
  trieTraverseMaybeWithKey :: (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) = Map k b -> Trie (OrdKey k) b
forall k a. TrieRep k a -> Trie k a
MkTrie (Map k b -> Trie (OrdKey k) b)
-> f (Map k b) -> f (Trie (OrdKey k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> a -> f (Maybe b)) -> Map k a -> f (Map k 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 (OrdKey k -> a -> f (Maybe b))
-> (k -> OrdKey k) -> k -> a -> f (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OrdKey k
forall k. k -> OrdKey k
OrdKey) Map k a
TrieRep (OrdKey k) a
x
  trieFoldWithKey :: (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)        = (k -> a -> r -> r) -> r -> Map k a -> r
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey (OrdKey k -> a -> r -> r
f (OrdKey k -> a -> r -> r) -> (k -> OrdKey k) -> k -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OrdKey k
forall k. k -> OrdKey k
OrdKey) r
z Map k a
TrieRep (OrdKey k) a
x
  trieTraverseWithKey :: (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)      = (Map k b -> Trie (OrdKey k) b)
-> f (Map k b) -> f (Trie (OrdKey k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map k b -> Trie (OrdKey k) b
forall k a. TrieRep k a -> Trie k a
MkTrie ((k -> a -> f b) -> Map k a -> f (Map k b)
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 (OrdKey k -> a -> f b) -> (k -> OrdKey k) -> k -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OrdKey k
forall k. k -> OrdKey k
OrdKey) Map k a
TrieRep (OrdKey k) a
x)
  trieMergeWithKey :: (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) = TrieRep (OrdKey k) c -> Trie (OrdKey k) c
forall k a. TrieRep k a -> Trie k a
MkTrie ((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
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 (OrdKey k -> a -> b -> Maybe c)
-> (k -> OrdKey k) -> k -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OrdKey k
forall k. k -> OrdKey k
OrdKey) ((Trie (OrdKey k) a -> Trie (OrdKey k) c) -> Map k a -> Map k c
coerce Trie (OrdKey k) a -> Trie (OrdKey k) c
g) ((Trie (OrdKey k) b -> Trie (OrdKey k) c) -> Map k b -> Map k c
coerce Trie (OrdKey k) b -> Trie (OrdKey k) c
h) Map k a
TrieRep (OrdKey k) a
x Map k b
TrieRep (OrdKey k) b
y)
  {-# INLINABLE trieEmpty #-}
  {-# INLINABLE trieInsert #-}
  {-# INLINABLE trieLookup #-}
  {-# INLINABLE trieDelete #-}
  {-# 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 :: Int -> Trie (OrdKey k) a -> ShowS
trieShowsPrec Int
p (MkTrie TrieRep (OrdKey k) a
x)            = Int -> Map k a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
p Map k a
TrieRep (OrdKey k) a
x
  {-# INLINABLE trieShowsPrec #-}

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

instance                                      TrieKey Void
instance                                      TrieKey ()
instance                                      TrieKey Bool
instance                                      TrieKey Ordering
instance TrieKey k                         => TrieKey (Maybe k)
instance (TrieKey a, TrieKey b)            => TrieKey (Either a b)
instance (TrieKey a, TrieKey b)            => TrieKey (a,b)
instance (TrieKey a, TrieKey b, TrieKey c) => TrieKey (a,b,c)
instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d) => TrieKey (a,b,c,d)
instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d, TrieKey e) => TrieKey (a,b,c,d,e)
instance TrieKey k                         => TrieKey [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 :: k -> Trie k a -> Maybe a
genericLookup k
k Trie k a
t = Rep k Any -> GTrie (Rep k) a -> Maybe a
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup (k -> Rep k Any
forall a x. Generic a => a -> Rep a x
from k
k) (GTrie (Rep k) a -> Maybe a) -> Maybe (GTrie (Rep k) a) -> Maybe a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Trie k a -> Maybe (GTrie (Rep k) a)
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 :: Trie k a -> Bool
genericTrieNull = Maybe (GTrie (Rep k) a) -> Bool
forall a. Maybe a -> Bool
isNothing (Maybe (GTrie (Rep k) a) -> Bool)
-> (Trie k a -> Maybe (GTrie (Rep k) a)) -> Trie k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Trie k a -> Maybe (GTrie (Rep k) a)
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 :: k -> a -> Trie k a
genericSingleton k
k a
v = Maybe (GTrie (Rep k) a) -> Trie k a
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (Maybe (GTrie (Rep k) a) -> Trie k a)
-> Maybe (GTrie (Rep k) a) -> Trie k a
forall a b. (a -> b) -> a -> b
$ GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a. a -> Maybe a
Just (GTrie (Rep k) a -> Maybe (GTrie (Rep k) a))
-> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a b. (a -> b) -> a -> b
$! Rep k Any -> a -> GTrie (Rep k) a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton (k -> Rep k Any
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 :: Trie k a
genericEmpty = TrieRep k a -> Trie k a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k a
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 :: k -> a -> Trie k a -> Trie k a
genericInsert k
k a
v Trie k a
m = Maybe (GTrie (Rep k) a) -> Trie k a
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (Maybe (GTrie (Rep k) a) -> Trie k a)
-> Maybe (GTrie (Rep k) a) -> Trie k a
forall a b. (a -> b) -> a -> b
$
  case Trie k a -> Maybe (GTrie (Rep k) a)
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 -> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a. a -> Maybe a
Just (GTrie (Rep k) a -> Maybe (GTrie (Rep k) a))
-> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a b. (a -> b) -> a -> b
$! Rep k Any -> a -> GTrie (Rep k) a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton (k -> Rep k Any
forall a x. Generic a => a -> Rep a x
from k
k) a
v
    Just GTrie (Rep k) a
t  -> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a. a -> Maybe a
Just (GTrie (Rep k) a -> Maybe (GTrie (Rep k) a))
-> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall a b. (a -> b) -> a -> b
$! Rep k Any -> a -> GTrie (Rep k) a -> GTrie (Rep k) a
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert    (k -> Rep k Any
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 :: k -> Trie k a -> Trie k a
genericDelete k
k Trie k a
m = Maybe (GTrie (Rep k) a) -> Trie k a
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap (Rep k Any -> GTrie (Rep k) a -> Maybe (GTrie (Rep k) a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete (k -> Rep k Any
forall a x. Generic a => a -> Rep a x
from k
k) (GTrie (Rep k) a -> Maybe (GTrie (Rep k) a))
-> Maybe (GTrie (Rep k) a) -> Maybe (GTrie (Rep k) a)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Trie k a -> Maybe (GTrie (Rep k) a)
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 'trieMap'. This is the default implementation.
genericTrieMap ::
    ( GTrieKey (Rep k)
    , TrieRep k ~ TrieRepDefault k
    ) =>
    (a -> b) -> Trie k a -> Trie k b
genericTrieMap :: (a -> b) -> Trie k a -> Trie k b
genericTrieMap a -> b
f Trie k a
x = Maybe (GTrie (Rep k) b) -> Trie k b
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap ((GTrie (Rep k) a -> GTrie (Rep k) b)
-> Maybe (GTrie (Rep k) a) -> Maybe (GTrie (Rep k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> GTrie (Rep k) a -> GTrie (Rep k) b
forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f) (Maybe (GTrie (Rep k) a) -> Maybe (GTrie (Rep k) b))
-> Maybe (GTrie (Rep k) a) -> Maybe (GTrie (Rep k) b)
forall a b. (a -> b) -> a -> b
$! Trie k a -> Maybe (GTrie (Rep k) a)
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 :: (a -> f b) -> Trie k a -> f (Trie k b)
genericTrieTraverse a -> f b
f Trie k a
x =
  (Maybe (GTrie (Rep k) b) -> Trie k b)
-> f (Maybe (GTrie (Rep k) b)) -> f (Trie k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe (GTrie (Rep k) b) -> Trie k b
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap ((GTrie (Rep k) a -> f (GTrie (Rep k) b))
-> Maybe (GTrie (Rep k) a) -> f (Maybe (GTrie (Rep k) b))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f b) -> GTrie (Rep k) a -> f (GTrie (Rep k) b)
forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse a -> f b
f) (Trie k a -> Maybe (GTrie (Rep k) a)
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 :: Int -> Trie k a -> ShowS
genericTrieShowsPrec Int
p Trie k a
m =
  case Trie k a -> Maybe (GTrie (Rep k) a)
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  -> Int -> GTrie (Rep k) a -> ShowS
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 :: (k -> a -> Maybe b) -> Trie k a -> Trie k b
genericMapMaybeWithKey k -> a -> Maybe b
f Trie k a
x = Maybe (GTrie (Rep k) b) -> Trie k b
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap ((Rep k Any -> a -> Maybe b)
-> GTrie (Rep k) a -> Maybe (GTrie (Rep k) b)
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 (k -> a -> Maybe b)
-> (Rep k Any -> k) -> Rep k Any -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rep k Any -> k
forall a x. Generic a => Rep a x -> a
to) (GTrie (Rep k) a -> Maybe (GTrie (Rep k) b))
-> Maybe (GTrie (Rep k) a) -> Maybe (GTrie (Rep k) b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Trie k a -> Maybe (GTrie (Rep k) a)
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 :: (k -> a -> r -> r) -> r -> Trie k a -> r
genericFoldWithKey k -> a -> r -> r
f r
z Trie k a
m =
  case Trie k a -> Maybe (GTrie (Rep k) a)
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  -> (Rep k Any -> a -> r -> r) -> r -> GTrie (Rep k) a -> r
forall (f :: * -> *) p a r.
GTrieKey f =>
(f p -> a -> r -> r) -> r -> GTrie f a -> r
gfoldWithKey (k -> a -> r -> r
f (k -> a -> r -> r) -> (Rep k Any -> k) -> Rep k Any -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rep k Any -> k
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 :: (k -> a -> f b) -> Trie k a -> f (Trie k b)
genericTraverseWithKey k -> a -> f b
f Trie k a
m = (Maybe (GTrie (Rep k) b) -> Trie k b)
-> f (Maybe (GTrie (Rep k) b)) -> f (Trie k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe (GTrie (Rep k) b) -> Trie k b
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap ((GTrie (Rep k) a -> f (GTrie (Rep k) b))
-> Maybe (GTrie (Rep k) a) -> f (Maybe (GTrie (Rep k) b))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((Rep k Any -> a -> f b) -> GTrie (Rep k) a -> f (GTrie (Rep k) b)
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 (k -> a -> f b) -> (Rep k Any -> k) -> Rep k Any -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rep k Any -> k
forall a x. Generic a => Rep a x -> a
to)) (Trie k a -> Maybe (GTrie (Rep k) a)
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 :: (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
genericTraverseMaybeWithKey k -> a -> f (Maybe b)
f Trie k a
m = (Maybe (Maybe (GTrie (Rep k) b)) -> Trie k b)
-> f (Maybe (Maybe (GTrie (Rep k) b))) -> f (Trie k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Trie k b
-> (Maybe (GTrie (Rep k) b) -> Trie k b)
-> Maybe (Maybe (GTrie (Rep k) b))
-> Trie k b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (TrieRep k b -> Trie k b
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k b
forall k a. TrieRepDefault k a
EmptyTrie) Maybe (GTrie (Rep k) b) -> Trie k b
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap) ((GTrie (Rep k) a -> f (Maybe (GTrie (Rep k) b)))
-> Maybe (GTrie (Rep k) a) -> f (Maybe (Maybe (GTrie (Rep k) b)))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((Rep k Any -> a -> f (Maybe b))
-> GTrie (Rep k) a -> f (Maybe (GTrie (Rep k) 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 (k -> a -> f (Maybe b)
f (k -> a -> f (Maybe b))
-> (Rep k Any -> k) -> Rep k Any -> a -> f (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rep k Any -> k
forall a x. Generic a => Rep a x -> a
to)) (Trie k a -> Maybe (GTrie (Rep k) a)
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 :: (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 (TrieRepDefault k a
TrieRep k a
x,TrieRepDefault k b
TrieRep k b
y) of
    (TrieRepDefault k a
EmptyTrie, TrieRepDefault k b
EmptyTrie) -> TrieRep k c -> Trie k c
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k c
forall k a. TrieRepDefault k a
EmptyTrie
    (NonEmptyTrie{} , TrieRepDefault k b
EmptyTrie) -> Trie k a -> Trie k c
g (TrieRep k a -> Trie k a
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 (TrieRep k b -> Trie k b
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') -> Maybe (GTrie (Rep k) c) -> Trie k c
forall k k1 a.
(TrieRep k ~ TrieRepDefault k1) =>
Maybe (GTrie (Rep k1) a) -> Trie k a
wrap ((Rep k Any -> a -> b -> Maybe c)
-> (GTrie (Rep k) a -> Maybe (GTrie (Rep k) c))
-> (GTrie (Rep k) b -> Maybe (GTrie (Rep k) c))
-> GTrie (Rep k) a
-> GTrie (Rep k) b
-> Maybe (GTrie (Rep k) c)
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 (k -> a -> b -> Maybe c)
-> (Rep k Any -> k) -> Rep k Any -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rep k Any -> k
forall a x. Generic a => Rep a x -> a
to) ((Trie k a -> Trie k c)
-> GTrie (Rep k) a -> Maybe (GTrie (Rep k) c)
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) ((Trie k b -> Trie k c)
-> GTrie (Rep k) b -> Maybe (GTrie (Rep k) c)
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 = Trie t t1 -> Maybe (GTrie (Rep t2) t1)
forall t t2 t1.
(TrieRep t ~ TrieRepDefault t2) =>
Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap (Trie k a -> Trie t t1
k (TrieRep k a -> Trie k a
forall k a. TrieRep k a -> Trie k a
MkTrie (GTrie (Rep k) a -> TrieRepDefault k a
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 :: Maybe (GTrie (Rep k1) a) -> Trie k a
wrap Maybe (GTrie (Rep k1) a)
Nothing = TrieRep k a -> Trie k a
forall k a. TrieRep k a -> Trie k a
MkTrie TrieRep k a
forall k a. TrieRepDefault k a
EmptyTrie
wrap (Just GTrie (Rep k1) a
t) = TrieRep k a -> Trie k a
forall k a. TrieRep k a -> Trie k a
MkTrie (GTrie (Rep k1) a -> TrieRepDefault k1 a
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 :: Trie t t1 -> Maybe (GTrie (Rep t2) t1)
unwrap (MkTrie TrieRep t t1
EmptyTrie) = Maybe (GTrie (Rep t2) t1)
forall a. Maybe a
Nothing
unwrap (MkTrie (NonEmptyTrie t)) = GTrie (Rep t2) t1 -> Maybe (GTrie (Rep t2) t1)
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.
data    family   GTrie (f :: * -> *) a
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 :: (a -> b) -> GTrie f a -> GTrie f b
fmap = (a -> b) -> GTrie f a -> GTrie f b
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)
  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 :: M1 i c f p -> GTrie (M1 i c f) a -> Maybe a
gtrieLookup (M1 f p
k) (MTrie x)  = f p -> GTrie f a -> Maybe a
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
k GTrie f a
x
  gtrieInsert :: 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 t)= GTrie f a -> GTrie (M1 i c f) a
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (f p -> a -> GTrie f a -> GTrie f a
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 :: M1 i c f p -> a -> GTrie (M1 i c f) a
gtrieSingleton (M1 f p
k) a
v       = GTrie f a -> GTrie (M1 i c f) a
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (f p -> a -> GTrie f a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
k a
v)
  gtrieDelete :: M1 i c f p -> GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) a)
gtrieDelete (M1 f p
k) (MTrie x)  = (GTrie f a -> GTrie (M1 i c f) a)
-> Maybe (GTrie f a) -> Maybe (GTrie (M1 i c f) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f a -> GTrie (M1 i c f) a
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie (f p -> GTrie f a -> Maybe (GTrie f a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete f p
k GTrie f a
x)
  gtrieMap :: (a -> b) -> GTrie (M1 i c f) a -> GTrie (M1 i c f) b
gtrieMap a -> b
f (MTrie x)          = GTrie f b -> GTrie (M1 i c f) b
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie ((a -> b) -> GTrie f a -> GTrie f b
forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie f a
x)
  gtrieTraverse :: (a -> m b) -> GTrie (M1 i c f) a -> m (GTrie (M1 i c f) b)
gtrieTraverse a -> m b
f (MTrie x)     = (GTrie f b -> GTrie (M1 i c f) b)
-> m (GTrie f b) -> m (GTrie (M1 i c f) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (M1 i c f) b
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie ((a -> m b) -> GTrie f a -> m (GTrie f b)
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 :: (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 x)  = (GTrie f b -> GTrie (M1 i c f) b)
-> Maybe (GTrie f b) -> Maybe (GTrie (M1 i c f) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (M1 i c f) b
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie ((f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
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 (M1 i c f p -> a -> Maybe b)
-> (f p -> M1 i c f p) -> f p -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
  gfoldWithKey :: (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 x)    = (f p -> a -> r -> r) -> r -> GTrie f a -> r
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 (M1 i c f p -> a -> r -> r)
-> (f p -> M1 i c f p) -> f p -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) r
z GTrie f a
x
  gtraverseWithKey :: (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 x)  = (GTrie f b -> GTrie (M1 i c f) b)
-> m (GTrie f b) -> m (GTrie (M1 i c f) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (M1 i c f) b
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie ((f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
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 (M1 i c f p -> a -> m b) -> (f p -> M1 i c f p) -> f p -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
  gtraverseMaybeWithKey :: (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 x)  = (Maybe (GTrie f b) -> Maybe (GTrie (M1 i c f) b))
-> m (Maybe (GTrie f b)) -> m (Maybe (GTrie (M1 i c f) b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe (GTrie f b) -> Maybe (GTrie (M1 i c f) b)
coerce ((f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie 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 (M1 i c f p -> a -> m (Maybe b)
f (M1 i c f p -> a -> m (Maybe b))
-> (f p -> M1 i c f p) -> f p -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) GTrie f a
x)
  gmergeWithKey :: (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 x) (MTrie y) = (GTrie f c -> GTrie (M1 i c f) c)
-> Maybe (GTrie f c) -> Maybe (GTrie (M1 i c f) c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f c -> GTrie (M1 i c f) c
forall i (c :: Meta) (f :: * -> *) a.
GTrie f a -> GTrie (M1 i c f) a
MTrie ((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)
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 (M1 i c f p -> a -> b -> Maybe c)
-> (f p -> M1 i c f p) -> f p -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
M1) ((GTrie (M1 i c f) a -> Maybe (GTrie (M1 i c f) c))
-> GTrie f a -> Maybe (GTrie f c)
coerce 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))
-> GTrie f b -> Maybe (GTrie f c)
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 gtrieMap #-}
  {-# INLINE gmapMaybeWithKey #-}
  {-# INLINE gtrieTraverse #-}
  {-# INLINE gfoldWithKey #-}
  {-# INLINE gtraverseWithKey #-}
  {-# INLINE gtraverseMaybeWithKey #-}

#if MIN_VERSION_base(4,9,0)
data MProxy (c :: Meta) (f :: * -> *) a = MProxy
#else
data MProxy (c :: *)    (f :: * -> *) a = MProxy
#endif

instance GTrieKeyShow f => GTrieKeyShow (M1 D d f) where
  gtrieShowsPrec :: Int -> GTrie (M1 D d f) a -> ShowS
gtrieShowsPrec Int
p (MTrie x)    = Int -> GTrie f a -> ShowS
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 :: Int -> GTrie (M1 C c f) a -> ShowS
gtrieShowsPrec Int
p (MTrie x)    = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
                                (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"Con "
                                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
forall a. Show a => a -> ShowS
shows (MProxy c f () -> String
forall k (c :: k) k1 (t :: k -> (k1 -> *) -> k1 -> *)
       (f :: k1 -> *) (a :: k1).
Constructor c =>
t c f a -> String
conName (MProxy c f ()
forall (c :: Meta) (f :: * -> *) a. MProxy c f a
MProxy :: MProxy c f ()))
                                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" "
                                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> GTrie f a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
instance GTrieKeyShow f => GTrieKeyShow (M1 S s f) where
  gtrieShowsPrec :: Int -> GTrie (M1 S s f) a -> ShowS
gtrieShowsPrec Int
p (MTrie x)    = Int -> GTrie f a -> ShowS
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 :: Trie k a -> Maybe (Trie k a)
checkNull Trie k a
x
  | Trie k a -> Bool
forall k a. TrieKey k => Trie k a -> Bool
trieNull Trie k a
x = Maybe (Trie k a)
forall a. Maybe a
Nothing
  | Bool
otherwise  = Trie k a -> Maybe (Trie k a)
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 :: K1 i k p -> GTrie (K1 i k) a -> Maybe a
gtrieLookup (K1 k
k) (KTrie x)          = k -> Trie k a -> Maybe a
forall k a. TrieKey k => k -> Trie k a -> Maybe a
trieLookup k
k Trie k a
x
  gtrieInsert :: K1 i k p -> a -> GTrie (K1 i k) a -> GTrie (K1 i k) a
gtrieInsert (K1 k
k) a
v (KTrie t)        = Trie k a -> GTrie (K1 i k) a
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (k -> a -> Trie k a -> Trie k a
forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
trieInsert k
k a
v Trie k a
t)
  gtrieSingleton :: K1 i k p -> a -> GTrie (K1 i k) a
gtrieSingleton (K1 k
k) a
v               = Trie k a -> GTrie (K1 i k) a
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (k -> a -> Trie k a
forall k a. TrieKey k => k -> a -> Trie k a
trieSingleton k
k a
v)
  gtrieDelete :: K1 i k p -> GTrie (K1 i k) a -> Maybe (GTrie (K1 i k) a)
gtrieDelete (K1 k
k) (KTrie t)          = (Trie k a -> GTrie (K1 i k) a)
-> Maybe (Trie k a) -> Maybe (GTrie (K1 i k) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k a -> GTrie (K1 i k) a
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (Trie k a -> Maybe (Trie k a)
forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull (k -> Trie k a -> Trie k a
forall k a. TrieKey k => k -> Trie k a -> Trie k a
trieDelete k
k Trie k a
t))
  gtrieMap :: (a -> b) -> GTrie (K1 i k) a -> GTrie (K1 i k) b
gtrieMap a -> b
f (KTrie x)                  = Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie ((a -> b) -> Trie k a -> Trie k b
forall k a b. TrieKey k => (a -> b) -> Trie k a -> Trie k b
trieMap a -> b
f Trie k a
x)
  gtrieTraverse :: (a -> m b) -> GTrie (K1 i k) a -> m (GTrie (K1 i k) b)
gtrieTraverse a -> m b
f (KTrie x)             = (Trie k b -> GTrie (K1 i k) b)
-> m (Trie k b) -> m (GTrie (K1 i k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie ((a -> m b) -> Trie k a -> m (Trie k b)
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 :: (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 x)          = (Trie k b -> GTrie (K1 i k) b)
-> Maybe (Trie k b) -> Maybe (GTrie (K1 i k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (Trie k b -> Maybe (Trie k b)
forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull ((k -> a -> Maybe b) -> Trie k a -> Trie k b
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 (K1 i k p -> a -> Maybe b) -> (k -> K1 i k p) -> k -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> K1 i k p
forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x))
  gfoldWithKey :: (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 x)            = (k -> a -> r -> r) -> r -> Trie k a -> r
forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey (K1 i k p -> a -> r -> r
f (K1 i k p -> a -> r -> r) -> (k -> K1 i k p) -> k -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> K1 i k p
forall k i c (p :: k). c -> K1 i c p
K1) r
z Trie k a
x
  gtraverseWithKey :: (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 x)          = (Trie k b -> GTrie (K1 i k) b)
-> m (Trie k b) -> m (GTrie (K1 i k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie ((k -> a -> m b) -> Trie k a -> m (Trie k b)
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 (K1 i k p -> a -> m b) -> (k -> K1 i k p) -> k -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> K1 i k p
forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x)
  gtraverseMaybeWithKey :: (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 x)     = (Trie k b -> Maybe (GTrie (K1 i k) b))
-> m (Trie k b) -> m (Maybe (GTrie (K1 i k) b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Trie k b -> GTrie (K1 i k) b)
-> Maybe (Trie k b) -> Maybe (GTrie (K1 i k) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (Maybe (Trie k b) -> Maybe (GTrie (K1 i k) b))
-> (Trie k b -> Maybe (Trie k b))
-> Trie k b
-> Maybe (GTrie (K1 i k) b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Trie k b -> Maybe (Trie k b)
forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull) ((k -> a -> m (Maybe b)) -> Trie k a -> m (Trie k b)
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 (K1 i k p -> a -> m (Maybe b))
-> (k -> K1 i k p) -> k -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> K1 i k p
forall k i c (p :: k). c -> K1 i c p
K1) Trie k a
x)
  gmergeWithKey :: (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 x) (KTrie y) = (Trie k c -> GTrie (K1 i k) c)
-> Maybe (Trie k c) -> Maybe (GTrie (K1 i k) c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Trie k c -> GTrie (K1 i k) c
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie (Trie k c -> Maybe (Trie k c)
forall k a. TrieKey k => Trie k a -> Maybe (Trie k a)
checkNull ((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
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 (K1 i k p -> a -> b -> Maybe c)
-> (k -> K1 i k p) -> k -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> K1 i k p
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 (Trie k a -> GTrie (K1 i k) a
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie Trie k a
t) of
              Just (KTrie t') -> Trie k c
t'
              Maybe (GTrie (K1 i k) c)
Nothing         -> Trie k c
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 (Trie k b -> GTrie (K1 i k) b
forall i k a. Trie k a -> GTrie (K1 i k) a
KTrie Trie k b
t) of
              Just (KTrie t') -> Trie k c
t'
              Maybe (GTrie (K1 i k) c)
Nothing         -> Trie k c
forall k a. TrieKey k => Trie k a
trieEmpty
  {-# INLINE gtrieLookup #-}
  {-# INLINE gtrieInsert #-}
  {-# INLINE gtrieSingleton #-}
  {-# INLINE gtrieDelete #-}
  {-# INLINE gtrieMap #-}
  {-# INLINE gtrieTraverse #-}
  {-# INLINE gfoldWithKey #-}
  {-# INLINE gtraverseWithKey #-}
  {-# INLINE gtraverseMaybeWithKey #-}
  {-# INLINE gmergeWithKey #-}
  {-# INLINE gmapMaybeWithKey #-}

instance ShowTrieKey k => GTrieKeyShow (K1 i k) where
  gtrieShowsPrec :: Int -> GTrie (K1 i k) a -> ShowS
gtrieShowsPrec Int
p (KTrie x)            = Int -> Trie k a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec 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 :: (:*:) f g p -> GTrie (f :*: g) a -> Maybe a
gtrieLookup (f p
i :*: g p
j) (PTrie x)       = g p -> GTrie g a -> Maybe a
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup g p
j (GTrie g a -> Maybe a) -> Maybe (GTrie g a) -> Maybe a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< f p -> GTrie f (GTrie g a) -> Maybe (GTrie g a)
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g a)
x
  gtrieInsert :: (:*:) f g p -> a -> GTrie (f :*: g) a -> GTrie (f :*: g) a
gtrieInsert (f p
i :*: g p
j) a
v (PTrie t)     = case f p -> GTrie f (GTrie g a) -> Maybe (GTrie g a)
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g a)
t of
                                            Maybe (GTrie g a)
Nothing -> GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g a -> GTrie f (GTrie g a) -> GTrie f (GTrie g a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
i (g p -> a -> GTrie g a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
j a
v) GTrie f (GTrie g a)
t)
                                            Just GTrie g a
ti -> GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g a -> GTrie f (GTrie g a) -> GTrie f (GTrie g a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
i (g p -> a -> GTrie g a -> GTrie g a
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert g p
j a
v GTrie g a
ti) GTrie f (GTrie g a)
t)
  gtrieDelete :: (:*:) f g p -> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a)
gtrieDelete (f p
i :*: g p
j) (PTrie t)       = case f p -> GTrie f (GTrie g a) -> Maybe (GTrie g a)
forall (f :: * -> *) p a. GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieLookup f p
i GTrie f (GTrie g a)
t of
                                            Maybe (GTrie g a)
Nothing -> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a)
forall a. a -> Maybe a
Just (GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie GTrie f (GTrie g a)
t)
                                            Just GTrie g a
ti -> case g p -> GTrie g a -> Maybe (GTrie g a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete g p
j GTrie g a
ti of
                                                         Maybe (GTrie g a)
Nothing -> (GTrie f (GTrie g a) -> GTrie (f :*: g) a)
-> Maybe (GTrie f (GTrie g a)) -> Maybe (GTrie (f :*: g) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (Maybe (GTrie f (GTrie g a)) -> Maybe (GTrie (f :*: g) a))
-> Maybe (GTrie f (GTrie g a)) -> Maybe (GTrie (f :*: g) a)
forall a b. (a -> b) -> a -> b
$! f p -> GTrie f (GTrie g a) -> Maybe (GTrie f (GTrie g a))
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> GTrie f a -> Maybe (GTrie f a)
gtrieDelete f p
i GTrie f (GTrie g a)
t
                                                         Just GTrie g a
tj -> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a)
forall a. a -> Maybe a
Just (GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a))
-> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g a -> GTrie f (GTrie g a) -> GTrie f (GTrie g a)
forall (f :: * -> *) p a.
GTrieKey f =>
f p -> a -> GTrie f a -> GTrie f a
gtrieInsert f p
i GTrie g a
tj GTrie f (GTrie g a)
t)
  gtrieSingleton :: (:*:) f g p -> a -> GTrie (f :*: g) a
gtrieSingleton (f p
i :*: g p
j) a
v            = GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g a -> GTrie f (GTrie g a)
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i (g p -> a -> GTrie g a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
j a
v))
  gtrieMap :: (a -> b) -> GTrie (f :*: g) a -> GTrie (f :*: g) b
gtrieMap a -> b
f (PTrie x)                  = GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie ((GTrie g a -> GTrie g b)
-> GTrie f (GTrie g a) -> GTrie f (GTrie g b)
forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap ((a -> b) -> GTrie g a -> GTrie g b
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 :: (a -> m b) -> GTrie (f :*: g) a -> m (GTrie (f :*: g) b)
gtrieTraverse a -> m b
f (PTrie x)             = (GTrie f (GTrie g b) -> GTrie (f :*: g) b)
-> m (GTrie f (GTrie g b)) -> m (GTrie (f :*: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie ((GTrie g a -> m (GTrie g b))
-> GTrie f (GTrie g a) -> m (GTrie f (GTrie g b))
forall (f :: * -> *) (m :: * -> *) a b.
(GTrieKey f, Applicative m) =>
(a -> m b) -> GTrie f a -> m (GTrie f b)
gtrieTraverse ((a -> m b) -> GTrie g a -> m (GTrie g b)
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 :: ((:*:) f g p -> a -> Maybe b)
-> GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) b)
gmapMaybeWithKey (:*:) f g p -> a -> Maybe b
f (PTrie x)          = (GTrie f (GTrie g b) -> GTrie (f :*: g) b)
-> Maybe (GTrie f (GTrie g b)) -> Maybe (GTrie (f :*: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie ((f p -> GTrie g a -> Maybe (GTrie g b))
-> GTrie f (GTrie g a) -> Maybe (GTrie f (GTrie g b))
forall (f :: * -> *) p a b.
GTrieKey f =>
(f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gmapMaybeWithKey (\f p
i -> (g p -> a -> Maybe b) -> GTrie g a -> Maybe (GTrie g b)
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
if p -> g p -> (:*:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*:g p
j))) GTrie f (GTrie g a)
x)
  gfoldWithKey :: ((:*:) f g p -> a -> r -> r) -> r -> GTrie (f :*: g) a -> r
gfoldWithKey (:*:) f g p -> a -> r -> r
f r
z (PTrie x)            = (f p -> GTrie g a -> r -> r) -> r -> GTrie f (GTrie g a) -> r
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 -> (g p -> a -> r -> r) -> r -> GTrie g a -> 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
if p -> g p -> (:*:) f g p
forall 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 :: ((:*:) f g p -> a -> m b)
-> GTrie (f :*: g) a -> m (GTrie (f :*: g) b)
gtraverseWithKey (:*:) f g p -> a -> m b
f (PTrie x)          = (GTrie f (GTrie g b) -> GTrie (f :*: g) b)
-> m (GTrie f (GTrie g b)) -> m (GTrie (f :*: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie ((f p -> GTrie g a -> m (GTrie g b))
-> GTrie f (GTrie g a) -> m (GTrie f (GTrie g b))
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 ->
                                                      (g p -> a -> m b) -> GTrie g a -> m (GTrie g b)
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 f p -> g p -> (:*:) f g p
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 :: ((:*:) 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 x)     = (Maybe (GTrie f (GTrie g b)) -> Maybe (GTrie (f :*: g) b))
-> m (Maybe (GTrie f (GTrie g b))) -> m (Maybe (GTrie (f :*: g) b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((GTrie f (GTrie g b) -> GTrie (f :*: g) b)
-> Maybe (GTrie f (GTrie g b)) -> Maybe (GTrie (f :*: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie) ((f p -> GTrie g a -> m (Maybe (GTrie g b)))
-> GTrie f (GTrie g a) -> m (Maybe (GTrie f (GTrie g 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 p
i ->
                                                      (g p -> a -> m (Maybe b)) -> GTrie g a -> m (Maybe (GTrie g 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 (\g p
j -> (:*:) f g p -> a -> m (Maybe b)
f (f p
i f p -> g p -> (:*:) f g p
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 :: ((:*:) 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 x) (PTrie y) =
    (GTrie f (GTrie g c) -> GTrie (f :*: g) c)
-> Maybe (GTrie f (GTrie g c)) -> Maybe (GTrie (f :*: g) c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f (GTrie g c) -> GTrie (f :*: g) c
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (Maybe (GTrie f (GTrie g c)) -> Maybe (GTrie (f :*: g) c))
-> Maybe (GTrie f (GTrie g c)) -> Maybe (GTrie (f :*: g) c)
forall a b. (a -> b) -> a -> b
$!
       (f p -> GTrie g a -> GTrie g b -> Maybe (GTrie g c))
-> (GTrie f (GTrie g a) -> Maybe (GTrie f (GTrie g c)))
-> (GTrie f (GTrie g b) -> Maybe (GTrie f (GTrie g c)))
-> GTrie f (GTrie g a)
-> GTrie f (GTrie g b)
-> Maybe (GTrie f (GTrie g c))
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 ->
           (g p -> a -> b -> Maybe c)
-> (GTrie g a -> Maybe (GTrie g c))
-> (GTrie g b -> Maybe (GTrie g c))
-> GTrie g a
-> GTrie g b
-> Maybe (GTrie g c)
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
if p -> g p -> (:*:) f g p
forall 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))
         ((GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c))
-> GTrie f (GTrie g a) -> Maybe (GTrie f (GTrie g c))
coerce GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c)
g)
         ((GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c))
-> GTrie f (GTrie g b) -> Maybe (GTrie f (GTrie g c))
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 t' <- GTrie (f :*: g) a -> Maybe (GTrie (f :*: g) c)
g (GTrie f (GTrie g a) -> GTrie (f :*: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g a -> GTrie f (GTrie g a)
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i GTrie g a
t))
                f p -> GTrie f (GTrie g c) -> Maybe (GTrie g c)
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 t' <- GTrie (f :*: g) b -> Maybe (GTrie (f :*: g) c)
h (GTrie f (GTrie g b) -> GTrie (f :*: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f (GTrie g a) -> GTrie (f :*: g) a
PTrie (f p -> GTrie g b -> GTrie f (GTrie g b)
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton f p
i GTrie g b
t))
                f p -> GTrie f (GTrie g c) -> Maybe (GTrie g c)
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 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 :: Int -> GTrie (f :*: g) a -> ShowS
gtrieShowsPrec Int
p (PTrie x)            = Int -> GTrie f (GTrie g a) -> ShowS
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 :: (:+:) f g p -> GTrie (f :+: g) a -> Maybe a
gtrieLookup (L1 f p
k) (STrieL x)         = f p -> GTrie f a -> Maybe a
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 x _)       = f p -> GTrie f a -> Maybe 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 y)         = g p -> GTrie g a -> Maybe a
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 _ y)       = g p -> GTrie g a -> Maybe a
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
_                  = Maybe a
forall a. Maybe a
Nothing

  gtrieInsert :: (:+:) f g p -> a -> GTrie (f :+: g) a -> GTrie (f :+: g) a
gtrieInsert (L1 f p
k) a
v (STrieL x)       = GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (f p -> a -> GTrie f a -> GTrie f a
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 y)       = GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (f p -> a -> GTrie f a
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 x y)     = GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB (f p -> a -> GTrie f a -> GTrie f a
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 x)       = GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x (g p -> a -> GTrie g a
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 y)       = GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (g p -> a -> GTrie g a -> GTrie g a
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 x y)     = GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x (g p -> a -> GTrie g a -> GTrie g a
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 :: (:+:) f g p -> a -> GTrie (f :+: g) a
gtrieSingleton (L1 f p
k) a
v               = GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (f p -> a -> GTrie f a
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               = GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (g p -> a -> GTrie g a
forall (f :: * -> *) p a. GTrieKey f => f p -> a -> GTrie f a
gtrieSingleton g p
k a
v)

  gtrieDelete :: (:+:) f g p -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
gtrieDelete (L1 f p
k) (STrieL x)         = (GTrie f a -> GTrie (f :+: g) a)
-> Maybe (GTrie f a) -> Maybe (GTrie (f :+: g) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (Maybe (GTrie f a) -> Maybe (GTrie (f :+: g) a))
-> Maybe (GTrie f a) -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! f p -> GTrie f a -> Maybe (GTrie f a)
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 y)         = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y
  gtrieDelete (L1 f p
k) (STrieB x y)       = case f p -> GTrie f a -> Maybe (GTrie f a)
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 -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
y
                                            Just GTrie f a
x' -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie g a -> GTrie (f :+: g) a
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 x)         = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x
  gtrieDelete (R1 g p
k) (STrieR y)         = (GTrie g a -> GTrie (f :+: g) a)
-> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a))
-> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! g p -> GTrie g a -> Maybe (GTrie g a)
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 x y)       = case g p -> GTrie g a -> Maybe (GTrie g a)
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 -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
x
                                            Just GTrie g a
y' -> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x GTrie g a
y'

  gtrieMap :: (a -> b) -> GTrie (f :+: g) a -> GTrie (f :+: g) b
gtrieMap a -> b
f (STrieB x y)               = GTrie f b -> GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB ((a -> b) -> GTrie f a -> GTrie f b
forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie f a
x) ((a -> b) -> GTrie g a -> GTrie g b
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 x)                 = GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL ((a -> b) -> GTrie f a -> GTrie f b
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 y)                 = GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR ((a -> b) -> GTrie g a -> GTrie g b
forall (f :: * -> *) a b.
GTrieKey f =>
(a -> b) -> GTrie f a -> GTrie f b
gtrieMap a -> b
f GTrie g a
y)

  gtrieTraverse :: (a -> m b) -> GTrie (f :+: g) a -> m (GTrie (f :+: g) b)
gtrieTraverse a -> m b
f (STrieB x y)          = (GTrie f b -> GTrie g b -> GTrie (f :+: g) b)
-> m (GTrie f b) -> m (GTrie g b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 GTrie f b -> GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB ((a -> m b) -> GTrie f a -> m (GTrie f b)
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) ((a -> m b) -> GTrie g a -> m (GTrie g b)
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 x)            = (GTrie f b -> GTrie (f :+: g) b)
-> m (GTrie f b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL ((a -> m b) -> GTrie f a -> m (GTrie f b)
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 y)            = (GTrie g b -> GTrie (f :+: g) b)
-> m (GTrie g b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR ((a -> m b) -> GTrie g a -> m (GTrie g b)
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 :: ((:+:) f g p -> a -> Maybe b)
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) b)
gmapMaybeWithKey (:+:) f g p -> a -> Maybe b
f (STrieL x)         = (GTrie f b -> GTrie (f :+: g) b)
-> Maybe (GTrie f b) -> Maybe (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (Maybe (GTrie f b) -> Maybe (GTrie (f :+: g) b))
-> Maybe (GTrie f b) -> Maybe (GTrie (f :+: g) b)
forall a b. (a -> b) -> a -> b
$! (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f 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 ((:+:) f g p -> a -> Maybe b)
-> (f p -> (:+:) f g p) -> f p -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
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 y)         = (GTrie g b -> GTrie (f :+: g) b)
-> Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b))
-> Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b)
forall a b. (a -> b) -> a -> b
$! (g p -> a -> Maybe b) -> GTrie g a -> Maybe (GTrie g 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 ((:+:) f g p -> a -> Maybe b)
-> (g p -> (:+:) f g p) -> g p -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 x y)       = case ((f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f 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 ((:+:) f g p -> a -> Maybe b)
-> (f p -> (:+:) f g p) -> f p -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x, (g p -> a -> Maybe b) -> GTrie g a -> Maybe (GTrie g 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 ((:+:) f g p -> a -> Maybe b)
-> (g p -> (:+:) f g p) -> g p -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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) -> Maybe (GTrie (f :+: g) b)
forall a. Maybe a
Nothing
                                            (Just GTrie f b
x', Maybe (GTrie g b)
Nothing) -> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a. a -> Maybe a
Just (GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b))
-> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a b. (a -> b) -> a -> b
$! GTrie f b -> GTrie (f :+: g) 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') -> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a. a -> Maybe a
Just (GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b))
-> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a b. (a -> b) -> a -> b
$! GTrie g b -> GTrie (f :+: g) 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') -> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a. a -> Maybe a
Just (GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b))
-> GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) b)
forall a b. (a -> b) -> a -> b
$! GTrie f b -> GTrie g b -> GTrie (f :+: g) 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 :: ((:+:) 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 x)         = (GTrie f b -> GTrie (f :+: g) b)
-> Maybe (GTrie f b) -> Maybe (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL (Maybe (GTrie f b) -> Maybe (GTrie (f :+: g) b))
-> m (Maybe (GTrie f b)) -> m (Maybe (GTrie (f :+: g) b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie 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 ((:+:) f g p -> a -> m (Maybe b))
-> (f p -> (:+:) f g p) -> f p -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
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 y)         = (GTrie g b -> GTrie (f :+: g) b)
-> Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR (Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b))
-> m (Maybe (GTrie g b)) -> m (Maybe (GTrie (f :+: g) b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (g p -> a -> m (Maybe b)) -> GTrie g a -> m (Maybe (GTrie g 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 ((:+:) f g p -> a -> m (Maybe b))
-> (g p -> (:+:) f g p) -> g p -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 x y)       =
    (Maybe (GTrie f b)
 -> Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b))
-> m (Maybe (GTrie f b))
-> m (Maybe (GTrie g b))
-> m (Maybe (GTrie (f :+: g) b))
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Maybe (GTrie f b) -> Maybe (GTrie g b) -> Maybe (GTrie (f :+: g) b)
forall (f :: * -> *) a (g :: * -> *).
Maybe (GTrie f a) -> Maybe (GTrie g a) -> Maybe (GTrie (f :+: g) a)
finish ((f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie 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 ((:+:) f g p -> a -> m (Maybe b))
-> (f p -> (:+:) f g p) -> f p -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x) ((g p -> a -> m (Maybe b)) -> GTrie g a -> m (Maybe (GTrie g 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 ((:+:) f g p -> a -> m (Maybe b))
-> (g p -> (:+:) f g p) -> g p -> a -> m (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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    = Maybe (GTrie (f :+: g) a)
forall a. Maybe a
Nothing
      finish (Just GTrie f a
x') Maybe (GTrie g a)
Nothing    = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie (f :+: g) a
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')  = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie g a -> GTrie (f :+: g) a
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')  = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a))
-> GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a b. (a -> b) -> a -> b
$! GTrie f a -> GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB GTrie f a
x' GTrie g a
y'

  gfoldWithKey :: ((:+:) f g p -> a -> r -> r) -> r -> GTrie (f :+: g) a -> r
gfoldWithKey (:+:) f g p -> a -> r -> r
f r
z (STrieL x)           = (f p -> a -> r -> r) -> r -> GTrie f a -> r
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 ((:+:) f g p -> a -> r -> r)
-> (f p -> (:+:) f g p) -> f p -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
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 y)           = (g p -> a -> r -> r) -> r -> GTrie g a -> r
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 ((:+:) f g p -> a -> r -> r)
-> (g p -> (:+:) f g p) -> g p -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 x y)         = (f p -> a -> r -> r) -> r -> GTrie f a -> r
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 ((:+:) f g p -> a -> r -> r)
-> (f p -> (:+:) f g p) -> f p -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) ((g p -> a -> r -> r) -> r -> GTrie g a -> r
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 ((:+:) f g p -> a -> r -> r)
-> (g p -> (:+:) f g p) -> g p -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 :: ((:+:) f g p -> a -> m b)
-> GTrie (f :+: g) a -> m (GTrie (f :+: g) b)
gtraverseWithKey (:+:) f g p -> a -> m b
f (STrieL x)         = (GTrie f b -> GTrie (f :+: g) b)
-> m (GTrie f b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL ((f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
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 ((:+:) f g p -> a -> m b)
-> (f p -> (:+:) f g p) -> f p -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
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 y)         = (GTrie g b -> GTrie (f :+: g) b)
-> m (GTrie g b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR ((g p -> a -> m b) -> GTrie g a -> m (GTrie g b)
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 ((:+:) f g p -> a -> m b)
-> (g p -> (:+:) f g p) -> g p -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 x y)       = (GTrie f b -> GTrie g b -> GTrie (f :+: g) b)
-> m (GTrie f b) -> m (GTrie g b) -> m (GTrie (f :+: g) b)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 GTrie f b -> GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie g a -> GTrie (f :+: g) a
STrieB ((f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
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 ((:+:) f g p -> a -> m b)
-> (f p -> (:+:) f g p) -> f p -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k). f p -> (:+:) f g p
L1) GTrie f a
x)
                                                        ((g p -> a -> m b) -> GTrie g a -> m (GTrie g b)
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 ((:+:) f g p -> a -> m b)
-> (g p -> (:+:) f g p) -> g p -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k). g p -> (:+:) f g p
R1) GTrie g a
y)

  gmergeWithKey :: ((:+:) 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 (GTrie (f :+: g) a -> (Maybe (GTrie f a), Maybe (GTrie g a))
forall (f :: * -> *) (g :: * -> *) a.
GTrie (f :+: g) a -> (Maybe (GTrie f a), Maybe (GTrie g a))
split GTrie (f :+: g) a
x0, GTrie (f :+: g) b -> (Maybe (GTrie f b), Maybe (GTrie g b))
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)) -> Maybe (GTrie f c) -> Maybe (GTrie g c) -> Maybe (GTrie (f :+: g) c)
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 x)   = (GTrie f a -> Maybe (GTrie f a)
forall a. a -> Maybe a
Just GTrie f a
x, Maybe (GTrie g a)
forall a. Maybe a
Nothing)
    split (STrieR y)   = (Maybe (GTrie f a)
forall a. Maybe a
Nothing, GTrie g a -> Maybe (GTrie g a)
forall a. a -> Maybe a
Just GTrie g a
y)
    split (STrieB x y) = (GTrie f a -> Maybe (GTrie f a)
forall a. a -> Maybe a
Just GTrie f a
x, GTrie g a -> Maybe (GTrie g a)
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) = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie f a -> GTrie g a -> GTrie (f :+: g) a
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  = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie f a -> GTrie (f :+: g) a
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) = GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) a)
forall a. a -> Maybe a
Just (GTrie g a -> GTrie (f :+: g) a
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  = Maybe (GTrie (f :+: g) a)
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  = Maybe (GTrie f c)
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) = (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)
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 ((:+:) f g p -> a -> b -> Maybe c)
-> (f p -> (:+:) f g p) -> f p -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f p -> (:+:) f g p
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  = Maybe (GTrie g c)
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) = (g p -> a -> b -> Maybe c)
-> (GTrie g a -> Maybe (GTrie g c))
-> (GTrie g b -> Maybe (GTrie g c))
-> GTrie g a
-> GTrie g b
-> Maybe (GTrie g c)
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 ((:+:) f g p -> a -> b -> Maybe c)
-> (g p -> (:+:) f g p) -> g p -> a -> b -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g p -> (:+:) f g p
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 t' <- GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c)
g (GTrie f a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f a
t)
              GTrie f c -> Maybe (GTrie f c)
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 t' <- GTrie (f :+: g) a -> Maybe (GTrie (f :+: g) c)
g (GTrie g a -> GTrie (f :+: g) a
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g a
t)
              GTrie g c -> Maybe (GTrie g c)
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 t' <- GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c)
h (GTrie f b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie f a -> GTrie (f :+: g) a
STrieL GTrie f b
t)
              GTrie f c -> Maybe (GTrie f c)
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 t' <- GTrie (f :+: g) b -> Maybe (GTrie (f :+: g) c)
h (GTrie g b -> GTrie (f :+: g) b
forall (f :: * -> *) (g :: * -> *) a.
GTrie g a -> GTrie (f :+: g) a
STrieR GTrie g b
t)
              GTrie g c -> Maybe (GTrie g c)
forall (m :: * -> *) a. Monad m => a -> m a
return GTrie g c
t'

  {-# INLINE gtrieLookup #-}
  {-# INLINE gtrieInsert #-}
  {-# INLINE gtrieDelete #-}
  {-# 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 :: Int -> GTrie (f :+: g) a -> ShowS
gtrieShowsPrec Int
p (STrieB x y)         = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
                                        (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieB "
                                        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> GTrie f a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
                                        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" "
                                        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> GTrie g a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie g a
y
  gtrieShowsPrec Int
p (STrieL x)           = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
                                        (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieL "
                                        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> GTrie f a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 GTrie f a
x
  gtrieShowsPrec Int
p (STrieR y)           = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
                                        (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"STrieR "
                                        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> GTrie g a -> ShowS
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 :: U1 p -> GTrie U1 a -> Maybe a
gtrieLookup U1 p
_ (UTrie x)       = a -> Maybe a
forall a. a -> Maybe a
Just a
x
  gtrieInsert :: U1 p -> a -> GTrie U1 a -> GTrie U1 a
gtrieInsert U1 p
_ a
v GTrie U1 a
_             = a -> GTrie U1 a
forall a. a -> GTrie U1 a
UTrie a
v
  gtrieDelete :: U1 p -> GTrie U1 a -> Maybe (GTrie U1 a)
gtrieDelete U1 p
_ GTrie U1 a
_               = Maybe (GTrie U1 a)
forall a. Maybe a
Nothing
  gtrieSingleton :: U1 p -> a -> GTrie U1 a
gtrieSingleton U1 p
_              = a -> GTrie U1 a
forall a. a -> GTrie U1 a
UTrie
  gtrieMap :: (a -> b) -> GTrie U1 a -> GTrie U1 b
gtrieMap a -> b
f (UTrie x)          = b -> GTrie U1 b
forall a. a -> GTrie U1 a
UTrie (a -> b
f a
x)
  gtrieTraverse :: (a -> m b) -> GTrie U1 a -> m (GTrie U1 b)
gtrieTraverse a -> m b
f (UTrie x)     = (b -> GTrie U1 b) -> m b -> m (GTrie U1 b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> GTrie U1 b
forall a. a -> GTrie U1 a
UTrie (a -> m b
f a
x)
  gmapMaybeWithKey :: (U1 p -> a -> Maybe b) -> GTrie U1 a -> Maybe (GTrie U1 b)
gmapMaybeWithKey U1 p -> a -> Maybe b
f (UTrie x)  = (b -> GTrie U1 b) -> Maybe b -> Maybe (GTrie U1 b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> GTrie U1 b
forall a. a -> GTrie U1 a
UTrie (Maybe b -> Maybe (GTrie U1 b)) -> Maybe b -> Maybe (GTrie U1 b)
forall a b. (a -> b) -> a -> b
$! U1 p -> a -> Maybe b
f U1 p
forall k (p :: k). U1 p
U1 a
x
  gtraverseMaybeWithKey :: (U1 p -> a -> m (Maybe b)) -> GTrie U1 a -> m (Maybe (GTrie U1 b))
gtraverseMaybeWithKey U1 p -> a -> m (Maybe b)
f (UTrie x)  = (Maybe b -> Maybe (GTrie U1 b))
-> m (Maybe b) -> m (Maybe (GTrie U1 b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((b -> GTrie U1 b) -> Maybe b -> Maybe (GTrie U1 b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> GTrie U1 b
forall a. a -> GTrie U1 a
UTrie) (m (Maybe b) -> m (Maybe (GTrie U1 b)))
-> m (Maybe b) -> m (Maybe (GTrie U1 b))
forall a b. (a -> b) -> a -> b
$! U1 p -> a -> m (Maybe b)
f U1 p
forall k (p :: k). U1 p
U1 a
x
  gfoldWithKey :: (U1 p -> a -> r -> r) -> r -> GTrie U1 a -> r
gfoldWithKey U1 p -> a -> r -> r
f r
z (UTrie x)    = U1 p -> a -> r -> r
f U1 p
forall k (p :: k). U1 p
U1 a
x r
z
  gtraverseWithKey :: (U1 p -> a -> m b) -> GTrie U1 a -> m (GTrie U1 b)
gtraverseWithKey U1 p -> a -> m b
f (UTrie x)  = (b -> GTrie U1 b) -> m b -> m (GTrie U1 b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> GTrie U1 b
forall a. a -> GTrie U1 a
UTrie (U1 p -> a -> m b
f U1 p
forall k (p :: k). U1 p
U1 a
x)
  gmergeWithKey :: (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 x) (UTrie y) = (c -> GTrie U1 c) -> Maybe c -> Maybe (GTrie U1 c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c -> GTrie U1 c
forall a. a -> GTrie U1 a
UTrie (Maybe c -> Maybe (GTrie U1 c)) -> Maybe c -> Maybe (GTrie U1 c)
forall a b. (a -> b) -> a -> b
$! U1 p -> a -> b -> Maybe c
f U1 p
forall k (p :: k). U1 p
U1 a
x b
y
  {-# INLINE gtrieLookup #-}
  {-# INLINE gtrieInsert #-}
  {-# INLINE gtrieDelete #-}
  {-# INLINE gtrieSingleton #-}
  {-# INLINE gtrieTraverse #-}
  {-# INLINE gtrieMap #-}
  {-# INLINE gfoldWithKey #-}
  {-# INLINE gtraverseWithKey #-}
  {-# INLINE gtraverseMaybeWithKey #-}
  {-# INLINE gmergeWithKey #-}
  {-# INLINE gmapMaybeWithKey #-}

instance GTrieKeyShow U1 where
  gtrieShowsPrec :: Int -> GTrie U1 a -> ShowS
gtrieShowsPrec Int
p (UTrie x)    = Int -> a -> ShowS
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 :: V1 p -> GTrie V1 a -> Maybe a
gtrieLookup V1 p
_ GTrie V1 a
t               = case GTrie V1 a
t of
  gtrieInsert :: V1 p -> a -> GTrie V1 a -> GTrie V1 a
gtrieInsert V1 p
_ a
_ GTrie V1 a
t             = case GTrie V1 a
t of
  gtrieDelete :: V1 p -> GTrie V1 a -> Maybe (GTrie V1 a)
gtrieDelete V1 p
_ GTrie V1 a
t               = case GTrie V1 a
t of
  gtrieSingleton :: V1 p -> a -> GTrie V1 a
gtrieSingleton V1 p
k a
_            = case V1 p
k of
  gtrieMap :: (a -> b) -> GTrie V1 a -> GTrie V1 b
gtrieMap a -> b
_ GTrie V1 a
t                  = case GTrie V1 a
t of
  gtrieTraverse :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 gtrieSingleton #-}
  {-# INLINE gtrieMap #-}
  {-# INLINE gtrieTraverse #-}
  {-# INLINE gfoldWithKey #-}
  {-# INLINE gtraverseWithKey #-}
  {-# INLINE gtraverseMaybeWithKey #-}
  {-# INLINE gmergeWithKey #-}
  {-# INLINE gmapMaybeWithKey #-}

instance GTrieKeyShow V1 where
  gtrieShowsPrec :: Int -> GTrie V1 a -> ShowS
gtrieShowsPrec Int
_ GTrie V1 a
_            = String -> ShowS
showString String
"()"


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

instance (Show a, ShowTrieKey k) => Show (Trie k a) where
  showsPrec :: Int -> Trie k a -> ShowS
showsPrec = Int -> Trie k a -> ShowS
forall k a. (ShowTrieKey k, Show a) => Int -> Trie k a -> ShowS
trieShowsPrec

instance (Show a, GTrieKeyShow f) => Show (GTrie f a) where
  showsPrec :: Int -> GTrie f a -> ShowS
showsPrec = Int -> GTrie f a -> ShowS
forall (f :: * -> *) a.
(GTrieKeyShow f, Show a) =>
Int -> GTrie f a -> ShowS
gtrieShowsPrec

instance TrieKey k => Functor (Trie k) where
  fmap :: (a -> b) -> Trie k a -> Trie k b
fmap = (a -> b) -> Trie k a -> Trie k b
forall k a b. TrieKey k => (a -> b) -> Trie k a -> Trie k b
trieMap

instance TrieKey k => Foldable (Trie k) where
  foldr :: (a -> b -> b) -> b -> Trie k a -> b
foldr a -> b -> b
f = (k -> a -> b -> b) -> b -> Trie k a -> b
forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey (\k
_ -> a -> b -> b
f)

instance TrieKey k => Traversable (Trie k) where
  traverse :: (a -> f b) -> Trie k a -> f (Trie k b)
traverse = (a -> f b) -> Trie k a -> f (Trie k b)
forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(a -> f b) -> Trie k a -> f (Trie k b)
trieTraverse