    {-# LANGUAGE CPP #-}
    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE FlexibleContexts #-}
    {-# LANGUAGE GADTs #-}
    {-# LANGUAGE PolyKinds #-}
    {-# LANGUAGE RankNTypes #-}
    {-# LANGUAGE ScopedTypeVariables #-}
    {-# LANGUAGE Trustworthy #-}
    {-# LANGUAGE TypeApplications #-}
    {-# LANGUAGE TypeOperators #-}
    {-# LANGUAGE UndecidableInstances #-}
    module Data.Dependent.Map
        ( DMap

        -- * Operators
        , (!), (\\)

        -- * Query
        , null
        , size
        , member
        , notMember
        , lookup
        , findWithDefault

        -- * Construction
        , empty
        , singleton

        -- ** Insertion
        , insert
        , insertWith
        , insertWith'
        , insertWithKey
        , insertWithKey'
        , insertLookupWithKey
        , insertLookupWithKey'

        -- ** Delete\/Update
        , delete
        , adjust
        , adjustWithKey
        , adjustWithKey'
        , update
        , updateWithKey
        , updateLookupWithKey
        , alter
        , alterF

        -- * Combine

        -- ** Union
        , union
        , unionWithKey
        , unions
        , unionsWithKey

        -- ** Difference
        , difference
        , differenceWithKey

        -- ** Intersection
        , intersection
        , intersectionWithKey

        -- * Traversal
        -- ** Map
        , map
        , ffor
        , mapWithKey
        , fforWithKey
        , traverseWithKey_
        , forWithKey_
        , traverseWithKey
        , forWithKey
        , mapAccumLWithKey
        , mapAccumRWithKey
        , mapKeysWith
        , mapKeysMonotonic

        -- ** Fold
        , foldWithKey
        , foldrWithKey
        , foldlWithKey
        -- , foldlWithKey'

        -- * Conversion
        , keys
        , assocs

        -- ** Lists
        , toList
        , fromList
        , fromListWithKey

        -- ** Ordered lists
        , toAscList
        , toDescList
        , fromAscList
        , fromAscListWithKey
        , fromDistinctAscList

        -- * Filter
        , filter
        , filterWithKey
        , partitionWithKey

        , mapMaybe
        , mapMaybeWithKey
        , mapEitherWithKey

        , split
        , splitLookup

        -- * Submap
        , isSubmapOf, isSubmapOfBy
        , isProperSubmapOf, isProperSubmapOfBy

        -- * Indexed
        , lookupIndex
        , findIndex
        , elemAt
        , updateAt
        , deleteAt

        -- * Min\/Max
        , findMin
        , findMax
        , lookupMin
        , lookupMax
        , deleteMin
        , deleteMax
        , deleteFindMin
        , deleteFindMax
        , updateMinWithKey
        , updateMaxWithKey
        , minViewWithKey
        , maxViewWithKey

        -- * Debugging
        , showTree
        , showTreeWith
        , valid
        ) where

    import Prelude hiding (null, lookup, map)
    import qualified Prelude
    import Data.Constraint.Extras (Has', has')
    import Data.Dependent.Sum (DSum((:=>)))
    import Data.GADT.Compare (GCompare, GEq, GOrdering(..), gcompare, geq)
    import Data.GADT.Show (GRead, GShow)
    import Data.Maybe (isJust)
    import Data.Some (Some, mkSome)
    import Data.Typeable ((:~:)(Refl))
    import Text.Read (Lexeme(Ident), lexP, parens, prec, readListPrec,
                      readListPrecDefault, readPrec)

    import Data.Dependent.Map.Internal
    import Data.Dependent.Map.PtrEquality (ptrEq)

    instance (GCompare k) => Monoid (DMap k f) where
        mempty :: DMap k f
    mempty  = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    empty
        mconcat :: [DMap k f] -> DMap k f
    mconcat = [DMap k f] -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    [DMap k f] -> DMap k f
    unions

    instance (GCompare k) => Semigroup (DMap k f) where
      <> :: DMap k f -> DMap k f -> DMap k f
    (<>) = DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    union

    {--------------------------------------------------------------------
      Operators
    --------------------------------------------------------------------}
    infixl 9 \\,! -- \\ at the end of the line means line continuation

    -- | /O(log n)/. Find the value at a key.
    -- Calls 'error' when the element can not be found.
    --
    -- > fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
    -- > fromList [(5,'a'), (3,'b')] ! 5 == 'a'

    (!) :: GCompare k => DMap k f -> k v -> f v
    ! :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    DMap k f -> k v -> f v
    (!) DMap k f
    m k v
    k    = k v -> DMap k f -> f v
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    k v -> DMap k f -> f v
    find k v
    k DMap k f
    m

    -- | Same as 'difference'.
    (\\) :: GCompare k => DMap k f -> DMap k f -> DMap k f
    DMap k f
    m1 \\ :: forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    \\ DMap k f
    m2 = DMap k f -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    DMap k f -> DMap k g -> DMap k f
    difference DMap k f
    m1 DMap k f
    m2

    -- #if __GLASGOW_HASKELL__
    --
    -- {--------------------------------------------------------------------
    --   A Data instance
    -- --------------------------------------------------------------------}
    --
    -- -- This instance preserves data abstraction at the cost of inefficiency.
    -- -- We omit reflection services for the sake of data abstraction.
    --
    -- instance (Data k, Data a, GCompare k) => Data (DMap k) where
    --   gfoldl f z m   = z fromList `f` toList m
    --   toConstr _     = error "toConstr"
    --   gunfold _ _    = error "gunfold"
    --   dataTypeOf _   = mkNoRepType "Data.Map.Map"
    --   dataCast2 f    = gcast2 f
    --
    -- #endif

    {--------------------------------------------------------------------
      Query
    --------------------------------------------------------------------}

    -- | /O(log n)/. Is the key a member of the map? See also 'notMember'.
    member :: GCompare k => k a -> DMap k f -> Bool
    member :: forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
    GCompare k =>
    k a -> DMap k f -> Bool
    member k a
    k = Maybe (f a) -> Bool
    forall a. Maybe a -> Bool
    isJust (Maybe (f a) -> Bool)
    -> (DMap k f -> Maybe (f a)) -> DMap k f -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k a -> DMap k f -> Maybe (f a)
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
    GCompare k2 =>
    k2 v -> DMap k2 f -> Maybe (f v)
    lookup k a
    k

    -- | /O(log n)/. Is the key not a member of the map? See also 'member'.
    notMember :: GCompare k => k v -> DMap k f -> Bool
    notMember :: forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
    GCompare k =>
    k a -> DMap k f -> Bool
    notMember k v
    k DMap k f
    m = Bool -> Bool
    not (k v -> DMap k f -> Bool
    forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
    GCompare k =>
    k a -> DMap k f -> Bool
    member k v
    k DMap k f
    m)

    -- | /O(log n)/. Find the value at a key.
    -- Calls 'error' when the element can not be found.
    -- Consider using 'lookup' when elements may not be present.
    find :: GCompare k => k v -> DMap k f -> f v
    find :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    k v -> DMap k f -> f v
    find k v
    k DMap k f
    m = case k v -> DMap k f -> Maybe (f v)
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
    GCompare k2 =>
    k2 v -> DMap k2 f -> Maybe (f v)
    lookup k v
    k DMap k f
    m of
        Maybe (f v)
    Nothing -> [Char] -> f v
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "DMap.find: element not in the map"
        Just f v
    v  -> f v
    v

    -- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns
    -- the value at key @k@ or returns default value @def@
    -- when the key is not in the map.
    findWithDefault :: GCompare k => f v -> k v -> DMap k f -> f v
    findWithDefault :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    f v -> k v -> DMap k f -> f v
    findWithDefault f v
    def k v
    k DMap k f
    m = case k v -> DMap k f -> Maybe (f v)
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
    GCompare k2 =>
    k2 v -> DMap k2 f -> Maybe (f v)
    lookup k v
    k DMap k f
    m of
        Maybe (f v)
    Nothing -> f v
    def
        Just f v
    v  -> f v
    v

    {--------------------------------------------------------------------
      Insertion
    --------------------------------------------------------------------}

    -- | /O(log n)/. Insert a new key and value in the map.
    -- If the key is already present in the map, the associated value is
    -- replaced with the supplied value. 'insert' is equivalent to
    -- @'insertWith' 'const'@.
    insert :: forall k f v. GCompare k => k v -> f v -> DMap k f -> DMap k f
    insert :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> f v -> DMap k f -> DMap k f
    insert k v
    kx f v
    x = k v
    kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
        where
            go :: DMap k f -> DMap k f
            go :: DMap k f -> DMap k f
    go DMap k f
    Tip = k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx f v
    x
            go t :: DMap k f
    t@(Bin Int
    sz k v
    ky f v
    y DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> let !l' :: DMap k f
    l' = DMap k f -> DMap k f
    go DMap k f
    l
                       in if DMap k f
    l' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    l
                          then DMap k f
    t
                          else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l' DMap k f
    r
                GOrdering v v
    GGT -> let !r' :: DMap k f
    r' = DMap k f -> DMap k f
    go DMap k f
    r
                       in if DMap k f
    r' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    r
                          then DMap k f
    t
                          else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l DMap k f
    r'
                GOrdering v v
    GEQ
                  | k v
    kx k v -> k v -> Bool
    forall a. a -> a -> Bool
    `ptrEq` k v
    k v
    ky Bool -> Bool -> Bool
    && f v
    x f v -> f v -> Bool
    forall a. a -> a -> Bool
    `ptrEq` f v
    f v
    y -> DMap k f
    t
                  | Bool
    otherwise -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sz k v
    kx f v
    x DMap k f
    l DMap k f
    r

    -- | /O(log n)/. Insert a new key and value in the map if the key
    -- is not already present. If the key is already present, @insertR@
    -- does nothing.
    insertR :: forall k f v. GCompare k => k v -> f v -> DMap k f -> DMap k f
    insertR :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> f v -> DMap k f -> DMap k f
    insertR k v
    kx f v
    x = k v
    kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
        where
            go :: DMap k f -> DMap k f
            go :: DMap k f -> DMap k f
    go DMap k f
    Tip = k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx f v
    x
            go t :: DMap k f
    t@(Bin Int
    sz k v
    ky f v
    y DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> let !l' :: DMap k f
    l' = DMap k f -> DMap k f
    go DMap k f
    l
                       in if DMap k f
    l' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    l
                          then DMap k f
    t
                          else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l' DMap k f
    r
                GOrdering v v
    GGT -> let !r' :: DMap k f
    r' = DMap k f -> DMap k f
    go DMap k f
    r
                       in if DMap k f
    r' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    r
                       then DMap k f
    t
                       else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l DMap k f
    r'
                GOrdering v v
    GEQ -> DMap k f
    t

    -- | /O(log n)/. Insert with a function, combining new value and old value.
    -- @'insertWith' f key value mp@
    -- will insert the entry @key :=> value@ into @mp@ if key does
    -- not exist in the map. If the key does exist, the function will
    -- insert the entry @key :=> f new_value old_value@.
    insertWith :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWith :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWith f v -> f v -> f v
    f = (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey (\k v
    _ f v
    x' f v
    y' -> f v -> f v -> f v
    f f v
    x' f v
    y')

    -- | Same as 'insertWith', but the combining function is applied strictly.
    -- This is often the most desirable behavior.
    insertWith' :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWith' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWith' f v -> f v -> f v
    f = (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey' (\k v
    _ f v
    x' f v
    y' -> f v -> f v -> f v
    f f v
    x' f v
    y')

    -- | /O(log n)/. Insert with a function, combining key, new value and old value.
    -- @'insertWithKey' f key value mp@
    -- will insert the entry @key :=> value@ into @mp@ if key does
    -- not exist in the map. If the key does exist, the function will
    -- insert the entry @key :=> f key new_value old_value@.
    -- Note that the key passed to f is the same key passed to 'insertWithKey'.
    insertWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey k v -> f v -> f v -> f v
    f k v
    kx f v
    x = k v
    kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx f v
    x
        go (Bin Int
    sy k v
    ky f v
    y DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
                GOrdering v v
    GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
                GOrdering v v
    GEQ -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sy k v
    kx (k v -> f v -> f v -> f v
    f k v
    kx f v
    x f v
    f v
    y) DMap k f
    l DMap k f
    r

    -- | Same as 'insertWithKey', but the combining function is applied strictly.
    insertWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey' k v -> f v -> f v -> f v
    f k v
    kx f v
    x = k v
    kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx (f v -> DMap k f) -> f v -> DMap k f
    forall a b. (a -> b) -> a -> b
    $! f v
    x
        go (Bin Int
    sy k v
    ky f v
    y DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
                GOrdering v v
    GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
                GOrdering v v
    GEQ -> let x' :: f v
    x' = k v -> f v -> f v -> f v
    f k v
    kx f v
    x f v
    f v
    y in f v -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    seq f v
    x' (Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sy k v
    kx f v
    x' DMap k f
    l DMap k f
    r)

    -- | /O(log n)/. Combines insert operation with old value retrieval.
    -- The expression (@'insertLookupWithKey' f k x map@)
    -- is a pair where the first element is equal to (@'lookup' k map@)
    -- and the second element equal to (@'insertWithKey' f k x map@).
    insertLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f
                        -> (Maybe (f v), DMap k f)
    insertLookupWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v)
    -> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
    insertLookupWithKey k v -> f v -> f v -> f v
    f k v
    kx f v
    x = k v
    kx k v
    -> (DMap k f -> (Maybe (f v), DMap k f))
    -> DMap k f
    -> (Maybe (f v), DMap k f)
    forall a b. a -> b -> b
    `seq` DMap k f -> (Maybe (f v), DMap k f)
    go
      where
        go :: DMap k f -> (Maybe (f v), DMap k f)
        go :: DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    Tip = (Maybe (f v)
    forall a. Maybe a
    Nothing, k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx f v
    x)
        go (Bin Int
    sy k v
    ky f v
    y DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> let (Maybe (f v)
    found, DMap k f
    l') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    l
                      in (Maybe (f v)
    found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l' DMap k f
    r)
                GOrdering v v
    GGT -> let (Maybe (f v)
    found, DMap k f
    r') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    r
                      in (Maybe (f v)
    found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l DMap k f
    r')
                GOrdering v v
    GEQ -> (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    f v
    y, Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sy k v
    kx (k v -> f v -> f v -> f v
    f k v
    kx f v
    x f v
    f v
    y) DMap k f
    l DMap k f
    r)

    -- | /O(log n)/. A strict version of 'insertLookupWithKey'.
    insertLookupWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f
                         -> (Maybe (f v), DMap k f)
    insertLookupWithKey' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v)
    -> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
    insertLookupWithKey' k v -> f v -> f v -> f v
    f k v
    kx f v
    x = k v
    kx k v
    -> (DMap k f -> (Maybe (f v), DMap k f))
    -> DMap k f
    -> (Maybe (f v), DMap k f)
    forall a b. a -> b -> b
    `seq` DMap k f -> (Maybe (f v), DMap k f)
    go
      where
        go :: DMap k f -> (Maybe (f v), DMap k f)
        go :: DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    Tip = f v
    x f v -> (Maybe (f v), DMap k f) -> (Maybe (f v), DMap k f)
    forall a b. a -> b -> b
    `seq` (Maybe (f v)
    forall a. Maybe a
    Nothing, k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    kx f v
    x)
        go (Bin Int
    sy k v
    ky f v
    y DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    kx k v
    ky of
                GOrdering v v
    GLT -> let (Maybe (f v)
    found, DMap k f
    l') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    l
                      in (Maybe (f v)
    found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l' DMap k f
    r)
                GOrdering v v
    GGT -> let (Maybe (f v)
    found, DMap k f
    r') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    r
                      in (Maybe (f v)
    found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    ky f v
    y DMap k f
    l DMap k f
    r')
                GOrdering v v
    GEQ -> let x' :: f v
    x' = k v -> f v -> f v -> f v
    f k v
    kx f v
    x f v
    f v
    y in f v
    x' f v -> (Maybe (f v), DMap k f) -> (Maybe (f v), DMap k f)
    forall a b. a -> b -> b
    `seq` (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    f v
    y, Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sy k v
    kx f v
    x' DMap k f
    l DMap k f
    r)

    {--------------------------------------------------------------------
      Deletion
      [delete] is the inlined version of [deleteWith (\k x -> Nothing)]
    --------------------------------------------------------------------}

    -- | /O(log n)/. Delete a key and its value from the map. When the key is not
    -- a member of the map, the original map is returned.
    delete :: forall k f v. GCompare k => k v -> DMap k f -> DMap k f
    delete :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> DMap k f
    delete k v
    k = k v
    k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
                GOrdering v v
    GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
                GOrdering v v
    GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
                GOrdering v v
    GEQ -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k f
    l DMap k f
    r

    -- | /O(log n)/. Update a value at a specific key with the result of the provided function.
    -- When the key is not
    -- a member of the map, the original map is returned.
    adjust :: GCompare k => (f v -> f v) -> k v -> DMap k f -> DMap k f
    adjust :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (f v -> f v) -> k v -> DMap k f -> DMap k f
    adjust f v -> f v
    f = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    adjustWithKey (\k v
    _ f v
    x -> f v -> f v
    f f v
    x)

    -- | /O(log n)/. Adjust a value at a specific key. When the key is not
    -- a member of the map, the original map is returned.
    adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    adjustWithKey :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    adjustWithKey k v -> f v -> f v
    f0 !k v
    k0 = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f0 k v
    k0
      where
        go :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
        go :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    _f k v
    _k DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go k v -> f v -> f v
    f k v
    k (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
          case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
            GOrdering v v
    GLT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f k v
    k DMap k f
    l) DMap k f
    r
            GOrdering v v
    GGT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x DMap k f
    l ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f k v
    k DMap k f
    r)
            GOrdering v v
    GEQ -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx (k v -> f v -> f v
    f k v
    k v
    kx f v
    f v
    x) DMap k f
    l DMap k f
    r

    -- | /O(log n)/. A strict version of 'adjustWithKey'.
    adjustWithKey' :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    adjustWithKey' :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    adjustWithKey' k v -> f v -> f v
    f0 !k v
    k0 = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f0 k v
    k0
      where
        go :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
        go :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    _f k v
    _k DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go k v -> f v -> f v
    f k v
    k (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
          case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
            GOrdering v v
    GLT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f k v
    k DMap k f
    l) DMap k f
    r
            GOrdering v v
    GGT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x DMap k f
    l ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go k v -> f v -> f v
    f k v
    k DMap k f
    r)
            GOrdering v v
    GEQ -> let !x' :: f v
    x' = k v -> f v -> f v
    f k v
    k v
    kx f v
    f v
    x in Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    f v
    x' DMap k f
    l DMap k f
    r

    -- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@
    -- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
    -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
    update :: GCompare k => (f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    update :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    update f v -> Maybe (f v)
    f = (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    updateWithKey (\k v
    _ f v
    x -> f v -> Maybe (f v)
    f f v
    x)

    -- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the
    -- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing',
    -- the element is deleted. If it is (@'Just' y@), the key @k@ is bound
    -- to the new value @y@.
    updateWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    updateWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    updateWithKey k v -> f v -> Maybe (f v)
    f k v
    k = k v
    k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
            case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
               GOrdering v v
    GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
               GOrdering v v
    GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
               GOrdering v v
    GEQ -> case k v -> f v -> Maybe (f v)
    f k v
    k v
    kx f v
    f v
    x of
                       Just f v
    x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    f v
    x' DMap k f
    l DMap k f
    r
                       Maybe (f v)
    Nothing -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k f
    l DMap k f
    r

    -- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
    -- The function returns changed value, if it is updated.
    -- Returns the original key value if the map entry is deleted.
    updateLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> (Maybe (f v), DMap k f)
    updateLookupWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> Maybe (f v))
    -> k v -> DMap k f -> (Maybe (f v), DMap k f)
    updateLookupWithKey k v -> f v -> Maybe (f v)
    f k v
    k = k v
    k k v
    -> (DMap k f -> (Maybe (f v), DMap k f))
    -> DMap k f
    -> (Maybe (f v), DMap k f)
    forall a b. a -> b -> b
    `seq` DMap k f -> (Maybe (f v), DMap k f)
    go
     where
       go :: DMap k f -> (Maybe (f v), DMap k f)
       go :: DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    Tip = (Maybe (f v)
    forall a. Maybe a
    Nothing,DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
       go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
              case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
                   GOrdering v v
    GLT -> let (Maybe (f v)
    found,DMap k f
    l') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    l in (Maybe (f v)
    found,k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l' DMap k f
    r)
                   GOrdering v v
    GGT -> let (Maybe (f v)
    found,DMap k f
    r') = DMap k f -> (Maybe (f v), DMap k f)
    go DMap k f
    r in (Maybe (f v)
    found,k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l DMap k f
    r')
                   GOrdering v v
    GEQ -> case k v -> f v -> Maybe (f v)
    f k v
    k v
    kx f v
    f v
    x of
                           Just f v
    x' -> (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    x',Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    f v
    x' DMap k f
    l DMap k f
    r)
                           Maybe (f v)
    Nothing -> (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    f v
    x,DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k f
    l DMap k f
    r)

    -- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.
    -- 'alter' can be used to insert, delete, or update a value in a 'Map'.
    -- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
    alter :: forall k f v. GCompare k => (Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    alter :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
    alter Maybe (f v) -> Maybe (f v)
    f k v
    k = k v
    k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = case Maybe (f v) -> Maybe (f v)
    f Maybe (f v)
    forall a. Maybe a
    Nothing of
                   Maybe (f v)
    Nothing -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
                   Just f v
    x  -> k v -> f v -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    k f v
    x

        go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
                   GOrdering v v
    GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
                   GOrdering v v
    GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
                   GOrdering v v
    GEQ -> case Maybe (f v) -> Maybe (f v)
    f (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    f v
    x) of
                           Just f v
    x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    f v
    x' DMap k f
    l DMap k f
    r
                           Maybe (f v)
    Nothing -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k f
    l DMap k f
    r

    -- | Works the same as 'alter' except the new value is returned in some 'Functor' @f@.
    -- In short : @(\v' -> alter (const v') k dm) <$> f (lookup k dm)@
    alterF :: forall k f v g. (GCompare  k, Functor f) => k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k g)
    alterF :: forall {k} (k :: k -> *) (f :: * -> *) (v :: k) (g :: k -> *).
    (GCompare k, Functor f) =>
    k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k g)
    alterF k v
    k Maybe (g v) -> f (Maybe (g v))
    f = DMap k g -> f (DMap k g)
    go
      where
        go :: DMap k g -> f (DMap k g)
        go :: DMap k g -> f (DMap k g)
    go DMap k g
    Tip = DMap k g -> (g v -> DMap k g) -> Maybe (g v) -> DMap k g
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip (k v -> g v -> DMap k g
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k v
    k) (Maybe (g v) -> DMap k g) -> f (Maybe (g v)) -> f (DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe (g v) -> f (Maybe (g v))
    f Maybe (g v)
    forall a. Maybe a
    Nothing

        go (Bin Int
    sx k v
    kx g v
    x DMap k g
    l DMap k g
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
          GOrdering v v
    GLT -> (\DMap k g
    l' -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx g v
    x DMap k g
    l' DMap k g
    r) (DMap k g -> DMap k g) -> f (DMap k g) -> f (DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> DMap k g -> f (DMap k g)
    go DMap k g
    l
          GOrdering v v
    GGT -> (\DMap k g
    r' -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx g v
    x DMap k g
    l DMap k g
    r') (DMap k g -> DMap k g) -> f (DMap k g) -> f (DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> DMap k g -> f (DMap k g)
    go DMap k g
    r
          GOrdering v v
    GEQ -> DMap k g -> (g v -> DMap k g) -> Maybe (g v) -> DMap k g
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k g
    l DMap k g
    r) (\g v
    x' -> Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx g v
    x' DMap k g
    l DMap k g
    r) (Maybe (g v) -> DMap k g) -> f (Maybe (g v)) -> f (DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe (g v) -> f (Maybe (g v))
    f (g v -> Maybe (g v)
    forall a. a -> Maybe a
    Just g v
    g v
    x)

    {--------------------------------------------------------------------
      Indexing
    --------------------------------------------------------------------}

    -- | /O(log n)/. Return the /index/ of a key. The index is a number from
    -- /0/ up to, but not including, the 'size' of the map. Calls 'error' when
    -- the key is not a 'member' of the map.
    findIndex :: GCompare k => k v -> DMap k f -> Int
    findIndex :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    GCompare k =>
    k v -> DMap k f -> Int
    findIndex k v
    k DMap k f
    t
      = case k v -> DMap k f -> Maybe Int
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> Maybe Int
    lookupIndex k v
    k DMap k f
    t of
          Maybe Int
    Nothing  -> [Char] -> Int
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Map.findIndex: element is not in the map"
          Just Int
    idx -> Int
    idx

    -- | /O(log n)/. Lookup the /index/ of a key. The index is a number from
    -- /0/ up to, but not including, the 'size' of the map.
    lookupIndex :: forall k f v. GCompare k => k v -> DMap k f -> Maybe Int
    lookupIndex :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> Maybe Int
    lookupIndex k v
    k = k v
    k k v -> (DMap k f -> Maybe Int) -> DMap k f -> Maybe Int
    forall a b. a -> b -> b
    `seq` Int -> DMap k f -> Maybe Int
    go Int
    0
      where
        go :: Int -> DMap k f -> Maybe Int
        go :: Int -> DMap k f -> Maybe Int
    go !Int
    idx DMap k f
    Tip  = Int
    idx Int -> Maybe Int -> Maybe Int
    forall a b. a -> b -> b
    `seq` Maybe Int
    forall a. Maybe a
    Nothing
        go !Int
    idx (Bin Int
    _ k v
    kx f v
    _ DMap k f
    l DMap k f
    r)
          = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
              GOrdering v v
    GLT -> Int -> DMap k f -> Maybe Int
    go Int
    idx DMap k f
    l
              GOrdering v v
    GGT -> Int -> DMap k f -> Maybe Int
    go (Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) DMap k f
    r
              GOrdering v v
    GEQ -> Int -> Maybe Int
    forall a. a -> Maybe a
    Just (Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l)

    -- | /O(log n)/. Retrieve an element by /index/. Calls 'error' when an
    -- invalid index is used.
    elemAt :: Int -> DMap k f -> DSum k f
    elemAt :: forall {k} (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DSum k f
    elemAt Int
    _ DMap k f
    Tip = [Char] -> DSum k f
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Map.elemAt: index out of range"
    elemAt Int
    i (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)
      = case Int -> Int -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Int
    i Int
    sizeL of
          Ordering
    LT -> Int -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DSum k f
    elemAt Int
    i DMap k f
    l
          Ordering
    GT -> Int -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DSum k f
    elemAt (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    sizeLInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) DMap k f
    r
          Ordering
    EQ -> k v
    kx k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x
      where
        sizeL :: Int
    sizeL = DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l

    -- | /O(log n)/. Update the element at /index/. Does nothing when an
    -- invalid index is used.
    updateAt :: (forall v. k v -> f v -> Maybe (f v)) -> Int -> DMap k f -> DMap k f
    updateAt :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> Maybe (f v))
    -> Int -> DMap k f -> DMap k f
    updateAt forall (v :: k). k v -> f v -> Maybe (f v)
    f Int
    i0 DMap k f
    t = Int
    i0 Int -> DMap k f -> DMap k f
    forall a b. a -> b -> b
    `seq` Int -> DMap k f -> DMap k f
    go Int
    i0 DMap k f
    t
     where
        go :: Int -> DMap k f -> DMap k f
    go Int
    _ DMap k f
    Tip  = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go Int
    i (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case Int -> Int -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Int
    i Int
    sizeL of
          Ordering
    LT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (Int -> DMap k f -> DMap k f
    go Int
    i DMap k f
    l) DMap k f
    r
          Ordering
    GT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (Int -> DMap k f -> DMap k f
    go (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    sizeLInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) DMap k f
    r)
          Ordering
    EQ -> case k v -> f v -> Maybe (f v)
    forall (v :: k). k v -> f v -> Maybe (f v)
    f k v
    kx f v
    x of
                  Just f v
    x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x' DMap k f
    l DMap k f
    r
                  Maybe (f v)
    Nothing -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    glue DMap k f
    l DMap k f
    r
          where
            sizeL :: Int
    sizeL = DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l

    -- | /O(log n)/. Delete the element at /index/.
    -- Defined as (@'deleteAt' i map = 'updateAt' (\k x -> 'Nothing') i map@).
    deleteAt :: Int -> DMap k f -> DMap k f
    deleteAt :: forall {k} (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DMap k f
    deleteAt Int
    i DMap k f
    m
      = (forall (v :: k). k v -> f v -> Maybe (f v))
    -> Int -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> Maybe (f v))
    -> Int -> DMap k f -> DMap k f
    updateAt (\k v
    _ f v
    _ -> Maybe (f v)
    forall a. Maybe a
    Nothing) Int
    i DMap k f
    m

    {--------------------------------------------------------------------
      Minimal, Maximal
    --------------------------------------------------------------------}

    -- | /O(log n)/. The minimal key of the map. Calls 'error' is the map is empty.
    findMin :: DMap k f -> DSum k f
    findMin :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DSum k f
    findMin DMap k f
    m = case DMap k f -> Maybe (DSum k f)
    forall {k} (k :: k -> *) (f :: k -> *).
    DMap k f -> Maybe (DSum k f)
    lookupMin DMap k f
    m of
      Just DSum k f
    x -> DSum k f
    x
      Maybe (DSum k f)
    Nothing -> [Char] -> DSum k f
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Map.findMin: empty map has no minimal element"

    lookupMin :: DMap k f -> Maybe (DSum k f)
    lookupMin :: forall {k} (k :: k -> *) (f :: k -> *).
    DMap k f -> Maybe (DSum k f)
    lookupMin DMap k f
    m = case DMap k f
    m of
          DMap k f
    Tip -> Maybe (DSum k f)
    forall a. Maybe a
    Nothing
          Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    _ -> DSum k f -> Maybe (DSum k f)
    forall a. a -> Maybe a
    Just (DSum k f -> Maybe (DSum k f)) -> DSum k f -> Maybe (DSum k f)
    forall a b. (a -> b) -> a -> b
    $! k v -> f v -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    l
      where
        go :: k v -> f v -> DMap k f -> DSum k f
        go :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    Tip = k v
    kx k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x
        go k v
    _  f v
    _ (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    _) = k v -> f v -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    l

    -- | /O(log n)/. The maximal key of the map. Calls 'error' is the map is empty.
    findMax :: DMap k f -> DSum k f
    findMax :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DSum k f
    findMax DMap k f
    m = case DMap k f -> Maybe (DSum k f)
    forall {k} (k :: k -> *) (f :: k -> *).
    DMap k f -> Maybe (DSum k f)
    lookupMax DMap k f
    m of
      Just DSum k f
    x -> DSum k f
    x
      Maybe (DSum k f)
    Nothing -> [Char] -> DSum k f
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Map.findMax: empty map has no maximal element"

    lookupMax :: DMap k f -> Maybe (DSum k f)
    lookupMax :: forall {k} (k :: k -> *) (f :: k -> *).
    DMap k f -> Maybe (DSum k f)
    lookupMax DMap k f
    m = case DMap k f
    m of
          DMap k f
    Tip -> Maybe (DSum k f)
    forall a. Maybe a
    Nothing
          Bin Int
    _ k v
    kx f v
    x DMap k f
    _ DMap k f
    r -> DSum k f -> Maybe (DSum k f)
    forall a. a -> Maybe a
    Just (DSum k f -> Maybe (DSum k f)) -> DSum k f -> Maybe (DSum k f)
    forall a b. (a -> b) -> a -> b
    $! k v -> f v -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    r
      where
        go :: k v -> f v -> DMap k f -> DSum k f
        go :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    Tip = k v
    kx k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x
        go k v
    _  f v
    _ (Bin Int
    _ k v
    kx f v
    x DMap k f
    _ DMap k f
    r) = k v -> f v -> DMap k f -> DSum k f
    forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
    k v -> f v -> DMap k f -> DSum k f
    go k v
    kx f v
    x DMap k f
    r

    -- | /O(log n)/. Delete the minimal key. Returns an empty map if the map is empty.
    deleteMin :: DMap k f -> DMap k f
    deleteMin :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
    deleteMin (Bin Int
    _ k v
    _  f v
    _ DMap k f
    Tip DMap k f
    r)  = DMap k f
    r
    deleteMin (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
    deleteMin DMap k f
    l) DMap k f
    r
    deleteMin DMap k f
    Tip                 = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip

    -- | /O(log n)/. Delete the maximal key. Returns an empty map if the map is empty.
    deleteMax :: DMap k f -> DMap k f
    deleteMax :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
    deleteMax (Bin Int
    _ k v
    _  f v
    _ DMap k f
    l DMap k f
    Tip)  = DMap k f
    l
    deleteMax (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
    deleteMax DMap k f
    r)
    deleteMax DMap k f
    Tip                 = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip

    -- | /O(log n)/. Update the value at the minimal key.
    updateMinWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> DMap k f -> DMap k f
    updateMinWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> Maybe (f v))
    -> DMap k f -> DMap k f
    updateMinWithKey forall (v :: k). k v -> f v -> Maybe (f v)
    f = DMap k f -> DMap k f
    go
     where
        go :: DMap k f -> DMap k f
    go (Bin Int
    sx k v
    kx f v
    x DMap k f
    Tip DMap k f
    r) = case k v -> f v -> Maybe (f v)
    forall (v :: k). k v -> f v -> Maybe (f v)
    f k v
    kx f v
    x of
                                      Maybe (f v)
    Nothing -> DMap k f
    r
                                      Just f v
    x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x' DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip DMap k f
    r
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x (DMap k f -> DMap k f
    go DMap k f
    l) DMap k f
    r
        go DMap k f
    Tip                 = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip

    -- | /O(log n)/. Update the value at the maximal key.
    updateMaxWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> DMap k f -> DMap k f
    updateMaxWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> Maybe (f v))
    -> DMap k f -> DMap k f
    updateMaxWithKey forall (v :: k). k v -> f v -> Maybe (f v)
    f = DMap k f -> DMap k f
    go
     where
        go :: DMap k f -> DMap k f
    go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    Tip) = case k v -> f v -> Maybe (f v)
    forall (v :: k). k v -> f v -> Maybe (f v)
    f k v
    kx f v
    x of
                                  Maybe (f v)
    Nothing -> DMap k f
    l
                                  Just f v
    x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx f v
    x' DMap k f
    l DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    balance k v
    kx f v
    x DMap k f
    l (DMap k f -> DMap k f
    go DMap k f
    r)
        go DMap k f
    Tip                 = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip

    {--------------------------------------------------------------------
      Union.
    --------------------------------------------------------------------}

    -- | The union of a list of maps:
    --   (@'unions' == 'Prelude.foldl' 'union' 'empty'@).
    unions :: GCompare k => [DMap k f] -> DMap k f
    unions :: forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    [DMap k f] -> DMap k f
    unions [DMap k f]
    ts
      = (DMap k f -> DMap k f -> DMap k f)
    -> DMap k f -> [DMap k f] -> DMap k f
    forall a b. (a -> b -> a) -> a -> [b] -> a
    foldlStrict DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    union DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    empty [DMap k f]
    ts

    -- | The union of a list of maps, with a combining operation:
    --   (@'unionsWithKey' f == 'Prelude.foldl' ('unionWithKey' f) 'empty'@).
    unionsWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [DMap k f] -> DMap k f
    unionsWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DMap k f] -> DMap k f
    unionsWithKey forall (v :: k). k v -> f v -> f v -> f v
    f [DMap k f]
    ts
      = (DMap k f -> DMap k f -> DMap k f)
    -> DMap k f -> [DMap k f] -> DMap k f
    forall a b. (a -> b -> a) -> a -> [b] -> a
    foldlStrict ((forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    unionWithKey k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f) DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    empty [DMap k f]
    ts

    -- | /O(m*log(n\/m + 1)), m <= n/.
    -- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@.
    -- It prefers @t1@ when duplicate keys are encountered,
    -- i.e. (@'union' == 'unionWith' 'const'@).
    union :: GCompare k => DMap k f -> DMap k f -> DMap k f
    union :: forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    union DMap k f
    t1 DMap k f
    Tip  = DMap k f
    t1
    union DMap k f
    t1 (Bin Int
    _ k v
    kx f v
    x DMap k f
    Tip DMap k f
    Tip) = k v -> f v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> f v -> DMap k f -> DMap k f
    insertR k v
    kx f v
    x DMap k f
    t1
    union DMap k f
    Tip DMap k f
    t2  = DMap k f
    t2
    union (Bin Int
    _ k v
    kx f v
    x DMap k f
    Tip DMap k f
    Tip) DMap k f
    t2 = k v -> f v -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> f v -> DMap k f -> DMap k f
    insert k v
    kx f v
    x DMap k f
    t2
    union t1 :: DMap k f
    t1@(Bin Int
    _ k v
    k1 f v
    x1 DMap k f
    l1 DMap k f
    r1) DMap k f
    t2 = case k v -> DMap k f -> (DMap k f, DMap k f)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, DMap k f)
    split k v
    k1 DMap k f
    t2 of
      (DMap k f
    l2, DMap k f
    r2)
        | DMap k f
    l1 DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    l1l2 Bool -> Bool -> Bool
    && DMap k f
    r1 DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    r1r2 -> DMap k f
    t1
        | Bool
    otherwise -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 f v
    x1 DMap k f
    l1l2 DMap k f
    r1r2
        where !l1l2 :: DMap k f
    l1l2 = DMap k f
    l1 DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    `union` DMap k f
    l2
              !r1r2 :: DMap k f
    r1r2 = DMap k f
    r1 DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    `union` DMap k f
    r2

    {--------------------------------------------------------------------
      Union with a combining function
    --------------------------------------------------------------------}

    -- | /O(n+m)/.
    -- Union with a combining function.
    unionWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> DMap k f -> DMap k f -> DMap k f
    unionWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    unionWithKey forall (v :: k). k v -> f v -> f v -> f v
    _ DMap k f
    t1 DMap k f
    Tip  = DMap k f
    t1
    unionWithKey forall (v :: k). k v -> f v -> f v -> f v
    _ DMap k f
    Tip DMap k f
    t2  = DMap k f
    t2
    unionWithKey forall (v :: k). k v -> f v -> f v -> f v
    f (Bin Int
    _ k v
    k1 f v
    x1 DMap k f
    l1 DMap k f
    r1) DMap k f
    t2 = case k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    splitLookup k v
    k1 DMap k f
    t2 of
      (DMap k f
    l2, Maybe (f v)
    mx2, DMap k f
    r2) -> case Maybe (f v)
    mx2 of
          Maybe (f v)
    Nothing -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 f v
    x1 DMap k f
    l1l2 DMap k f
    r1r2
          Just f v
    x2 -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 (k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f k v
    k1 f v
    x1 f v
    x2) DMap k f
    l1l2 DMap k f
    r1r2
        where !l1l2 :: DMap k f
    l1l2 = (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    unionWithKey k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f DMap k f
    l1 DMap k f
    l2
              !r1r2 :: DMap k f
    r1r2 = (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DMap k f -> DMap k f
    unionWithKey k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f DMap k f
    r1 DMap k f
    r2

    {--------------------------------------------------------------------
      Difference
    --------------------------------------------------------------------}

    -- | /O(m * log (n\/m + 1)), m <= n/. Difference of two maps.
    -- Return elements of the first map not existing in the second map.
    difference :: GCompare k => DMap k f -> DMap k g -> DMap k f
    difference :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    DMap k f -> DMap k g -> DMap k f
    difference DMap k f
    Tip DMap k g
    _   = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    difference DMap k f
    t1 DMap k g
    Tip  = DMap k f
    t1
    difference DMap k f
    t1 (Bin Int
    _ k v
    k2 g v
    _x2 DMap k g
    l2 DMap k g
    r2) = case k v -> DMap k f -> (DMap k f, DMap k f)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, DMap k f)
    split k v
    k2 DMap k f
    t1 of
      (DMap k f
    l1, DMap k f
    r1)
        | DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t1 Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l1l2 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    r1r2 -> DMap k f
    t1
        | Bool
    otherwise -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l1l2 DMap k f
    r1r2
        where
          !l1l2 :: DMap k f
    l1l2 = DMap k f
    l1 DMap k f -> DMap k g -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    DMap k f -> DMap k g -> DMap k f
    `difference` DMap k g
    l2
          !r1r2 :: DMap k f
    r1r2 = DMap k f
    r1 DMap k f -> DMap k g -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    DMap k f -> DMap k g -> DMap k f
    `difference` DMap k g
    r2

    -- | /O(n+m)/. Difference with a combining function. When two equal keys are
    -- encountered, the combining function is applied to the key and both values.
    -- If it returns 'Nothing', the element is discarded (proper set difference). If
    -- it returns (@'Just' y@), the element is updated with a new value @y@.
    differenceWithKey :: GCompare k => (forall v. k v -> f v -> g v -> Maybe (f v)) -> DMap k f -> DMap k g -> DMap k f
    differenceWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
    -> DMap k f -> DMap k g -> DMap k f
    differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    _ DMap k f
    Tip DMap k g
    _   = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    _ DMap k f
    t1 DMap k g
    Tip  = DMap k f
    t1
    differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    f (Bin Int
    _ k v
    k1 f v
    x1 DMap k f
    l1 DMap k f
    r1) DMap k g
    t2 = case k v -> DMap k g -> (DMap k g, Maybe (g v), DMap k g)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    splitLookup k v
    k1 DMap k g
    t2 of
      (DMap k g
    l2, Maybe (g v)
    mx2, DMap k g
    r2) -> case Maybe (g v)
    mx2 of
          Maybe (g v)
    Nothing -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 f v
    x1 DMap k f
    l1l2 DMap k f
    r1r2
          Just g v
    x2 -> case k v -> f v -> g v -> Maybe (f v)
    forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    f k v
    k1 f v
    x1 g v
    x2 of
            Maybe (f v)
    Nothing -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l1l2 DMap k f
    r1r2
            Just f v
    x1x2 -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 f v
    x1x2 DMap k f
    l1l2 DMap k f
    r1r2
        where !l1l2 :: DMap k f
    l1l2 = (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
    -> DMap k f -> DMap k g -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
    -> DMap k f -> DMap k g -> DMap k f
    differenceWithKey k v -> f v -> g v -> Maybe (f v)
    forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    f DMap k f
    l1 DMap k g
    l2
              !r1r2 :: DMap k f
    r1r2 = (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
    -> DMap k f -> DMap k g -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
    -> DMap k f -> DMap k g -> DMap k f
    differenceWithKey k v -> f v -> g v -> Maybe (f v)
    forall (v :: k). k v -> f v -> g v -> Maybe (f v)
    f DMap k f
    r1 DMap k g
    r2

    {--------------------------------------------------------------------
      Intersection
    --------------------------------------------------------------------}

    -- | /O(m * log (n\/m + 1), m <= n/. Intersection of two maps.
    -- Return data in the first map for the keys existing in both maps.
    -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@).
    intersection :: GCompare k => DMap k f -> DMap k f -> DMap k f
    intersection :: forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    intersection DMap k f
    Tip DMap k f
    _ = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    intersection DMap k f
    _ DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    intersection t1 :: DMap k f
    t1@(Bin Int
    s1 k v
    k1 f v
    x1 DMap k f
    l1 DMap k f
    r1) DMap k f
    t2 =
      let !(DMap k f
    l2, Bool
    found, DMap k f
    r2) = k v -> DMap k f -> (DMap k f, Bool, DMap k f)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Bool, DMap k f)
    splitMember k v
    k1 DMap k f
    t2
          !l1l2 :: DMap k f
    l1l2 = DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    intersection DMap k f
    l1 DMap k f
    l2
          !r1r2 :: DMap k f
    r1r2 = DMap k f -> DMap k f -> DMap k f
    forall k (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DMap k f -> DMap k f
    intersection DMap k f
    r1 DMap k f
    r2
      in if Bool
    found
         then if DMap k f
    l1l2 DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    l1 Bool -> Bool -> Bool
    && DMap k f
    r1r2 DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    r1
              then DMap k f
    t1
              else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 f v
    x1 DMap k f
    l1l2 DMap k f
    r1r2
         else DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l1l2 DMap k f
    r1r2

    -- | /O(m * log (n\/m + 1), m <= n/. Intersection with a combining function.
    intersectionWithKey :: GCompare k => (forall v. k v -> f v -> g v -> h v) -> DMap k f -> DMap k g -> DMap k h
    intersectionWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> h v)
    -> DMap k f -> DMap k g -> DMap k h
    intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
    _ DMap k f
    Tip DMap k g
    _ = DMap k h
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
    _ DMap k f
    _ DMap k g
    Tip = DMap k h
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
    f (Bin Int
    s1 k v
    k1 f v
    x1 DMap k f
    l1 DMap k f
    r1) DMap k g
    t2 =
      let !(DMap k g
    l2, Maybe (g v)
    found, DMap k g
    r2) = k v -> DMap k g -> (DMap k g, Maybe (g v), DMap k g)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    splitLookup k v
    k1 DMap k g
    t2
          !l1l2 :: DMap k h
    l1l2 = (forall (v :: k). k v -> f v -> g v -> h v)
    -> DMap k f -> DMap k g -> DMap k h
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> h v)
    -> DMap k f -> DMap k g -> DMap k h
    intersectionWithKey k v -> f v -> g v -> h v
    forall (v :: k). k v -> f v -> g v -> h v
    f DMap k f
    l1 DMap k g
    l2
          !r1r2 :: DMap k h
    r1r2 = (forall (v :: k). k v -> f v -> g v -> h v)
    -> DMap k f -> DMap k g -> DMap k h
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> g v -> h v)
    -> DMap k f -> DMap k g -> DMap k h
    intersectionWithKey k v -> f v -> g v -> h v
    forall (v :: k). k v -> f v -> g v -> h v
    f DMap k f
    r1 DMap k g
    r2
      in case Maybe (g v)
    found of
           Maybe (g v)
    Nothing -> DMap k h -> DMap k h -> DMap k h
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k h
    l1l2 DMap k h
    r1r2
           Just g v
    x2 -> k v -> h v -> DMap k h -> DMap k h -> DMap k h
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    k1 (k v -> f v -> g v -> h v
    forall (v :: k). k v -> f v -> g v -> h v
    f k v
    k1 f v
    x1 g v
    x2) DMap k h
    l1l2 DMap k h
    r1r2

    {--------------------------------------------------------------------
      Submap
    --------------------------------------------------------------------}
    -- | /O(n+m)/.
    -- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' 'eqTagged')@).
    --
    isSubmapOf
      :: forall k f
      .  (GCompare k, Has' Eq k f)
      => DMap k f -> DMap k f -> Bool
    isSubmapOf :: forall {k} (k :: k -> *) (f :: k -> *).
    (GCompare k, Has' Eq k f) =>
    DMap k f -> DMap k f -> Bool
    isSubmapOf DMap k f
    m1 DMap k f
    m2 = (forall (v :: k). k v -> k v -> f v -> f v -> Bool)
    -> DMap k f -> DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    isSubmapOfBy (\k v
    k k v
    _ f v
    x0 f v
    x1 -> forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
           (f :: k' -> *) (a :: k') r.
    Has' c f g =>
    f a -> (c (g a) => r) -> r
    forall (c :: * -> Constraint) (g :: k -> *) (f :: k -> *) (a :: k)
           r.
    Has' c f g =>
    f a -> (c (g a) => r) -> r
    has' @Eq @f k v
    k (f v
    x0 f v -> f v -> Bool
    forall a. Eq a => a -> a -> Bool
    == f v
    x1)) DMap k f
    m1 DMap k f
    m2

    {- | /O(n+m)/.
     The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if
     all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when
     applied to their respective keys and values.
    -}
    isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
    isSubmapOfBy :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    isSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    t1 DMap k g
    t2
      = (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t1 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= DMap k g -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k g
    t2) Bool -> Bool -> Bool
    && ((forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    submap' k v -> k v -> f v -> g v -> Bool
    forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    t1 DMap k g
    t2)

    submap' :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
    submap' :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
    _ DMap k f
    Tip DMap k g
    _ = Bool
    True
    submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
    _ DMap k f
    _ DMap k g
    Tip = Bool
    False
    submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) DMap k g
    t
      = case Maybe (k v, g v)
    found of
          Maybe (k v, g v)
    Nothing -> Bool
    False
          Just (k v
    ky, g v
    y)  -> k v -> k v -> f v -> g v -> Bool
    forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f k v
    kx k v
    ky f v
    x g v
    y Bool -> Bool -> Bool
    && (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    submap' k v -> k v -> f v -> g v -> Bool
    forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    l DMap k g
    lt Bool -> Bool -> Bool
    && (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    submap' k v -> k v -> f v -> g v -> Bool
    forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    r DMap k g
    gt
      where
        (DMap k g
    lt,Maybe (k v, g v)
    found,DMap k g
    gt) = k v -> DMap k g -> (DMap k g, Maybe (k v, g v), DMap k g)
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
    splitLookupWithKey k v
    kx DMap k g
    t

    -- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
    -- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' 'eqTagged'@).
    isProperSubmapOf
      :: forall k f
      .  (GCompare k, Has' Eq k f)
      => DMap k f -> DMap k f -> Bool
    isProperSubmapOf :: forall {k} (k :: k -> *) (f :: k -> *).
    (GCompare k, Has' Eq k f) =>
    DMap k f -> DMap k f -> Bool
    isProperSubmapOf DMap k f
    m1 DMap k f
    m2
      = (forall (v :: k). k v -> k v -> f v -> f v -> Bool)
    -> DMap k f -> DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    isProperSubmapOfBy (\k v
    k k v
    _ f v
    x0 f v
    x1 -> forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
           (f :: k' -> *) (a :: k') r.
    Has' c f g =>
    f a -> (c (g a) => r) -> r
    forall (c :: * -> Constraint) (g :: k -> *) (f :: k -> *) (a :: k)
           r.
    Has' c f g =>
    f a -> (c (g a) => r) -> r
    has' @Eq @f k v
    k (f v
    x0 f v -> f v -> Bool
    forall a. Eq a => a -> a -> Bool
    == f v
    x1)) DMap k f
    m1 DMap k f
    m2

    {- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
     The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when
     @m1@ and @m2@ are not equal,
     all keys in @m1@ are in @m2@, and when @f@ returns 'True' when
     applied to their respective keys and values.
    -}
    isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
    isProperSubmapOfBy :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    isProperSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    t1 DMap k g
    t2
      = (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t1 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < DMap k g -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k g
    t2) Bool -> Bool -> Bool
    && ((forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
    -> DMap k f -> DMap k g -> Bool
    submap' k v -> k v -> f v -> g v -> Bool
    forall (v :: k). k v -> k v -> f v -> g v -> Bool
    f DMap k f
    t1 DMap k g
    t2)

    {--------------------------------------------------------------------
      Filter and partition
    --------------------------------------------------------------------}

    -- | /O(n)/. Filter all keys\/values that satisfy the predicate.
    filterWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> DMap k f
    filterWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool) -> DMap k f -> DMap k f
    filterWithKey forall (v :: k). k v -> f v -> Bool
    p = DMap k f -> DMap k f
    go
      where
        go :: DMap k f -> DMap k f
    go DMap k f
    Tip = DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go t :: DMap k f
    t@(Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)
          | k v -> f v -> Bool
    forall (v :: k). k v -> f v -> Bool
    p k v
    kx f v
    x    = if DMap k f
    l' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    l Bool -> Bool -> Bool
    && DMap k f
    r' DMap k f -> DMap k f -> Bool
    forall a. a -> a -> Bool
    `ptrEq` DMap k f
    r
                        then DMap k f
    t
                        else k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l' DMap k f
    r'
          | Bool
    otherwise = DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l' DMap k f
    r'
          where !l' :: DMap k f
    l' = DMap k f -> DMap k f
    go DMap k f
    l
                !r' :: DMap k f
    r' = DMap k f -> DMap k f
    go DMap k f
    r

    -- | /O(n)/. Partition the map according to a predicate. The first
    -- map contains all elements that satisfy the predicate, the second all
    -- elements that fail the predicate. See also 'split'.
    partitionWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> (DMap k f, DMap k f)
    partitionWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> (DMap k f, DMap k f)
    partitionWithKey forall (v :: k). k v -> f v -> Bool
    p0 DMap k f
    m0 = (DMap k f :*: DMap k f) -> (DMap k f, DMap k f)
    forall a b. (a :*: b) -> (a, b)
    toPair ((forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    go k v -> f v -> Bool
    forall (v :: k). k v -> f v -> Bool
    p0 DMap k f
    m0)
      where
        go :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> (DMap k f :*: DMap k f)
        go :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    go forall (v :: k). k v -> f v -> Bool
    _ DMap k f
    Tip = (DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
        go forall (v :: k). k v -> f v -> Bool
    p (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r)
          | k v -> f v -> Bool
    forall (v :: k). k v -> f v -> Bool
    p k v
    kx f v
    x    = (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l1 DMap k f
    r1 DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l2 DMap k f
    r2)
          | Bool
    otherwise = (DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k f
    l1 DMap k f
    r1 DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l2 DMap k f
    r2)
          where
            (DMap k f
    l1 :*: DMap k f
    l2) = (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    go k v -> f v -> Bool
    forall (v :: k). k v -> f v -> Bool
    p DMap k f
    l
            (DMap k f
    r1 :*: DMap k f
    r2) = (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Bool)
    -> DMap k f -> DMap k f :*: DMap k f
    go k v -> f v -> Bool
    forall (v :: k). k v -> f v -> Bool
    p DMap k f
    r

    -- | /O(n)/. Map values and collect the 'Just' results.
    mapMaybe :: GCompare k => (forall v. f v -> Maybe (g v)) -> DMap k f -> DMap k g
    mapMaybe :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). f v -> Maybe (g v)) -> DMap k f -> DMap k g
    mapMaybe forall (v :: k). f v -> Maybe (g v)
    f = (forall (v :: k). k v -> f v -> Maybe (g v))
    -> DMap k f -> DMap k g
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Maybe (g v))
    -> DMap k f -> DMap k g
    mapMaybeWithKey ((f v -> Maybe (g v)) -> k v -> f v -> Maybe (g v)
    forall a b. a -> b -> a
    const f v -> Maybe (g v)
    forall (v :: k). f v -> Maybe (g v)
    f)

    -- | /O(n)/. Map keys\/values and collect the 'Just' results.
    mapMaybeWithKey :: GCompare k => (forall v. k v -> f v -> Maybe (g v)) -> DMap k f -> DMap k g
    mapMaybeWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Maybe (g v))
    -> DMap k f -> DMap k g
    mapMaybeWithKey forall (v :: k). k v -> f v -> Maybe (g v)
    f = DMap k f -> DMap k g
    go
      where
        go :: DMap k f -> DMap k g
    go DMap k f
    Tip = DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> f v -> Maybe (g v)
    forall (v :: k). k v -> f v -> Maybe (g v)
    f k v
    kx f v
    x of
            Just g v
    y  -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx g v
    y (DMap k f -> DMap k g
    go DMap k f
    l) (DMap k f -> DMap k g
    go DMap k f
    r)
            Maybe (g v)
    Nothing -> DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge (DMap k f -> DMap k g
    go DMap k f
    l) (DMap k f -> DMap k g
    go DMap k f
    r)

    -- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
    mapEitherWithKey :: GCompare k =>
      (forall v. k v -> f v -> Either (g v) (h v)) -> DMap k f -> (DMap k g, DMap k h)
    mapEitherWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> (DMap k g, DMap k h)
    mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
    f0 = (DMap k g :*: DMap k h) -> (DMap k g, DMap k h)
    forall a b. (a :*: b) -> (a, b)
    toPair ((DMap k g :*: DMap k h) -> (DMap k g, DMap k h))
    -> (DMap k f -> DMap k g :*: DMap k h)
    -> DMap k f
    -> (DMap k g, DMap k h)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> DMap k g :*: DMap k h
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> DMap k g :*: DMap k h
    go k v -> f v -> Either (g v) (h v)
    forall (v :: k). k v -> f v -> Either (g v) (h v)
    f0
      where
        go :: GCompare k
           => (forall v. k v -> f v -> Either (g v) (h v))
           -> DMap k f -> (DMap k g :*: DMap k h)
        go :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> DMap k g :*: DMap k h
    go forall (v :: k). k v -> f v -> Either (g v) (h v)
    _ DMap k f
    Tip = (DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip DMap k g -> DMap k h -> DMap k g :*: DMap k h
    forall a b. a -> b -> a :*: b
    :*: DMap k h
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
        go forall (v :: k). k v -> f v -> Either (g v) (h v)
    f (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> f v -> Either (g v) (h v)
    forall (v :: k). k v -> f v -> Either (g v) (h v)
    f k v
    kx f v
    x of
          Left g v
    y  -> (k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx g v
    y DMap k g
    l1 DMap k g
    r1 DMap k g -> DMap k h -> DMap k g :*: DMap k h
    forall a b. a -> b -> a :*: b
    :*: DMap k h -> DMap k h -> DMap k h
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k h
    l2 DMap k h
    r2)
          Right h v
    z -> (DMap k g -> DMap k g -> DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
    DMap k2 f -> DMap k2 f -> DMap k2 f
    merge DMap k g
    l1 DMap k g
    r1 DMap k g -> DMap k h -> DMap k g :*: DMap k h
    forall a b. a -> b -> a :*: b
    :*: k v -> h v -> DMap k h -> DMap k h -> DMap k h
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx h v
    z DMap k h
    l2 DMap k h
    r2)
          where
            (DMap k g
    l1,DMap k h
    l2) = (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> (DMap k g, DMap k h)
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> (DMap k g, DMap k h)
    mapEitherWithKey k v -> f v -> Either (g v) (h v)
    forall (v :: k). k v -> f v -> Either (g v) (h v)
    f DMap k f
    l
            (DMap k g
    r1,DMap k h
    r2) = (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> (DMap k g, DMap k h)
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> Either (g v) (h v))
    -> DMap k f -> (DMap k g, DMap k h)
    mapEitherWithKey k v -> f v -> Either (g v) (h v)
    forall (v :: k). k v -> f v -> Either (g v) (h v)
    f DMap k f
    r

    {--------------------------------------------------------------------
      Mapping
    --------------------------------------------------------------------}

    -- | /O(n)/. Map a function over all values in the map.
    map :: (forall v. f v -> g v) -> DMap k f -> DMap k g
    map :: forall {k} (f :: k -> *) (g :: k -> *) (k :: k -> *).
    (forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
    map forall (v :: k). f v -> g v
    f = DMap k f -> DMap k g
    go
      where
        go :: DMap k f -> DMap k g
    go DMap k f
    Tip = DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) = Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx (f v -> g v
    forall (v :: k). f v -> g v
    f f v
    x) (DMap k f -> DMap k g
    go DMap k f
    l) (DMap k f -> DMap k g
    go DMap k f
    r)

    -- | /O(n)/.
    -- @'ffor' == 'flip' 'map'@ except we cannot actually use
    -- 'flip' because of the lack of impredicative types.
    ffor :: DMap k f -> (forall v. f v -> g v) -> DMap k g
    ffor :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    DMap k f -> (forall (v :: k). f v -> g v) -> DMap k g
    ffor DMap k f
    m forall (v :: k). f v -> g v
    f = (forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
    forall {k} (f :: k -> *) (g :: k -> *) (k :: k -> *).
    (forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
    map f v -> g v
    forall (v :: k). f v -> g v
    f DMap k f
    m

    -- | /O(n)/. Map a function over all values in the map.
    mapWithKey :: (forall v. k v -> f v -> g v) -> DMap k f -> DMap k g
    mapWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    (forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
    mapWithKey forall (v :: k). k v -> f v -> g v
    f = DMap k f -> DMap k g
    go
      where
        go :: DMap k f -> DMap k g
    go DMap k f
    Tip = DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) = Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx (k v -> f v -> g v
    forall (v :: k). k v -> f v -> g v
    f k v
    kx f v
    x) (DMap k f -> DMap k g
    go DMap k f
    l) (DMap k f -> DMap k g
    go DMap k f
    r)

    -- | /O(n)/.
    -- @'fforWithKey' == 'flip' 'mapWithKey'@ except we cannot actually use
    -- 'flip' because of the lack of impredicative types.
    fforWithKey :: DMap k f -> (forall v. k v -> f v -> g v) -> DMap k g
    fforWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    DMap k f -> (forall (v :: k). k v -> f v -> g v) -> DMap k g
    fforWithKey DMap k f
    m forall (v :: k). k v -> f v -> g v
    f = (forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
    forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
    (forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
    mapWithKey k v -> f v -> g v
    forall (v :: k). k v -> f v -> g v
    f DMap k f
    m

    -- | /O(n)/.
    -- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
    -- That is, behaves exactly like a regular 'traverse' except that the traversing
    -- function also has access to the key associated with a value.
    traverseWithKey_ :: Applicative t => (forall v. k v -> f v -> t ()) -> DMap k f -> t ()
    traverseWithKey_ :: forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *).
    Applicative t =>
    (forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
    traverseWithKey_ forall (v :: k). k v -> f v -> t ()
    f = DMap k f -> t ()
    go
      where
        go :: DMap k f -> t ()
    go DMap k f
    Tip = () -> t ()
    forall a. a -> t a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ()
        go (Bin Int
    1 k v
    k f v
    v DMap k f
    _ DMap k f
    _) = k v -> f v -> t ()
    forall (v :: k). k v -> f v -> t ()
    f k v
    k f v
    v
        go (Bin Int
    s k v
    k f v
    v DMap k f
    l DMap k f
    r) = DMap k f -> t ()
    go DMap k f
    l t () -> t () -> t ()
    forall a b. t a -> t b -> t b
    forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
    *> k v -> f v -> t ()
    forall (v :: k). k v -> f v -> t ()
    f k v
    k f v
    v t () -> t () -> t ()
    forall a b. t a -> t b -> t b
    forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
    *> DMap k f -> t ()
    go DMap k f
    r

    -- | /O(n)/.
    -- @'forWithKey' == 'flip' 'traverseWithKey'@ except we cannot actually use
    -- 'flip' because of the lack of impredicative types.
    forWithKey_ :: Applicative t => DMap k f -> (forall v. k v -> f v -> t ()) -> t ()
    forWithKey_ :: forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *).
    Applicative t =>
    DMap k f -> (forall (v :: k). k v -> f v -> t ()) -> t ()
    forWithKey_ DMap k f
    m forall (v :: k). k v -> f v -> t ()
    f = (forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
    forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *).
    Applicative t =>
    (forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
    traverseWithKey_ k v -> f v -> t ()
    forall (v :: k). k v -> f v -> t ()
    f DMap k f
    m

    -- | /O(n)/.
    -- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
    -- That is, behaves exactly like a regular 'traverse' except that the traversing
    -- function also has access to the key associated with a value.
    traverseWithKey :: Applicative t => (forall v. k v -> f v -> t (g v)) -> DMap k f -> t (DMap k g)
    traverseWithKey :: forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *) (g :: k -> *).
    Applicative t =>
    (forall (v :: k). k v -> f v -> t (g v))
    -> DMap k f -> t (DMap k g)
    traverseWithKey forall (v :: k). k v -> f v -> t (g v)
    f = DMap k f -> t (DMap k g)
    go
      where
        go :: DMap k f -> t (DMap k g)
    go DMap k f
    Tip = DMap k g -> t (DMap k g)
    forall a. a -> t a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    1 k v
    k f v
    v DMap k f
    _ DMap k f
    _) = (\g v
    v' -> Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    1 k v
    k g v
    v' DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip) (g v -> DMap k g) -> t (g v) -> t (DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> k v -> f v -> t (g v)
    forall (v :: k). k v -> f v -> t (g v)
    f k v
    k f v
    v
        go (Bin Int
    s k v
    k f v
    v DMap k f
    l DMap k f
    r) = (g v -> DMap k g -> DMap k g -> DMap k g)
    -> DMap k g -> g v -> DMap k g -> DMap k g
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    s k v
    k) (DMap k g -> g v -> DMap k g -> DMap k g)
    -> t (DMap k g) -> t (g v -> DMap k g -> DMap k g)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> DMap k f -> t (DMap k g)
    go DMap k f
    l t (g v -> DMap k g -> DMap k g)
    -> t (g v) -> t (DMap k g -> DMap k g)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> k v -> f v -> t (g v)
    forall (v :: k). k v -> f v -> t (g v)
    f k v
    k f v
    v t (DMap k g -> DMap k g) -> t (DMap k g) -> t (DMap k g)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> DMap k f -> t (DMap k g)
    go DMap k f
    r

    -- | /O(n)/.
    -- @'forWithKey' == 'flip' 'traverseWithKey'@ except we cannot actually use
    -- 'flip' because of the lack of impredicative types.
    forWithKey :: Applicative t => DMap k f -> (forall v. k v -> f v -> t (g v)) -> t (DMap k g)
    forWithKey :: forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *) (g :: k -> *).
    Applicative t =>
    DMap k f
    -> (forall (v :: k). k v -> f v -> t (g v)) -> t (DMap k g)
    forWithKey DMap k f
    m forall (v :: k). k v -> f v -> t (g v)
    f = (forall (v :: k). k v -> f v -> t (g v))
    -> DMap k f -> t (DMap k g)
    forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *) (g :: k -> *).
    Applicative t =>
    (forall (v :: k). k v -> f v -> t (g v))
    -> DMap k f -> t (DMap k g)
    traverseWithKey k v -> f v -> t (g v)
    forall (v :: k). k v -> f v -> t (g v)
    f DMap k f
    m

    -- | /O(n)/. The function 'mapAccumLWithKey' threads an accumulating
    -- argument through the map in ascending order of keys.
    mapAccumLWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k g)
    mapAccumLWithKey :: forall {k} a (k :: k -> *) (f :: k -> *) (g :: k -> *).
    (forall (v :: k). a -> k v -> f v -> (a, g v))
    -> a -> DMap k f -> (a, DMap k g)
    mapAccumLWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
    f = a -> DMap k f -> (a, DMap k g)
    go
      where
        go :: a -> DMap k f -> (a, DMap k g)
    go a
    a DMap k f
    Tip               = (a
    a,DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
        go a
    a (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
                     let (a
    a1,DMap k g
    l') = a -> DMap k f -> (a, DMap k g)
    go a
    a DMap k f
    l
                         (a
    a2,g v
    x') = a -> k v -> f v -> (a, g v)
    forall (v :: k). a -> k v -> f v -> (a, g v)
    f a
    a1 k v
    kx f v
    x
                         (a
    a3,DMap k g
    r') = a -> DMap k f -> (a, DMap k g)
    go a
    a2 DMap k f
    r
                     in (a
    a3,Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx g v
    x' DMap k g
    l' DMap k g
    r')

    -- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating
    -- argument through the map in descending order of keys.
    mapAccumRWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k g)
    mapAccumRWithKey :: forall {k} a (k :: k -> *) (f :: k -> *) (g :: k -> *).
    (forall (v :: k). a -> k v -> f v -> (a, g v))
    -> a -> DMap k f -> (a, DMap k g)
    mapAccumRWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
    f = a -> DMap k f -> (a, DMap k g)
    go
      where
        go :: a -> DMap k f -> (a, DMap k g)
    go a
    a DMap k f
    Tip = (a
    a,DMap k g
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
        go a
    a (Bin Int
    sx k v
    kx f v
    x DMap k f
    l DMap k f
    r) =
                     let (a
    a1,DMap k g
    r') = a -> DMap k f -> (a, DMap k g)
    go a
    a DMap k f
    r
                         (a
    a2,g v
    x') = a -> k v -> f v -> (a, g v)
    forall (v :: k). a -> k v -> f v -> (a, g v)
    f a
    a1 k v
    kx f v
    x
                         (a
    a3,DMap k g
    l') = a -> DMap k f -> (a, DMap k g)
    go a
    a2 DMap k f
    l
                     in (a
    a3,Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sx k v
    kx g v
    x' DMap k g
    l' DMap k g
    r')

    -- | /O(n*log n)/.
    -- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
    --
    -- The size of the result may be smaller if @f@ maps two or more distinct
    -- keys to the same new key.  In this case the associated values will be
    -- combined using @c@.
    mapKeysWith :: GCompare k2 => (forall v. k2 v -> f v -> f v -> f v) -> (forall v. k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysWith :: forall {k} (k2 :: k -> *) (f :: k -> *) (k1 :: k -> *).
    GCompare k2 =>
    (forall (v :: k). k2 v -> f v -> f v -> f v)
    -> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysWith forall (v :: k). k2 v -> f v -> f v -> f v
    c forall (v :: k). k1 v -> k2 v
    f = (forall (v :: k). k2 v -> f v -> f v -> f v)
    -> [DSum k2 f] -> DMap k2 f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DSum k f] -> DMap k f
    fromListWithKey k2 v -> f v -> f v -> f v
    forall (v :: k). k2 v -> f v -> f v -> f v
    c ([DSum k2 f] -> DMap k2 f)
    -> (DMap k1 f -> [DSum k2 f]) -> DMap k1 f -> DMap k2 f
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (DSum k1 f -> DSum k2 f) -> [DSum k1 f] -> [DSum k2 f]
    forall a b. (a -> b) -> [a] -> [b]
    Prelude.map DSum k1 f -> DSum k2 f
    fFirst ([DSum k1 f] -> [DSum k2 f])
    -> (DMap k1 f -> [DSum k1 f]) -> DMap k1 f -> [DSum k2 f]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DMap k1 f -> [DSum k1 f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toList
        where fFirst :: DSum k1 f -> DSum k2 f
    fFirst (k1 a
    x :=> f a
    y) = (k1 a -> k2 a
    forall (v :: k). k1 v -> k2 v
    f k1 a
    x k2 a -> f a -> DSum k2 f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f a
    y)

    -- | /O(n)/.
    -- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@
    -- is strictly monotonic.
    -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
    -- /The precondition is not checked./
    -- Semi-formally, we have:
    --
    -- > and [x < y ==> f x < f y | x <- ls, y <- ls]
    -- >                     ==> mapKeysMonotonic f s == mapKeys f s
    -- >     where ls = keys s
    --
    -- This means that @f@ maps distinct original keys to distinct resulting keys.
    -- This function has better performance than 'mapKeys'.
    mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysMonotonic :: forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
    (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysMonotonic forall (v :: k). k1 v -> k2 v
    _ DMap k1 f
    Tip = DMap k2 f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
    mapKeysMonotonic forall (v :: k). k1 v -> k2 v
    f (Bin Int
    sz k1 v
    k f v
    x DMap k1 f
    l DMap k1 f
    r) =
        Int -> k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    forall {k} (k1 :: k -> *) (v :: k) (f :: k -> *).
    Int -> k1 v -> f v -> DMap k1 f -> DMap k1 f -> DMap k1 f
    Bin Int
    sz (k1 v -> k2 v
    forall (v :: k). k1 v -> k2 v
    f k1 v
    k) f v
    x ((forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
    (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysMonotonic k1 v -> k2 v
    forall (v :: k). k1 v -> k2 v
    f DMap k1 f
    l) ((forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
    (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
    mapKeysMonotonic k1 v -> k2 v
    forall (v :: k). k1 v -> k2 v
    f DMap k1 f
    r)

    {--------------------------------------------------------------------
      Folds
    --------------------------------------------------------------------}

    -- | /O(n)/. Fold the keys and values in the map, such that
    -- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
    --
    -- This is identical to 'foldrWithKey', and you should use that one instead of
    -- this one.  This name is kept for backward compatibility.
    foldWithKey :: (forall v. k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldWithKey :: forall {k} (k :: k -> *) (f :: k -> *) b.
    (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldWithKey = (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
    forall {k} (k :: k -> *) (f :: k -> *) b.
    (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldrWithKey
    {-# DEPRECATED foldWithKey "Use foldrWithKey instead" #-}

    -- | /O(n)/. Post-order fold.  The function will be applied from the lowest
    -- value to the highest.
    foldrWithKey :: (forall v. k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldrWithKey :: forall {k} (k :: k -> *) (f :: k -> *) b.
    (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldrWithKey forall (v :: k). k v -> f v -> b -> b
    f = b -> DMap k f -> b
    go
      where
        go :: b -> DMap k f -> b
    go b
    z DMap k f
    Tip              = b
    z
        go b
    z (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = b -> DMap k f -> b
    go (k v -> f v -> b -> b
    forall (v :: k). k v -> f v -> b -> b
    f k v
    kx f v
    x (b -> DMap k f -> b
    go b
    z DMap k f
    r)) DMap k f
    l

    -- | /O(n)/. Pre-order fold.  The function will be applied from the highest
    -- value to the lowest.
    foldlWithKey :: (forall v. b -> k v -> f v -> b) -> b -> DMap k f -> b
    foldlWithKey :: forall {k} b (k :: k -> *) (f :: k -> *).
    (forall (v :: k). b -> k v -> f v -> b) -> b -> DMap k f -> b
    foldlWithKey forall (v :: k). b -> k v -> f v -> b
    f = b -> DMap k f -> b
    go
      where
        go :: b -> DMap k f -> b
    go b
    z DMap k f
    Tip              = b
    z
        go b
    z (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = b -> DMap k f -> b
    go (b -> k v -> f v -> b
    forall (v :: k). b -> k v -> f v -> b
    f (b -> DMap k f -> b
    go b
    z DMap k f
    l) k v
    kx f v
    x) DMap k f
    r

    {-
    -- | /O(n)/. A strict version of 'foldlWithKey'.
    foldlWithKey' :: (b -> k -> a -> b) -> b -> DMap k -> b
    foldlWithKey' f = go
      where
        go z Tip              = z
        go z (Bin _ kx x l r) = z `seq` go (f (go z l) kx x) r
    -}

    {--------------------------------------------------------------------
      List variations
    --------------------------------------------------------------------}

    -- | /O(n)/. Return all keys of the map in ascending order.
    --
    -- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]
    -- > keys empty == []

    keys  :: DMap k f -> [Some k]
    keys :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [Some k]
    keys DMap k f
    m
      = [k a -> Some k
    forall {k} (tag :: k -> *) (a :: k). tag a -> Some tag
    mkSome k a
    k | (k a
    k :=> f a
    _) <- DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    assocs DMap k f
    m]

    -- | /O(n)/. Return all key\/value pairs in the map in ascending key order.
    assocs :: DMap k f -> [DSum k f]
    assocs :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    assocs DMap k f
    m
      = DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toList DMap k f
    m

    {--------------------------------------------------------------------
      Lists
      use [foldlStrict] to reduce demand on the control-stack
    --------------------------------------------------------------------}

    -- | /O(n*log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.
    -- If the list contains more than one value for the same key, the last value
    -- for the key is retained.
    fromList :: GCompare k => [DSum k f] -> DMap k f
    fromList :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    [DSum k f] -> DMap k f
    fromList [DSum k f]
    xs
      = (DMap k f -> DSum k f -> DMap k f)
    -> DMap k f -> [DSum k f] -> DMap k f
    forall a b. (a -> b -> a) -> a -> [b] -> a
    foldlStrict DMap k f -> DSum k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DSum k f -> DMap k f
    ins DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    empty [DSum k f]
    xs
      where
        ins :: GCompare k => DMap k f -> DSum k f -> DMap k f
        ins :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> DSum k f -> DMap k f
    ins DMap k f
    t (k a
    k :=> f a
    x) = k a -> f a -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> f v -> DMap k f -> DMap k f
    insert k a
    k f a
    x DMap k f
    t

    -- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'.
    fromListWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k f
    fromListWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DSum k f] -> DMap k f
    fromListWithKey forall (v :: k). k v -> f v -> f v -> f v
    f [DSum k f]
    xs
      = (DMap k f -> DSum k f -> DMap k f)
    -> DMap k f -> [DSum k f] -> DMap k f
    forall a b. (a -> b -> a) -> a -> [b] -> a
    foldlStrict ((forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DSum k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DSum k f -> DMap k f
    ins k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f) DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    empty [DSum k f]
    xs
      where
        ins :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> DMap k f -> DSum k f -> DMap k f
        ins :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DMap k f -> DSum k f -> DMap k f
    ins forall (v :: k). k v -> f v -> f v -> f v
    f DMap k f
    t (k a
    k :=> f a
    x) = (k a -> f a -> f a -> f a) -> k a -> f a -> DMap k f -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
    insertWithKey k a -> f a -> f a -> f a
    forall (v :: k). k v -> f v -> f v -> f v
    f k a
    k f a
    x DMap k f
    t

    -- | /O(n)/. Convert to a list of key\/value pairs.
    toList :: DMap k f -> [DSum k f]
    toList :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toList DMap k f
    t      = DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    t

    -- | /O(n)/. Convert to an ascending list.
    toAscList :: DMap k f -> [DSum k f]
    toAscList :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    t   = (forall (v :: k). k v -> f v -> [DSum k f] -> [DSum k f])
    -> [DSum k f] -> DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *) b.
    (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
    foldrWithKey (\k v
    k f v
    x [DSum k f]
    xs -> (k v
    k k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x)DSum k f -> [DSum k f] -> [DSum k f]
    forall a. a -> [a] -> [a]
    :[DSum k f]
    xs) [] DMap k f
    t

    -- | /O(n)/. Convert to a descending list.
    toDescList :: DMap k f -> [DSum k f]
    toDescList :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toDescList DMap k f
    t  = (forall (v :: k). [DSum k f] -> k v -> f v -> [DSum k f])
    -> [DSum k f] -> DMap k f -> [DSum k f]
    forall {k} b (k :: k -> *) (f :: k -> *).
    (forall (v :: k). b -> k v -> f v -> b) -> b -> DMap k f -> b
    foldlWithKey (\[DSum k f]
    xs k v
    k f v
    x -> (k v
    k k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x)DSum k f -> [DSum k f] -> [DSum k f]
    forall a. a -> [a] -> [a]
    :[DSum k f]
    xs) [] DMap k f
    t

    {--------------------------------------------------------------------
      Building trees from ascending/descending lists can be done in linear time.

      Note that if [xs] is ascending that:
        fromAscList xs       == fromList xs
        fromAscListWith f xs == fromListWith f xs
    --------------------------------------------------------------------}

    -- | /O(n)/. Build a map from an ascending list in linear time.
    -- /The precondition (input list is ascending) is not checked./
    fromAscList :: GEq k => [DSum k f] -> DMap k f
    fromAscList :: forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    [DSum k f] -> DMap k f
    fromAscList [DSum k f]
    xs
      = (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DSum k f] -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DSum k f] -> DMap k f
    fromAscListWithKey (\k v
    _ f v
    x f v
    _ -> f v
    x) [DSum k f]
    xs

    -- | /O(n)/. Build a map from an ascending list in linear time with a
    -- combining function for equal keys.
    -- /The precondition (input list is ascending) is not checked./
    fromAscListWithKey :: GEq k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k f
    fromAscListWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> [DSum k f] -> DMap k f
    fromAscListWithKey forall (v :: k). k v -> f v -> f v -> f v
    f [DSum k f]
    xs
      = [DSum k f] -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *). [DSum k f] -> DMap k f
    fromDistinctAscList ((k (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0))
    -> [DSum k f] -> [DSum k f]
    combineEq k (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0)
    forall (v :: k). k v -> f v -> f v -> f v
    f [DSum k f]
    xs)
      where
      -- [combineEq f xs] combines equal elements with function [f] in an ordered list [xs]
      combineEq :: (k (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0))
    -> [DSum k f] -> [DSum k f]
    combineEq k (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0) -> f (ZonkAny 0)
    _ [DSum k f]
    xs'
        = case [DSum k f]
    xs' of
            []     -> []
            [DSum k f
    x]    -> [DSum k f
    x]
            (DSum k f
    x:[DSum k f]
    xx) -> (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    combineEq' k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f DSum k f
    x [DSum k f]
    xx

      combineEq' :: GEq k => (forall v. k v -> f v -> f v -> f v) -> DSum k f -> [DSum k f] -> [DSum k f]
      combineEq' :: forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    combineEq' forall (v :: k). k v -> f v -> f v -> f v
    f DSum k f
    z [] = [DSum k f
    z]
      combineEq' forall (v :: k). k v -> f v -> f v -> f v
    f z :: DSum k f
    z@(k a
    kz :=> f a
    zz) (x :: DSum k f
    x@(k a
    kx :=> f a
    xx):[DSum k f]
    xs') =
        case k a -> k a -> Maybe (a :~: a)
    forall (a :: k) (b :: k). k a -> k b -> Maybe (a :~: b)
    forall k (f :: k -> *) (a :: k) (b :: k).
    GEq f =>
    f a -> f b -> Maybe (a :~: b)
    geq k a
    kx k a
    kz of
            Just a :~: a
    Refl   -> let yy :: f a
    yy = k a -> f a -> f a -> f a
    forall (v :: k). k v -> f v -> f v -> f v
    f k a
    kx f a
    xx f a
    f a
    zz in (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    combineEq' k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f (k a
    kx k a -> f a -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f a
    yy) [DSum k f]
    xs'
            Maybe (a :~: a)
    Nothing     -> DSum k f
    z DSum k f -> [DSum k f] -> [DSum k f]
    forall a. a -> [a] -> [a]
    : (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *).
    GEq k =>
    (forall (v :: k). k v -> f v -> f v -> f v)
    -> DSum k f -> [DSum k f] -> [DSum k f]
    combineEq' k v -> f v -> f v -> f v
    forall (v :: k). k v -> f v -> f v -> f v
    f DSum k f
    x [DSum k f]
    xs'

    -- | /O(n)/. Build a map from an ascending list of distinct elements in linear time.
    -- /The precondition is not checked./
    fromDistinctAscList :: [DSum k f] -> DMap k f
    fromDistinctAscList :: forall {k} (k :: k -> *) (f :: k -> *). [DSum k f] -> DMap k f
    fromDistinctAscList [DSum k f]
    xs
      = (DMap k f -> [DSum k f] -> DMap k f)
    -> Int -> [DSum k f] -> DMap k f
    forall {k} (k :: k -> *) (f :: k -> *) b.
    (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    build DMap k f -> [DSum k f] -> DMap k f
    forall a b. a -> b -> a
    const ([DSum k f] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [DSum k f]
    xs) [DSum k f]
    xs
      where
        -- 1) use continutations so that we use heap space instead of stack space.
        -- 2) special case for n==5 to build bushier trees.

        build :: (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
        build :: forall {k} (k :: k -> *) (f :: k -> *) b.
    (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    build DMap k f -> [DSum k f] -> b
    c Int
    0 [DSum k f]
    xs'  = DMap k f -> [DSum k f] -> b
    c DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip [DSum k f]
    xs'
        build DMap k f -> [DSum k f] -> b
    c Int
    5 [DSum k f]
    xs'  = case [DSum k f]
    xs' of
                           ((k a
    k1:=>f a
    x1):(k a
    k2:=>f a
    x2):(k a
    k3:=>f a
    x3):(k a
    k4:=>f a
    x4):(k a
    k5:=>f a
    x5):[DSum k f]
    xx)
                                -> DMap k f -> [DSum k f] -> b
    c (k a -> f a -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    bin k a
    k4 f a
    x4 (k a -> f a -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    bin k a
    k2 f a
    x2 (k a -> f a -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k a
    k1 f a
    x1) (k a -> f a -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k a
    k3 f a
    x3)) (k a -> f a -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f
    singleton k a
    k5 f a
    x5)) [DSum k f]
    xx
                           [DSum k f]
    _ -> [Char] -> b
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "fromDistinctAscList build"
        build DMap k f -> [DSum k f] -> b
    c Int
    n [DSum k f]
    xs'  = Int -> b -> b
    forall a b. a -> b -> b
    seq Int
    nr (b -> b) -> b -> b
    forall a b. (a -> b) -> a -> b
    $ (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    forall {k} (k :: k -> *) (f :: k -> *) b.
    (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    build (Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
    forall {k} (k :: k -> *) (f :: k -> *) b.
    Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
    buildR Int
    nr DMap k f -> [DSum k f] -> b
    c) Int
    nl [DSum k f]
    xs'
                       where
                         nl :: Int
    nl = Int
    n Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `div` Int
    2
                         nr :: Int
    nr = Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    nl Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1

        buildR :: Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
        buildR :: forall {k} (k :: k -> *) (f :: k -> *) b.
    Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
    buildR Int
    n DMap k f -> [DSum k f] -> b
    c DMap k f
    l ((k a
    k:=>f a
    x):[DSum k f]
    ys) = (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    forall {k} (k :: k -> *) (f :: k -> *) b.
    (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    build (DMap k f
    -> k a
    -> f a
    -> (DMap k f -> [DSum k f] -> b)
    -> DMap k f
    -> [DSum k f]
    -> b
    forall {k} (k :: k -> *) (f :: k -> *) (v :: k) a b.
    DMap k f
    -> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
    buildB DMap k f
    l k a
    k f a
    x DMap k f -> [DSum k f] -> b
    c) Int
    n [DSum k f]
    ys
        buildR Int
    _ DMap k f -> [DSum k f] -> b
    _ DMap k f
    _ []           = [Char] -> b
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "fromDistinctAscList buildR []"

        buildB :: DMap k f -> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
        buildB :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k) a b.
    DMap k f
    -> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
    buildB DMap k f
    l k v
    k f v
    x DMap k f -> a -> b
    c DMap k f
    r a
    zs       = DMap k f -> a -> b
    c (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    bin k v
    k f v
    x DMap k f
    l DMap k f
    r) a
    zs

    {--------------------------------------------------------------------
      Split
    --------------------------------------------------------------------}

    -- | /O(log n)/. The expression (@'split' k map@) is a pair @(map1,map2)@ where
    -- the keys in @map1@ are smaller than @k@ and the keys in @map2@ larger than @k@.
    -- Any key equal to @k@ is found in neither @map1@ nor @map2@.
    split :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, DMap k f)
    split :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, DMap k f)
    split k v
    k = (DMap k f :*: DMap k f) -> (DMap k f, DMap k f)
    forall a b. (a :*: b) -> (a, b)
    toPair ((DMap k f :*: DMap k f) -> (DMap k f, DMap k f))
    -> (DMap k f -> DMap k f :*: DMap k f)
    -> DMap k f
    -> (DMap k f, DMap k f)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DMap k f -> DMap k f :*: DMap k f
    go
      where
        go :: DMap k f -> (DMap k f :*: DMap k f)
        go :: DMap k f -> DMap k f :*: DMap k f
    go DMap k f
    Tip              = (DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip)
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
              GOrdering v v
    GLT -> let !(DMap k f
    lt :*: DMap k f
    gt) = DMap k f -> DMap k f :*: DMap k f
    go DMap k f
    l in (DMap k f
    lt DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    gt DMap k f
    r)
              GOrdering v v
    GGT -> let !(DMap k f
    lt :*: DMap k f
    gt) = DMap k f -> DMap k f :*: DMap k f
    go DMap k f
    r in (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l DMap k f
    lt DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: DMap k f
    gt)
              GOrdering v v
    GEQ -> (DMap k f
    l DMap k f -> DMap k f -> DMap k f :*: DMap k f
    forall a b. a -> b -> a :*: b
    :*: DMap k f
    r)
    {-# INLINABLE split #-}

    -- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
    -- like 'split' but also returns @'lookup' k map@.
    splitLookup :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    splitLookup :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
    splitLookup k v
    k = Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    -> (DMap k f, Maybe (f v), DMap k f)
    forall a b c. Triple' a b c -> (a, b, c)
    toTriple (Triple' (DMap k f) (Maybe (f v)) (DMap k f)
     -> (DMap k f, Maybe (f v), DMap k f))
    -> (DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f))
    -> DMap k f
    -> (DMap k f, Maybe (f v), DMap k f)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    go
      where
        go :: DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
        go :: DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    go DMap k f
    Tip              = DMap k f
    -> Maybe (f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip Maybe (f v)
    forall a. Maybe a
    Nothing DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
          GOrdering v v
    GLT -> let !(Triple' DMap k f
    lt Maybe (f v)
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    go DMap k f
    l in DMap k f
    -> Maybe (f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    lt Maybe (f v)
    z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    gt DMap k f
    r)
          GOrdering v v
    GGT -> let !(Triple' DMap k f
    lt Maybe (f v)
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    go DMap k f
    r in DMap k f
    -> Maybe (f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l DMap k f
    lt) Maybe (f v)
    z DMap k f
    gt
          GOrdering v v
    GEQ -> DMap k f
    -> Maybe (f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    l (f v -> Maybe (f v)
    forall a. a -> Maybe a
    Just f v
    f v
    x) DMap k f
    r

    -- | /O(log n)/. The expression (@'splitMember' k map@) splits a map just
    -- like 'split' but also returns @'member' k map@.
    splitMember :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Bool, DMap k f)
    splitMember :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Bool, DMap k f)
    splitMember k v
    k = Triple' (DMap k f) Bool (DMap k f) -> (DMap k f, Bool, DMap k f)
    forall a b c. Triple' a b c -> (a, b, c)
    toTriple (Triple' (DMap k f) Bool (DMap k f) -> (DMap k f, Bool, DMap k f))
    -> (DMap k f -> Triple' (DMap k f) Bool (DMap k f))
    -> DMap k f
    -> (DMap k f, Bool, DMap k f)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    go
      where
        go :: DMap k f -> Triple' (DMap k f) Bool (DMap k f)
        go :: DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    go DMap k f
    Tip              = DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip Bool
    False DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
          GOrdering v v
    GLT -> let !(Triple' DMap k f
    lt Bool
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    go DMap k f
    l in DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    lt Bool
    z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    gt DMap k f
    r)
          GOrdering v v
    GGT -> let !(Triple' DMap k f
    lt Bool
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    go DMap k f
    r in DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l DMap k f
    lt) Bool
    z DMap k f
    gt
          GOrdering v v
    GEQ -> DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    l Bool
    True DMap k f
    r

    -- | /O(log n)/.
    splitLookupWithKey :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
    splitLookupWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
    GCompare k =>
    k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
    splitLookupWithKey k v
    k = Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    -> (DMap k f, Maybe (k v, f v), DMap k f)
    forall a b c. Triple' a b c -> (a, b, c)
    toTriple (Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
     -> (DMap k f, Maybe (k v, f v), DMap k f))
    -> (DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f))
    -> DMap k f
    -> (DMap k f, Maybe (k v, f v), DMap k f)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    go
      where
        go :: DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
        go :: DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    go DMap k f
    Tip              = DMap k f
    -> Maybe (k v, f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip Maybe (k v, f v)
    forall a. Maybe a
    Nothing DMap k f
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
    Tip
        go (Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r) = case k v -> k v -> GOrdering v v
    forall (a :: k) (b :: k). k a -> k b -> GOrdering a b
    forall k (f :: k -> *) (a :: k) (b :: k).
    GCompare f =>
    f a -> f b -> GOrdering a b
    gcompare k v
    k k v
    kx of
          GOrdering v v
    GLT -> let !(Triple' DMap k f
    lt Maybe (k v, f v)
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    go DMap k f
    l in DMap k f
    -> Maybe (k v, f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    lt Maybe (k v, f v)
    z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    gt DMap k f
    r)
          GOrdering v v
    GGT -> let !(Triple' DMap k f
    lt Maybe (k v, f v)
    z DMap k f
    gt) = DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    go DMap k f
    r in DMap k f
    -> Maybe (k v, f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
    forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
    GCompare k2 =>
    k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
    combine k v
    kx f v
    x DMap k f
    l DMap k f
    lt) Maybe (k v, f v)
    z DMap k f
    gt
          GOrdering v v
    GEQ -> DMap k f
    -> Maybe (k v, f v)
    -> DMap k f
    -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    forall a b c. a -> b -> c -> Triple' a b c
    Triple' DMap k f
    l ((k v, f v) -> Maybe (k v, f v)
    forall a. a -> Maybe a
    Just (k v
    k v
    kx, f v
    f v
    x)) DMap k f
    r

    {--------------------------------------------------------------------
      Eq converts the tree to a list. In a lazy setting, this
      actually seems one of the faster methods to compare two trees
      and it is certainly the simplest :-)
    --------------------------------------------------------------------}
    instance (GEq k, Has' Eq k f) => Eq (DMap k f) where
      DMap k f
    t1 == :: DMap k f -> DMap k f -> Bool
    == DMap k f
    t2  = (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t1 Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t2) Bool -> Bool -> Bool
    && (DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    t1 [DSum k f] -> [DSum k f] -> Bool
    forall a. Eq a => a -> a -> Bool
    == DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    t2)

    {--------------------------------------------------------------------
      Ord
    --------------------------------------------------------------------}

    instance (GCompare k, Has' Eq k f, Has' Ord k f) => Ord (DMap k f) where
      compare :: DMap k f -> DMap k f -> Ordering
    compare DMap k f
    m1 DMap k f
    m2 = [DSum k f] -> [DSum k f] -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    m1) (DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toAscList DMap k f
    m2)

    {--------------------------------------------------------------------
      Read
    --------------------------------------------------------------------}

    instance (GCompare k, GRead k, Has' Read k f) => Read (DMap k f) where
      readPrec :: ReadPrec (DMap k f)
    readPrec = ReadPrec (DMap k f) -> ReadPrec (DMap k f)
    forall a. ReadPrec a -> ReadPrec a
    parens (ReadPrec (DMap k f) -> ReadPrec (DMap k f))
    -> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
    forall a b. (a -> b) -> a -> b
    $ Int -> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
    forall a. Int -> ReadPrec a -> ReadPrec a
    prec Int
    10 (ReadPrec (DMap k f) -> ReadPrec (DMap k f))
    -> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
    forall a b. (a -> b) -> a -> b
    $ do
        Ident "fromList" <- ReadPrec Lexeme
    lexP
        xs <- readPrec
        return (fromList xs)

      readListPrec :: ReadPrec [DMap k f]
    readListPrec = ReadPrec [DMap k f]
    forall a. Read a => ReadPrec [a]
    readListPrecDefault

    {--------------------------------------------------------------------
      Show
    --------------------------------------------------------------------}
    instance (GShow k, Has' Show k f) => Show (DMap k f) where
        showsPrec :: Int -> DMap k f -> ShowS
    showsPrec Int
    p DMap k f
    m = Bool -> ShowS -> ShowS
    showParen (Int
    pInt -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >Int
    10)
            ( [Char] -> ShowS
    showString [Char]
    "fromList "
            ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> [DSum k f] -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec Int
    11 (DMap k f -> [DSum k f]
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
    toList DMap k f
    m)
            )

    -- | /O(n)/. Show the tree that implements the map. The tree is shown
    -- in a compressed, hanging format. See 'showTreeWith'.
    showTree :: (GShow k, Has' Show k f) => DMap k f -> String
    showTree :: forall k (k :: k -> *) (f :: k -> *).
    (GShow k, Has' Show k f) =>
    DMap k f -> [Char]
    showTree DMap k f
    m
      = (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> Bool -> DMap k f -> [Char]
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> Bool -> DMap k f -> [Char]
    showTreeWith k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    forall {k'} (k :: k' -> *) (f :: k' -> *) (v :: k').
    (GShow k, Has' Show k f) =>
    k v -> f v -> [Char]
    showElem Bool
    True Bool
    False DMap k f
    m
      where
        showElem :: (GShow k, Has' Show k f) => k v -> f v -> String
        showElem :: forall {k'} (k :: k' -> *) (f :: k' -> *) (v :: k').
    (GShow k, Has' Show k f) =>
    k v -> f v -> [Char]
    showElem k v
    k f v
    x  = DSum k f -> [Char]
    forall a. Show a => a -> [Char]
    show (k v
    k k v -> f v -> DSum k f
    forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
    tag a -> f a -> DSum tag f
    :=> f v
    x)

    {- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
     the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
     'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
     @wide@ is 'True', an extra wide version is shown.
    -}
    showTreeWith :: (forall v. k v -> f v -> String) -> Bool -> Bool -> DMap k f -> String
    showTreeWith :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> Bool -> DMap k f -> [Char]
    showTreeWith forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    hang Bool
    wide DMap k f
    t
      | Bool
    hang      = ((forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    showsTreeHang k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide [] DMap k f
    t) [Char]
    ""
      | Bool
    otherwise = ((forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    showsTree k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide [] [] DMap k f
    t) [Char]
    ""

    showsTree :: (forall v. k v -> f v -> String) -> Bool -> [String] -> [String] -> DMap k f -> ShowS
    showsTree :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    showsTree forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide [[Char]]
    lbars [[Char]]
    rbars DMap k f
    t
      = case DMap k f
    t of
          DMap k f
    Tip -> [[Char]] -> ShowS
    showsBars [[Char]]
    lbars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "|\n"
          Bin Int
    _ k v
    kx f v
    x DMap k f
    Tip DMap k f
    Tip
              -> [[Char]] -> ShowS
    showsBars [[Char]]
    lbars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString (k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem k v
    kx f v
    x) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "\n"
          Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r
              -> (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    showsTree k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide ([[Char]] -> [[Char]]
    withBar [[Char]]
    rbars) ([[Char]] -> [[Char]]
    withEmpty [[Char]]
    rbars) DMap k f
    r ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 Bool -> [[Char]] -> ShowS
    showWide Bool
    wide [[Char]]
    rbars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 [[Char]] -> ShowS
    showsBars [[Char]]
    lbars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString (k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem k v
    kx f v
    x) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "\n" ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 Bool -> [[Char]] -> ShowS
    showWide Bool
    wide [[Char]]
    lbars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
    showsTree k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide ([[Char]] -> [[Char]]
    withEmpty [[Char]]
    lbars) ([[Char]] -> [[Char]]
    withBar [[Char]]
    lbars) DMap k f
    l

    showsTreeHang :: (forall v. k v -> f v -> String) -> Bool -> [String] -> DMap k f -> ShowS
    showsTreeHang :: forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    showsTreeHang forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide [[Char]]
    bars DMap k f
    t
      = case DMap k f
    t of
          DMap k f
    Tip -> [[Char]] -> ShowS
    showsBars [[Char]]
    bars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "|\n"
          Bin Int
    _ k v
    kx f v
    x DMap k f
    Tip DMap k f
    Tip
              -> [[Char]] -> ShowS
    showsBars [[Char]]
    bars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString (k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem k v
    kx f v
    x) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "\n"
          Bin Int
    _ k v
    kx f v
    x DMap k f
    l DMap k f
    r
              -> [[Char]] -> ShowS
    showsBars [[Char]]
    bars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString (k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem k v
    kx f v
    x) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "\n" ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 Bool -> [[Char]] -> ShowS
    showWide Bool
    wide [[Char]]
    bars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    showsTreeHang k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide ([[Char]] -> [[Char]]
    withBar [[Char]]
    bars) DMap k f
    l ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 Bool -> [[Char]] -> ShowS
    showWide Bool
    wide [[Char]]
    bars ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                 (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    forall {k} (k :: k -> *) (f :: k -> *).
    (forall (v :: k). k v -> f v -> [Char])
    -> Bool -> [[Char]] -> DMap k f -> ShowS
    showsTreeHang k v -> f v -> [Char]
    forall (v :: k). k v -> f v -> [Char]
    showelem Bool
    wide ([[Char]] -> [[Char]]
    withEmpty [[Char]]
    bars) DMap k f
    r

    showWide :: Bool -> [String] -> String -> String
    showWide :: Bool -> [[Char]] -> ShowS
    showWide Bool
    wide [[Char]]
    bars
      | Bool
    wide      = [Char] -> ShowS
    showString ([[Char]] -> [Char]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[Char]] -> [[Char]]
    forall a. [a] -> [a]
    reverse [[Char]]
    bars)) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    "|\n"
      | Bool
    otherwise = ShowS
    forall a. a -> a
    id

    showsBars :: [String] -> ShowS
    showsBars :: [[Char]] -> ShowS
    showsBars [[Char]]
    bars
      = case [[Char]]
    bars of
          [] -> ShowS
    forall a. a -> a
    id
          [[Char]]
    _  -> [Char] -> ShowS
    showString ([[Char]] -> [Char]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[Char]] -> [[Char]]
    forall a. [a] -> [a]
    reverse ([[Char]] -> [[Char]]
    forall a. HasCallStack => [a] -> [a]
    tail [[Char]]
    bars))) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Char] -> ShowS
    showString [Char]
    node

    node :: String
    node :: [Char]
    node           = [Char]
    "+--"

    withBar, withEmpty :: [String] -> [String]
    withBar :: [[Char]] -> [[Char]]
    withBar [[Char]]
    bars   = [Char]
    "|  "[Char] -> [[Char]] -> [[Char]]
    forall a. a -> [a] -> [a]
    :[[Char]]
    bars
    withEmpty :: [[Char]] -> [[Char]]
    withEmpty [[Char]]
    bars = [Char]
    "   "[Char] -> [[Char]] -> [[Char]]
    forall a. a -> [a] -> [a]
    :[[Char]]
    bars

    {--------------------------------------------------------------------
      Assertions
    --------------------------------------------------------------------}

    -- | /O(n)/. Test if the internal map structure is valid.
    valid :: GCompare k => DMap k f -> Bool
    valid :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> Bool
    valid DMap k f
    t
      = DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    balanced DMap k f
    t Bool -> Bool -> Bool
    && DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> Bool
    ordered DMap k f
    t Bool -> Bool -> Bool
    && DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    validsize DMap k f
    t

    ordered :: GCompare k => DMap k f -> Bool
    ordered :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    DMap k f -> Bool
    ordered DMap k f
    t
      = (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    bounded (Bool -> Some k -> Bool
    forall a b. a -> b -> a
    const Bool
    True) (Bool -> Some k -> Bool
    forall a b. a -> b -> a
    const Bool
    True) DMap k f
    t
      where
        bounded :: GCompare k => (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
        bounded :: forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    bounded Some k -> Bool
    lo Some k -> Bool
    hi DMap k f
    t'
          = case DMap k f
    t' of
              DMap k f
    Tip              -> Bool
    True
              Bin Int
    _ k v
    kx f v
    _ DMap k f
    l DMap k f
    r  -> Some k -> Bool
    lo (k v -> Some k
    forall {k} (tag :: k -> *) (a :: k). tag a -> Some tag
    mkSome k v
    kx) Bool -> Bool -> Bool
    && Some k -> Bool
    hi (k v -> Some k
    forall {k} (tag :: k -> *) (a :: k). tag a -> Some tag
    mkSome k v
    kx) Bool -> Bool -> Bool
    && (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    bounded Some k -> Bool
    lo (Some k -> Some k -> Bool
    forall a. Ord a => a -> a -> Bool
    < k v -> Some k
    forall {k} (tag :: k -> *) (a :: k). tag a -> Some tag
    mkSome k v
    kx) DMap k f
    l Bool -> Bool -> Bool
    && (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *).
    GCompare k =>
    (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    bounded (Some k -> Some k -> Bool
    forall a. Ord a => a -> a -> Bool
    > k v -> Some k
    forall {k} (tag :: k -> *) (a :: k). tag a -> Some tag
    mkSome k v
    kx) Some k -> Bool
    hi DMap k f
    r

    -- | Exported only for "Debug.QuickCheck"
    balanced :: DMap k f -> Bool
    balanced :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    balanced DMap k f
    t
      = case DMap k f
    t of
          DMap k f
    Tip            -> Bool
    True
          Bin Int
    _ k v
    _ f v
    _ DMap k f
    l DMap k f
    r  -> (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    r Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    1 Bool -> Bool -> Bool
    || (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    deltaInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    r Bool -> Bool -> Bool
    && DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    r Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    deltaInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    l)) Bool -> Bool -> Bool
    &&
                            DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    balanced DMap k f
    l Bool -> Bool -> Bool
    && DMap k f -> Bool
    forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    balanced DMap k f
    r

    validsize :: DMap k f -> Bool
    validsize :: forall {k} (k :: k -> *) (f :: k -> *). DMap k f -> Bool
    validsize DMap k f
    t
      = (DMap k f -> Maybe Int
    forall {k} {k1 :: k -> *} {f :: k -> *}. DMap k1 f -> Maybe Int
    realsize DMap k f
    t Maybe Int -> Maybe Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int -> Maybe Int
    forall a. a -> Maybe a
    Just (DMap k f -> Int
    forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
    size DMap k f
    t))
      where
        realsize :: DMap k1 f -> Maybe Int
    realsize DMap k1 f
    t'
          = case DMap k1 f
    t' of
              DMap k1 f
    Tip            -> Int -> Maybe Int
    forall a. a -> Maybe a
    Just Int
    0
              Bin Int
    sz k1 v
    _ f v
    _ DMap k1 f
    l DMap k1 f
    r -> case (DMap k1 f -> Maybe Int
    realsize DMap k1 f
    l,DMap k1 f -> Maybe Int
    realsize DMap k1 f
    r) of
                                (Just Int
    n,Just Int
    m)  | Int
    nInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    mInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1 Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    sz  -> Int -> Maybe Int
    forall a. a -> Maybe a
    Just Int
    sz
                                (Maybe Int, Maybe Int)
    _                               -> Maybe Int
    forall a. Maybe a
    Nothing
    {--------------------------------------------------------------------
      Utilities
    --------------------------------------------------------------------}
    foldlStrict :: (a -> b -> a) -> a -> [b] -> a
    foldlStrict :: forall a b. (a -> b -> a) -> a -> [b] -> a
    foldlStrict a -> b -> a
    f = a -> [b] -> a
    go
      where
        go :: a -> [b] -> a
    go a
    z []     = a
    z
        go a
    z (b
    x:[b]
    xs) = a
    z a -> a -> a
    forall a b. a -> b -> b
    `seq` a -> [b] -> a
    go (a -> b -> a
    f a
    z b
    x) [b]
    xs