    {-# LANGUAGE DeriveAnyClass        #-}
    {-# LANGUAGE DeriveDataTypeable    #-}
    {-# LANGUAGE DeriveGeneric         #-}
    {-# LANGUAGE DeriveLift            #-}
    {-# LANGUAGE ExplicitForAll        #-}
    {-# LANGUAGE FlexibleInstances     #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE TypeFamilies          #-}

    -- | `Map` type used to represent records and unions

    module Dhall.Map
        ( -- * Type
          Map

          -- * Construction
        , empty
        , singleton
        , fromList
        , fromListWithKey
        , fromMap

          -- * Constructing unordered 'Map's
        , unorderedSingleton
        , unorderedFromList

          -- * Sorting
        , sort
        , isSorted

          -- * Insertion
        , insert
        , insertWith

          -- * Deletion/Update
        , delete
        , filter
        , partition
        , restrictKeys
        , withoutKeys
        , mapMaybe

          -- * Query
        , lookup
        , member
        , uncons
        , size

          -- * Combine
        , union
        , unionWith
        , outerJoin
        , intersection
        , intersectionWith
        , difference

          -- * Traversals
        , mapWithKey
        , traverseWithKey
        , unorderedTraverseWithKey
        , unorderedTraverseWithKey_
        , foldMapWithKey

          -- * Conversions
        , toList
        , toAscList
        , toMap
        , keys
        , keysSet
        , elems
        ) where

    import Control.Applicative        ((<|>))
    import Control.DeepSeq            (NFData)
    import Data.Data                  (Data)
    import GHC.Generics               (Generic)
    import Instances.TH.Lift          ()
    import Language.Haskell.TH.Syntax (Lift)
    import Prelude                    hiding (filter, lookup)

    import qualified Data.Foldable.WithIndex    as Foldable.WithIndex
    import qualified Data.Functor.WithIndex     as Functor.WithIndex
    import qualified Data.List
    import qualified Data.Map.Strict
    import qualified Data.Set
    import qualified Data.Traversable.WithIndex as Traversable.WithIndex
    import qualified GHC.Exts
    import qualified Prelude

    {-| A `Map` that remembers the original ordering of keys

        This is primarily used so that formatting preserves field order

        This is done primarily to avoid a dependency on @insert-ordered-containers@
        and also to improve performance
    -}
    data Map k v = Map (Data.Map.Strict.Map k v) (Keys k)
        deriving (Typeable (Map k v)
    Typeable (Map k v) =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> Map k v -> c (Map k v))
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c (Map k v))
    -> (Map k v -> Constr)
    -> (Map k v -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c (Map k v)))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v)))
    -> ((forall b. Data b => b -> b) -> Map k v -> Map k v)
    -> (forall r r'.
        (r -> r' -> r)
        -> r -> (forall d. Data d => d -> r') -> Map k v -> r)
    -> (forall r r'.
        (r' -> r -> r)
        -> r -> (forall d. Data d => d -> r') -> Map k v -> r)
    -> (forall u. (forall d. Data d => d -> u) -> Map k v -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
    -> Data (Map k v)
    Map k v -> Constr
    Map k v -> DataType
    (forall b. Data b => b -> b) -> Map k v -> Map k v
    forall a.
    Typeable a =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> a -> c a)
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c a)
    -> (a -> Constr)
    -> (a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c a))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
    -> ((forall b. Data b => b -> b) -> a -> a)
    -> (forall r r'.
        (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall r r'.
        (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> Data a
    forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u
    forall u. (forall d. Data d => d -> u) -> Map k v -> [u]
    forall k v. (Data k, Data v, Ord k) => Typeable (Map k v)
    forall k v. (Data k, Data v, Ord k) => Map k v -> Constr
    forall k v. (Data k, Data v, Ord k) => Map k v -> DataType
    forall k v.
    (Data k, Data v, Ord k) =>
    (forall b. Data b => b -> b) -> Map k v -> Map k v
    forall k v u.
    (Data k, Data v, Ord k) =>
    Int -> (forall d. Data d => d -> u) -> Map k v -> u
    forall k v u.
    (Data k, Data v, Ord k) =>
    (forall d. Data d => d -> u) -> Map k v -> [u]
    forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    forall k v (m :: * -> *).
    (Data k, Data v, Ord k, Monad m) =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Map k v)
    forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Map k v -> c (Map k v)
    forall k v (t :: * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (Map k v))
    forall k v (t :: * -> * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
    forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Map k v)
    forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Map k v -> c (Map k v)
    forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Map k v))
    forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
    $cgfoldl :: forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Map k v -> c (Map k v)
    gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Map k v -> c (Map k v)
    $cgunfold :: forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Map k v)
    gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Map k v)
    $ctoConstr :: forall k v. (Data k, Data v, Ord k) => Map k v -> Constr
    toConstr :: Map k v -> Constr
    $cdataTypeOf :: forall k v. (Data k, Data v, Ord k) => Map k v -> DataType
    dataTypeOf :: Map k v -> DataType
    $cdataCast1 :: forall k v (t :: * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (Map k v))
    dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Map k v))
    $cdataCast2 :: forall k v (t :: * -> * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
    dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
    $cgmapT :: forall k v.
    (Data k, Data v, Ord k) =>
    (forall b. Data b => b -> b) -> Map k v -> Map k v
    gmapT :: (forall b. Data b => b -> b) -> Map k v -> Map k v
    $cgmapQl :: forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    gmapQl :: forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    $cgmapQr :: forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    gmapQr :: forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r
    $cgmapQ :: forall k v u.
    (Data k, Data v, Ord k) =>
    (forall d. Data d => d -> u) -> Map k v -> [u]
    gmapQ :: forall u. (forall d. Data d => d -> u) -> Map k v -> [u]
    $cgmapQi :: forall k v u.
    (Data k, Data v, Ord k) =>
    Int -> (forall d. Data d => d -> u) -> Map k v -> u
    gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u
    $cgmapM :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, Monad m) =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    gmapM :: forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    $cgmapMp :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    gmapMp :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    $cgmapMo :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    gmapMo :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
    Data, (forall x. Map k v -> Rep (Map k v) x)
    -> (forall x. Rep (Map k v) x -> Map k v) -> Generic (Map k v)
    forall x. Rep (Map k v) x -> Map k v
    forall x. Map k v -> Rep (Map k v) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall k v x. Rep (Map k v) x -> Map k v
    forall k v x. Map k v -> Rep (Map k v) x
    $cfrom :: forall k v x. Map k v -> Rep (Map k v) x
    from :: forall x. Map k v -> Rep (Map k v) x
    $cto :: forall k v x. Rep (Map k v) x -> Map k v
    to :: forall x. Rep (Map k v) x -> Map k v
    Generic, (forall (m :: * -> *). Quote m => Map k v -> m Exp)
    -> (forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v))
    -> Lift (Map k v)
    forall k v (m :: * -> *).
    (Lift k, Lift v, Quote m) =>
    Map k v -> m Exp
    forall k v (m :: * -> *).
    (Lift k, Lift v, Quote m) =>
    Map k v -> Code m (Map k v)
    forall t.
    (forall (m :: * -> *). Quote m => t -> m Exp)
    -> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
    forall (m :: * -> *). Quote m => Map k v -> m Exp
    forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v)
    $clift :: forall k v (m :: * -> *).
    (Lift k, Lift v, Quote m) =>
    Map k v -> m Exp
    lift :: forall (m :: * -> *). Quote m => Map k v -> m Exp
    $cliftTyped :: forall k v (m :: * -> *).
    (Lift k, Lift v, Quote m) =>
    Map k v -> Code m (Map k v)
    liftTyped :: forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v)
    Lift, Map k v -> ()
    (Map k v -> ()) -> NFData (Map k v)
    forall a. (a -> ()) -> NFData a
    forall k v. (NFData k, NFData v) => Map k v -> ()
    $crnf :: forall k v. (NFData k, NFData v) => Map k v -> ()
    rnf :: Map k v -> ()
    NFData)

    data Keys a
        = Sorted
        | Original [a]
        deriving (Typeable (Keys a)
    Typeable (Keys a) =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> Keys a -> c (Keys a))
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c (Keys a))
    -> (Keys a -> Constr)
    -> (Keys a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c (Keys a)))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Keys a)))
    -> ((forall b. Data b => b -> b) -> Keys a -> Keys a)
    -> (forall r r'.
        (r -> r' -> r)
        -> r -> (forall d. Data d => d -> r') -> Keys a -> r)
    -> (forall r r'.
        (r' -> r -> r)
        -> r -> (forall d. Data d => d -> r') -> Keys a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> Keys a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> Keys a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> Keys a -> m (Keys a))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> Keys a -> m (Keys a))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> Keys a -> m (Keys a))
    -> Data (Keys a)
    Keys a -> Constr
    Keys a -> DataType
    (forall b. Data b => b -> b) -> Keys a -> Keys a
    forall a. Data a => Typeable (Keys a)
    forall a. Data a => Keys a -> Constr
    forall a. Data a => Keys a -> DataType
    forall a.
    Data a =>
    (forall b. Data b => b -> b) -> Keys a -> Keys a
    forall a u.
    Data a =>
    Int -> (forall d. Data d => d -> u) -> Keys a -> u
    forall a u. Data a => (forall d. Data d => d -> u) -> Keys a -> [u]
    forall a r r'.
    Data a =>
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    forall a r r'.
    Data a =>
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    forall a (m :: * -> *).
    (Data a, Monad m) =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    forall a (c :: * -> *).
    Data a =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Keys a)
    forall a (c :: * -> *).
    Data a =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Keys a -> c (Keys a)
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (Keys a))
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Keys a))
    forall a.
    Typeable a =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> a -> c a)
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c a)
    -> (a -> Constr)
    -> (a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c a))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
    -> ((forall b. Data b => b -> b) -> a -> a)
    -> (forall r r'.
        (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall r r'.
        (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> Data a
    forall u. Int -> (forall d. Data d => d -> u) -> Keys a -> u
    forall u. (forall d. Data d => d -> u) -> Keys a -> [u]
    forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Keys a)
    forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Keys a -> c (Keys a)
    forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Keys a))
    forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Keys a))
    $cgfoldl :: forall a (c :: * -> *).
    Data a =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Keys a -> c (Keys a)
    gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Keys a -> c (Keys a)
    $cgunfold :: forall a (c :: * -> *).
    Data a =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Keys a)
    gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Keys a)
    $ctoConstr :: forall a. Data a => Keys a -> Constr
    toConstr :: Keys a -> Constr
    $cdataTypeOf :: forall a. Data a => Keys a -> DataType
    dataTypeOf :: Keys a -> DataType
    $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (Keys a))
    dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Keys a))
    $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Keys a))
    dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Keys a))
    $cgmapT :: forall a.
    Data a =>
    (forall b. Data b => b -> b) -> Keys a -> Keys a
    gmapT :: (forall b. Data b => b -> b) -> Keys a -> Keys a
    $cgmapQl :: forall a r r'.
    Data a =>
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    gmapQl :: forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    $cgmapQr :: forall a r r'.
    Data a =>
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    gmapQr :: forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
    $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Keys a -> [u]
    gmapQ :: forall u. (forall d. Data d => d -> u) -> Keys a -> [u]
    $cgmapQi :: forall a u.
    Data a =>
    Int -> (forall d. Data d => d -> u) -> Keys a -> u
    gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Keys a -> u
    $cgmapM :: forall a (m :: * -> *).
    (Data a, Monad m) =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    gmapM :: forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    $cgmapMp :: forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    gmapMp :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    $cgmapMo :: forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    gmapMo :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
    Data, (forall x. Keys a -> Rep (Keys a) x)
    -> (forall x. Rep (Keys a) x -> Keys a) -> Generic (Keys a)
    forall x. Rep (Keys a) x -> Keys a
    forall x. Keys a -> Rep (Keys a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall a x. Rep (Keys a) x -> Keys a
    forall a x. Keys a -> Rep (Keys a) x
    $cfrom :: forall a x. Keys a -> Rep (Keys a) x
    from :: forall x. Keys a -> Rep (Keys a) x
    $cto :: forall a x. Rep (Keys a) x -> Keys a
    to :: forall x. Rep (Keys a) x -> Keys a
    Generic, (forall (m :: * -> *). Quote m => Keys a -> m Exp)
    -> (forall (m :: * -> *). Quote m => Keys a -> Code m (Keys a))
    -> Lift (Keys a)
    forall a (m :: * -> *). (Lift a, Quote m) => Keys a -> m Exp
    forall a (m :: * -> *).
    (Lift a, Quote m) =>
    Keys a -> Code m (Keys a)
    forall t.
    (forall (m :: * -> *). Quote m => t -> m Exp)
    -> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
    forall (m :: * -> *). Quote m => Keys a -> m Exp
    forall (m :: * -> *). Quote m => Keys a -> Code m (Keys a)
    $clift :: forall a (m :: * -> *). (Lift a, Quote m) => Keys a -> m Exp
    lift :: forall (m :: * -> *). Quote m => Keys a -> m Exp
    $cliftTyped :: forall a (m :: * -> *).
    (Lift a, Quote m) =>
    Keys a -> Code m (Keys a)
    liftTyped :: forall (m :: * -> *). Quote m => Keys a -> Code m (Keys a)
    Lift, Keys a -> ()
    (Keys a -> ()) -> NFData (Keys a)
    forall a. NFData a => Keys a -> ()
    forall a. (a -> ()) -> NFData a
    $crnf :: forall a. NFData a => Keys a -> ()
    rnf :: Keys a -> ()
    NFData)

    instance (Ord k, Eq v) => Eq (Map k v) where
      Map k v
    m1 == :: Map k v -> Map k v -> Bool
    == Map k v
    m2 =
          Map k v -> Int
    forall k a. Map k a -> Int
    Data.Map.Strict.size (Map k v -> Map k v
    forall k v. Map k v -> Map k v
    toMap Map k v
    m1) Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Map k v -> Int
    forall k a. Map k a -> Int
    Data.Map.Strict.size (Map k v -> Map k v
    forall k v. Map k v -> Map k v
    toMap Map k v
    m2)
          Bool -> Bool -> Bool
    && Map k v -> [(k, v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k v
    m1 [(k, v)] -> [(k, v)] -> Bool
    forall a. Eq a => a -> a -> Bool
    == Map k v -> [(k, v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k v
    m2
      {-# INLINABLE (==) #-}

    {-|
    >>> fromList [("A",1),("B",2)] < fromList [("B",1),("A",0)]
    True
    -}
    instance (Ord k, Ord v) => Ord (Map k v) where
      compare :: Map k v -> Map k v -> Ordering
    compare Map k v
    m1 Map k v
    m2 = [(k, v)] -> [(k, v)] -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (Map k v -> [(k, v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k v
    m1) (Map k v -> [(k, v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k v
    m2)
      {-# INLINABLE compare #-}

    instance Functor (Map k) where
      fmap :: forall a b. (a -> b) -> Map k a -> Map k b
    fmap a -> b
    f (Map Map k a
    m Keys k
    ks) = Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map ((a -> b) -> Map k a -> Map k b
    forall a b. (a -> b) -> Map k a -> Map k b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f Map k a
    m) Keys k
    ks
      {-# INLINABLE fmap #-}

    instance Ord k => Foldable (Map k) where
      foldr :: forall a b. (a -> b -> b) -> b -> Map k a -> b
    foldr a -> b -> b
    f b
    z (Map Map k a
    m Keys k
    Sorted) = (a -> b -> b) -> b -> Map k a -> b
    forall a b. (a -> b -> b) -> b -> Map k a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    f b
    z Map k a
    m
      foldr a -> b -> b
    f b
    z Map k a
    m              = (a -> b -> b) -> b -> [a] -> b
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    f b
    z (Map k a -> [a]
    forall k v. Ord k => Map k v -> [v]
    elems Map k a
    m)
      {-# INLINABLE foldr #-}

      length :: forall a. Map k a -> Int
    length Map k a
    m = Map k a -> Int
    forall k v. Map k v -> Int
    size Map k a
    m
      {-# INLINABLE length #-}

      null :: forall a. Map k a -> Bool
    null (Map Map k a
    m Keys k
    _) = Map k a -> Bool
    forall a. Map k a -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null Map k a
    m
      {-# INLINABLE null #-}

    instance Ord k => Traversable (Map k) where
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Map k a -> f (Map k b)
    traverse a -> f b
    f Map k a
    m = (k -> a -> f b) -> Map k a -> f (Map k b)
    forall k (f :: * -> *) a b.
    (Ord k, Applicative f) =>
    (k -> a -> f b) -> Map k a -> f (Map k b)
    traverseWithKey (\k
    _ a
    v -> a -> f b
    f a
    v) Map k a
    m
      {-# INLINABLE traverse #-}

    {-|
    prop> \x y z -> x <> (y <> z) == (x <> y) <> (z :: Map Int Int)
    -}
    instance Ord k => Semigroup (Map k v) where
        <> :: Map k v -> Map k v -> Map k v
    (<>) = Map k v -> Map k v -> Map k v
    forall k v. Ord k => Map k v -> Map k v -> Map k v
    union
        {-# INLINABLE (<>) #-}

    {-|
    prop> \x -> x <> mempty == (x :: Map Int Int)
    prop> \x -> mempty <> x == (x :: Map Int Int)
    -}
    instance Ord k => Monoid (Map k v) where
        mempty :: Map k v
    mempty = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    forall k a. Map k a
    Data.Map.Strict.empty ([k] -> Keys k
    forall a. [a] -> Keys a
    Original [])
        {-# INLINABLE mempty #-}

    instance (Show k, Show v, Ord k) => Show (Map k v) where
        showsPrec :: Int -> Map k v -> ShowS
    showsPrec Int
    d Map k v
    m =
            Bool -> ShowS -> ShowS
    showParen (Int
    d Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    10) (String -> ShowS
    showString String
    "fromList " ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> [(k, v)] -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec Int
    11 [(k, v)]
    kvs)
          where
            kvs :: [(k, v)]
    kvs = Map k v -> [(k, v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k v
    m

    instance Ord k => GHC.Exts.IsList (Map k v) where
        type Item (Map k v) = (k, v)

        fromList :: [Item (Map k v)] -> Map k v
    fromList = [(k, v)] -> Map k v
    [Item (Map k v)] -> Map k v
    forall k v. Ord k => [(k, v)] -> Map k v
    Dhall.Map.fromList

        toList :: Map k v -> [Item (Map k v)]
    toList = Map k v -> [(k, v)]
    Map k v -> [Item (Map k v)]
    forall k v. Ord k => Map k v -> [(k, v)]
    Dhall.Map.toList

    instance Ord k => Foldable.WithIndex.FoldableWithIndex k (Map k) where
        ifoldMap :: forall m a. Monoid m => (k -> a -> m) -> Map k a -> m
    ifoldMap = (k -> a -> m) -> Map k a -> m
    forall m k a. (Monoid m, Ord k) => (k -> a -> m) -> Map k a -> m
    foldMapWithKey
        {-# INLINABLE ifoldMap #-}

    instance Functor.WithIndex.FunctorWithIndex k (Map k) where
        imap :: forall a b. (k -> a -> b) -> Map k a -> Map k b
    imap = (k -> a -> b) -> Map k a -> Map k b
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    mapWithKey
        {-# INLINABLE imap #-}

    instance Ord k => Traversable.WithIndex.TraversableWithIndex k (Map k) where
        itraverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (k -> a -> f b) -> Map k a -> f (Map k b)
    itraverse = (k -> a -> f b) -> Map k a -> f (Map k b)
    forall k (f :: * -> *) a b.
    (Ord k, Applicative f) =>
    (k -> a -> f b) -> Map k a -> f (Map k b)
    traverseWithKey
        {-# INLINABLE itraverse #-}

    -- | Create an empty `Map`
    empty :: Ord k => Map k v
    empty :: forall k v. Ord k => Map k v
    empty = Map k v
    forall a. Monoid a => a
    mempty

    {-| Create a `Map` from a single key-value pair

    >>> singleton "A" 1
    fromList [("A",1)]
    -}
    singleton :: k -> v -> Map k v
    singleton :: forall k v. k -> v -> Map k v
    singleton k
    k v
    v = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    ks
      where
        m :: Map k v
    m = k -> v -> Map k v
    forall k a. k -> a -> Map k a
    Data.Map.Strict.singleton k
    k v
    v

        ks :: Keys k
    ks = [k] -> Keys k
    forall a. [a] -> Keys a
    Original [k
    k]
    {-# INLINABLE singleton #-}

    {-| Create a `Map` from a list of key-value pairs

    >>> fromList [("B",1),("A",2)]  -- The map preserves order
    fromList [("B",1),("A",2)]
    >>> fromList [("A",1),("A",2)]  -- For duplicates, later values take precedence
    fromList [("A",2)]

    Note that this handling of duplicates means that 'fromList' is /not/ a monoid
    homomorphism:

    >>> fromList [(1, True)] <> fromList [(1, False)]
    fromList [(1,True)]
    >>> fromList ([(1, True)] <> [(1, False)])
    fromList [(1,False)]

    -}
    fromList :: Ord k => [(k, v)] -> Map k v
    fromList :: forall k v. Ord k => [(k, v)] -> Map k v
    fromList [(k, v)]
    kvs = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    ks
      where
        m :: Map k v
    m = [(k, v)] -> Map k v
    forall k a. Ord k => [(k, a)] -> Map k a
    Data.Map.Strict.fromList [(k, v)]
    kvs

        ks :: Keys k
    ks = [k] -> Keys k
    forall a. [a] -> Keys a
    Original ([k] -> [k]
    forall k. Ord k => [k] -> [k]
    nubOrd (((k, v) -> k) -> [(k, v)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> k
    forall a b. (a, b) -> a
    fst [(k, v)]
    kvs))
    {-# INLINABLE fromList #-}

    {-| Create a `Map` from a list of key-value pairs with a combining function.

    >>> fromListWithKey (\k v1 v2 -> k ++ v1 ++ v2) [("B","v1"),("A","v2"),("B","v3")]
    fromList [("B","Bv3v1"),("A","v2")]
    -}
    fromListWithKey :: Ord k => (k -> v -> v -> v) -> [(k, v)] -> Map k v
    fromListWithKey :: forall k v. Ord k => (k -> v -> v -> v) -> [(k, v)] -> Map k v
    fromListWithKey k -> v -> v -> v
    f [(k, v)]
    kvs = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    ks
      where
        m :: Map k v
    m = (k -> v -> v -> v) -> [(k, v)] -> Map k v
    forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
    Data.Map.Strict.fromListWithKey k -> v -> v -> v
    f [(k, v)]
    kvs

        ks :: Keys k
    ks = [k] -> Keys k
    forall a. [a] -> Keys a
    Original ([k] -> [k]
    forall k. Ord k => [k] -> [k]
    nubOrd (((k, v) -> k) -> [(k, v)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> k
    forall a b. (a, b) -> a
    fst [(k, v)]
    kvs))
    {-# INLINABLE fromListWithKey #-}

    -- | Create a `Map` from a @"Data.Map.Strict".`Data.Map.Strict.Map`@
    fromMap :: Data.Map.Strict.Map k v -> Map k v
    fromMap :: forall k v. Map k v -> Map k v
    fromMap Map k v
    m = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    forall a. Keys a
    Sorted

    {-| Remove duplicates from a  list

    >>> nubOrd [1,2,3]
    [1,2,3]
    >>> nubOrd [1,1,3]
    [1,3]
    -}
    nubOrd :: Ord k => [k] -> [k]
    nubOrd :: forall k. Ord k => [k] -> [k]
    nubOrd = Set k -> [k] -> [k]
    forall {a}. Ord a => Set a -> [a] -> [a]
    go Set k
    forall a. Set a
    Data.Set.empty
      where
        go :: Set a -> [a] -> [a]
    go Set a
    _      []  = []
        go Set a
    set (a
    k:[a]
    ks)
            | a -> Set a -> Bool
    forall a. Ord a => a -> Set a -> Bool
    Data.Set.member a
    k Set a
    set =     Set a -> [a] -> [a]
    go                    Set a
    set  [a]
    ks
            | Bool
    otherwise             = a
    k a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : Set a -> [a] -> [a]
    go (a -> Set a -> Set a
    forall a. Ord a => a -> Set a -> Set a
    Data.Set.insert a
    k Set a
    set) [a]
    ks
    {-# INLINABLE nubOrd #-}

    {-| Create a `Map` from a single key-value pair.

        Any further operations on this map will not retain the order of the keys.

    >>> unorderedSingleton "A" 1
    fromList [("A",1)]
    -}
    unorderedSingleton :: k -> v -> Map k v
    unorderedSingleton :: forall k v. k -> v -> Map k v
    unorderedSingleton k
    k v
    v = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    forall a. Keys a
    Sorted
      where
        m :: Map k v
    m = k -> v -> Map k v
    forall k a. k -> a -> Map k a
    Data.Map.Strict.singleton k
    k v
    v
    {-# INLINABLE unorderedSingleton #-}

    {-| Create a `Map` from a list of key-value pairs

        Any further operations on this map will not retain the order of the keys.

    >>> unorderedFromList []
    fromList []
    >>> unorderedFromList [("B",1),("A",2)]  -- The map /doesn't/ preserve order
    fromList [("A",2),("B",1)]
    >>> unorderedFromList [("A",1),("A",2)]  -- For duplicates, later values take precedence
    fromList [("A",2)]
    -}
    unorderedFromList :: Ord k => [(k, v)] -> Map k v
    unorderedFromList :: forall k v. Ord k => [(k, v)] -> Map k v
    unorderedFromList [(k, v)]
    kvs = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    forall a. Keys a
    Sorted
      where
        m :: Map k v
    m = [(k, v)] -> Map k v
    forall k a. Ord k => [(k, a)] -> Map k a
    Data.Map.Strict.fromList [(k, v)]
    kvs
    {-# INLINABLE unorderedFromList #-}

    {-| Sort the keys of a `Map`, forgetting the original ordering

    > sort (sort x) = sort x

    >>> sort (fromList [("B",1),("A",2)])
    fromList [("A",2),("B",1)]
    -}
    sort :: Map k v -> Map k v
    sort :: forall k v. Map k v -> Map k v
    sort (Map Map k v
    m Keys k
    _) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    forall a. Keys a
    Sorted
    {-# INLINABLE sort #-}

    {-| Check if the keys of a `Map` are already sorted

    > isSorted (sort m) = True

    >>> isSorted (fromList [("B",1),("A",2)])  -- Sortedness is based only on keys
    False
    >>> isSorted (fromList [("A",2),("B",1)])
    True
    -}
    isSorted :: Eq k => Map k v -> Bool
    isSorted :: forall k v. Eq k => Map k v -> Bool
    isSorted (Map Map k v
    _ Keys k
    Sorted)        = Bool
    True
    isSorted (Map Map k v
    m (Original [k]
    ks)) = Map k v -> [k]
    forall k a. Map k a -> [k]
    Data.Map.Strict.keys Map k v
    m [k] -> [k] -> Bool
    forall a. Eq a => a -> a -> Bool
    == [k]
    ks -- Or shortcut to False here?
    {-# INLINABLE isSorted #-}

    {-| Insert a key-value pair into a `Map`, overriding any previous value stored
        underneath the same key, if present

    > insert = insertWith (\v _ -> v)

    >>> insert "C" 1 (fromList [("B",2),("A",3)])  -- Values are inserted on left
    fromList [("C",1),("B",2),("A",3)]
    >>> insert "C" 1 (fromList [("C",2),("A",3)])  -- New value takes precedence
    fromList [("C",1),("A",3)]
    -}
    insert :: Ord k => k -> v -> Map k v -> Map k v
    insert :: forall k v. Ord k => k -> v -> Map k v -> Map k v
    insert k
    k v
    v (Map Map k v
    m Keys k
    Sorted)        = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map (k -> v -> Map k v -> Map k v
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Data.Map.Strict.insert k
    k v
    v Map k v
    m) Keys k
    forall a. Keys a
    Sorted
    insert k
    k v
    v (Map Map k v
    m (Original [k]
    ks)) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m' ([k] -> Keys k
    forall a. [a] -> Keys a
    Original [k]
    ks')
      where
        (Maybe v
    mayOldV, Map k v
    m') = (k -> v -> v -> v) -> k -> v -> Map k v -> (Maybe v, Map k v)
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
    Data.Map.Strict.insertLookupWithKey (\k
    _k v
    new v
    _old -> v
    new) k
    k v
    v Map k v
    m

        ks' :: [k]
    ks' | Just v
    _ <- Maybe v
    mayOldV = [k]
    ks
            | Bool
    otherwise         = k
    k k -> [k] -> [k]
    forall a. a -> [a] -> [a]
    : [k]
    ks
    {-# INLINABLE insert #-}

    {-| Insert a key-value pair into a `Map`, using the supplied function to combine
        the new value with any old value underneath the same key, if present

    >>> insertWith (+) "C" 1 (fromList [("B",2),("A",3)])  -- No collision
    fromList [("C",1),("B",2),("A",3)]
    >>> insertWith (+) "C" 1 (fromList [("C",2),("A",3)])  -- Collision
    fromList [("C",3),("A",3)]
    -}
    insertWith :: Ord k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
    insertWith :: forall k v. Ord k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
    insertWith v -> v -> v
    f k
    k v
    v (Map Map k v
    m Keys k
    Sorted)        = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map ((v -> v -> v) -> k -> v -> Map k v -> Map k v
    forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
    Data.Map.Strict.insertWith v -> v -> v
    f k
    k v
    v Map k v
    m) Keys k
    forall a. Keys a
    Sorted
    insertWith v -> v -> v
    f k
    k v
    v (Map Map k v
    m (Original [k]
    ks)) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m' ([k] -> Keys k
    forall a. [a] -> Keys a
    Original [k]
    ks')
      where
        (Maybe v
    mayOldV, Map k v
    m') = (k -> v -> v -> v) -> k -> v -> Map k v -> (Maybe v, Map k v)
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
    Data.Map.Strict.insertLookupWithKey (\k
    _k v
    new v
    old -> v -> v -> v
    f v
    new v
    old) k
    k v
    v Map k v
    m

        ks' :: [k]
    ks' | Just v
    _ <- Maybe v
    mayOldV = [k]
    ks
            | Bool
    otherwise         = k
    k k -> [k] -> [k]
    forall a. a -> [a] -> [a]
    : [k]
    ks
    {-# INLINABLE insertWith #-}

    {-| Delete a key from a `Map` if present, otherwise return the original `Map`

    >>> delete "B" (fromList [("C",1),("B",2),("A",3)])
    fromList [("C",1),("A",3)]
    >>> delete "D" (fromList [("C",1),("B",2),("A",3)])
    fromList [("C",1),("B",2),("A",3)]
    -}
    delete :: Ord k => k -> Map k v -> Map k v
    delete :: forall k v. Ord k => k -> Map k v -> Map k v
    delete k
    k (Map Map k v
    m Keys k
    ks) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m' Keys k
    ks'
      where
        m' :: Map k v
    m' = k -> Map k v -> Map k v
    forall k a. Ord k => k -> Map k a -> Map k a
    Data.Map.Strict.delete k
    k Map k v
    m

        ks' :: Keys k
    ks' = case Keys k
    ks of
            Keys k
    Sorted        -> Keys k
    forall a. Keys a
    Sorted
            Original [k]
    ks'' -> [k] -> Keys k
    forall a. [a] -> Keys a
    Original (k -> [k] -> [k]
    forall a. Eq a => a -> [a] -> [a]
    Data.List.delete k
    k [k]
    ks'')
    {-# INLINABLE delete #-}

    {-| Keep all values that satisfy the given predicate

    >>> filter even (fromList [("C",3),("B",2),("A",1)])
    fromList [("B",2)]
    >>> filter odd (fromList [("C",3),("B",2),("A",1)])
    fromList [("C",3),("A",1)]
    -}
    filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
    filter :: forall k a. Ord k => (a -> Bool) -> Map k a -> Map k a
    filter a -> Bool
    predicate (Map Map k a
    m Keys k
    ks) = Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    m' Keys k
    ks'
      where
        m' :: Map k a
    m' = (a -> Bool) -> Map k a -> Map k a
    forall a k. (a -> Bool) -> Map k a -> Map k a
    Data.Map.Strict.filter a -> Bool
    predicate Map k a
    m

        ks' :: Keys k
    ks' = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k a
    m') Keys k
    ks
    {-# INLINABLE filter #-}

    {-| Split the map into values that do and don't satisfy the predicate

    >>> partition even (fromList [("C",3),("B",2),("A",1)])
    (fromList [("B",2)],fromList [("C",3),("A",1)])
    >>> partition odd (fromList [("C",3),("B",2),("A",1)])
    (fromList [("C",3),("A",1)],fromList [("B",2)])
    -}
    partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
    partition :: forall k a. Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
    partition a -> Bool
    predicate (Map Map k a
    m Keys k
    ks) = (Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    mpass Keys k
    kpass, Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    mfail Keys k
    kfail)
      where
        (Map k a
    mpass, Map k a
    mfail) = (a -> Bool) -> Map k a -> (Map k a, Map k a)
    forall a k. (a -> Bool) -> Map k a -> (Map k a, Map k a)
    Data.Map.Strict.partition a -> Bool
    predicate Map k a
    m

        (Keys k
    kpass, Keys k
    kfail) = (k -> Bool) -> Keys k -> (Keys k, Keys k)
    forall a. (a -> Bool) -> Keys a -> (Keys a, Keys a)
    partitionKeys (\k
    k -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k a
    mpass) Keys k
    ks
    {-# INLINABLE partition #-}

    {-| Restrict a 'Map' to only those keys found in a @"Data.Set".'Data.Set.Set'@.

    >>> restrictKeys (fromList [("A",1),("B",2)]) (Data.Set.fromList ["A"])
    fromList [("A",1)]
    -}
    restrictKeys :: Ord k => Map k a -> Data.Set.Set k -> Map k a
    restrictKeys :: forall k a. Ord k => Map k a -> Set k -> Map k a
    restrictKeys (Map Map k a
    m Keys k
    ks) Set k
    s = Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    m' Keys k
    ks'
      where
        m' :: Map k a
    m' = Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    Data.Map.Strict.restrictKeys Map k a
    m Set k
    s

        ks' :: Keys k
    ks' = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Set k -> Bool
    forall a. Ord a => a -> Set a -> Bool
    Data.Set.member k
    k Set k
    s) Keys k
    ks
    {-# INLINABLE restrictKeys #-}

    {-| Remove all keys in a @"Data.Set".'Data.Set.Set'@ from a 'Map'

    >>> withoutKeys (fromList [("A",1),("B",2)]) (Data.Set.fromList ["A"])
    fromList [("B",2)]
    -}
    withoutKeys :: Ord k => Map k a -> Data.Set.Set k -> Map k a
    withoutKeys :: forall k a. Ord k => Map k a -> Set k -> Map k a
    withoutKeys (Map Map k a
    m Keys k
    ks) Set k
    s = Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    m' Keys k
    ks'
      where
        m' :: Map k a
    m' = Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    Data.Map.Strict.withoutKeys Map k a
    m Set k
    s

        ks' :: Keys k
    ks' = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Set k -> Bool
    forall a. Ord a => a -> Set a -> Bool
    Data.Set.notMember k
    k Set k
    s) Keys k
    ks
    {-# INLINABLE withoutKeys #-}

    {-| Transform all values in a `Map` using the supplied function, deleting the
        key if the function returns `Nothing`

    >>> mapMaybe Data.Maybe.listToMaybe (fromList [("C",[1]),("B",[]),("A",[3])])
    fromList [("C",1),("A",3)]
    -}
    mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b
    mapMaybe :: forall k a b. Ord k => (a -> Maybe b) -> Map k a -> Map k b
    mapMaybe a -> Maybe b
    f (Map Map k a
    m Keys k
    ks) = Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k b
    m' Keys k
    ks'
      where
        m' :: Map k b
    m' = (a -> Maybe b) -> Map k a -> Map k b
    forall a b k. (a -> Maybe b) -> Map k a -> Map k b
    Data.Map.Strict.mapMaybe a -> Maybe b
    f Map k a
    m

        ks' :: Keys k
    ks' = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Map k b -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k b
    m') Keys k
    ks
    {-# INLINABLE mapMaybe #-}

    {-| Retrieve a key from a `Map`

    > lookup k mempty = empty
    >
    > lookup k (x <> y) = lookup k y <|> lookup k x

    >>> lookup "A" (fromList [("B",1),("A",2)])
    Just 2
    >>> lookup "C" (fromList [("B",1),("A",2)])
    Nothing
    -}
    lookup :: Ord k => k -> Map k v -> Maybe v
    lookup :: forall k v. Ord k => k -> Map k v -> Maybe v
    lookup k
    k (Map Map k v
    m Keys k
    _) = k -> Map k v -> Maybe v
    forall k a. Ord k => k -> Map k a -> Maybe a
    Data.Map.Strict.lookup k
    k Map k v
    m
    {-# INLINABLE lookup #-}

    {-| Retrieve the first key, value of the 'Map', if present,
        and also returning the rest of the 'Map'.

    > uncons mempty = empty
    >
    > uncons (singleton k v) = (k, v, mempty)

    >>> uncons (fromList [("C",1),("B",2),("A",3)])
    Just ("C",1,fromList [("B",2),("A",3)])
    >>> uncons (fromList [])
    Nothing
    -}
    uncons :: Ord k => Map k v -> Maybe (k, v, Map k v)
    uncons :: forall k v. Ord k => Map k v -> Maybe (k, v, Map k v)
    uncons (Map Map k v
    _ (Original []))     = Maybe (k, v, Map k v)
    forall a. Maybe a
    Nothing
    uncons (Map Map k v
    m (Original (k
    k:[k]
    ks))) =
        (k, v, Map k v) -> Maybe (k, v, Map k v)
    forall a. a -> Maybe a
    Just (k
    k, Map k v
    m Map k v -> k -> v
    forall k a. Ord k => Map k a -> k -> a
    Data.Map.Strict.! k
    k, Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map (k -> Map k v -> Map k v
    forall k a. Ord k => k -> Map k a -> Map k a
    Data.Map.Strict.delete k
    k Map k v
    m) ([k] -> Keys k
    forall a. [a] -> Keys a
    Original [k]
    ks))
    uncons (Map Map k v
    m Keys k
    Sorted)
      | Just ((k
    k, v
    v), Map k v
    m') <- Map k v -> Maybe ((k, v), Map k v)
    forall k a. Map k a -> Maybe ((k, a), Map k a)
    Data.Map.Strict.minViewWithKey Map k v
    m = (k, v, Map k v) -> Maybe (k, v, Map k v)
    forall a. a -> Maybe a
    Just (k
    k, v
    v, Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m' Keys k
    forall a. Keys a
    Sorted)
      | Bool
    otherwise                                      = Maybe (k, v, Map k v)
    forall a. Maybe a
    Nothing
    {-# INLINABLE uncons #-}

    {-| Check if a key belongs to a `Map`

    > member k mempty = False
    >
    > member k (x <> y) = member k x || member k y

    >>> member "A" (fromList [("B",1),("A",2)])
    True
    >>> member "C" (fromList [("B",1),("A",2)])
    False
    -}
    member :: Ord k => k -> Map k v -> Bool
    member :: forall k v. Ord k => k -> Map k v -> Bool
    member k
    k (Map Map k v
    m Keys k
    _) = k -> Map k v -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k v
    m
    {-# INLINABLE member #-}

    {-|
    >>> size (fromList [("A",1)])
    1
    -}
    size :: Map k v -> Int
    size :: forall k v. Map k v -> Int
    size (Map Map k v
    m Keys k
    _) = Map k v -> Int
    forall k a. Map k a -> Int
    Data.Map.Strict.size Map k v
    m
    {-# INLINABLE size #-}

    {-| Combine two `Map`s, preferring keys from the first `Map`

    > union = unionWith (\v _ -> v)

    >>> union (fromList [("D",1),("C",2)]) (fromList [("B",3),("A",4)])
    fromList [("D",1),("C",2),("B",3),("A",4)]
    >>> union (fromList [("D",1),("C",2)]) (fromList [("C",3),("A",4)])
    fromList [("D",1),("C",2),("A",4)]
    -}
    union :: Ord k => Map k v -> Map k v -> Map k v
    union :: forall k v. Ord k => Map k v -> Map k v -> Map k v
    union (Map Map k v
    mL Keys k
    ksL) (Map Map k v
    mR Keys k
    ksR) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    ks
      where
        m :: Map k v
    m = Map k v -> Map k v -> Map k v
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    Data.Map.Strict.union Map k v
    mL Map k v
    mR

        ks :: Keys k
    ks = case (Keys k
    ksL, Keys k
    ksR) of
            (Original [k]
    l, Original [k]
    r) -> [k] -> Keys k
    forall a. [a] -> Keys a
    Original ([k] -> Keys k) -> [k] -> Keys k
    forall a b. (a -> b) -> a -> b
    $
                [k]
    l [k] -> [k] -> [k]
    forall a. [a] -> [a] -> [a]
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (k -> Bool) -> [k] -> [k]
    forall a. (a -> Bool) -> [a] -> [a]
    Prelude.filter (\k
    k -> k -> Map k v -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.notMember k
    k Map k v
    mL) [k]
    r
            (Keys k, Keys k)
    _                        -> Keys k
    forall a. Keys a
    Sorted
    {-# INLINABLE union #-}

    {-| Combine two `Map`s using a combining function for colliding keys

    >>> unionWith (+) (fromList [("D",1),("C",2)]) (fromList [("B",3),("A",4)])
    fromList [("D",1),("C",2),("B",3),("A",4)]
    >>> unionWith (+) (fromList [("D",1),("C",2)]) (fromList [("C",3),("A",4)])
    fromList [("D",1),("C",5),("A",4)]
    -}
    unionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
    unionWith :: forall k v. Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
    unionWith v -> v -> v
    combine (Map Map k v
    mL Keys k
    ksL) (Map Map k v
    mR Keys k
    ksR) = Map k v -> Keys k -> Map k v
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k v
    m Keys k
    ks
      where
        m :: Map k v
    m = (v -> v -> v) -> Map k v -> Map k v -> Map k v
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    Data.Map.Strict.unionWith v -> v -> v
    combine Map k v
    mL Map k v
    mR

        ks :: Keys k
    ks = case (Keys k
    ksL, Keys k
    ksR) of
            (Original [k]
    l, Original [k]
    r) -> [k] -> Keys k
    forall a. [a] -> Keys a
    Original ([k] -> Keys k) -> [k] -> Keys k
    forall a b. (a -> b) -> a -> b
    $
                [k]
    l [k] -> [k] -> [k]
    forall a. [a] -> [a] -> [a]
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (k -> Bool) -> [k] -> [k]
    forall a. (a -> Bool) -> [a] -> [a]
    Prelude.filter (\k
    k -> k -> Map k v -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.notMember k
    k Map k v
    mL) [k]
    r
            (Keys k, Keys k)
    _                        -> Keys k
    forall a. Keys a
    Sorted
    {-# INLINABLE unionWith #-}

    {-| A generalised 'unionWith'.

    >>> outerJoin Left Left (\k a b -> Right (k, a, b)) (fromList [("A",1),("B",2)]) (singleton "A" 3)
    fromList [("A",Right ("A",1,3)),("B",Left 2)]

    This function is much inspired by the "Data.Semialign.Semialign" class.
    -}
    outerJoin
        :: Ord k
        => (a -> c)
        -> (b -> c)
        -> (k -> a -> b -> c)
        -> Map k a
        -> Map k b
        -> Map k c
    outerJoin :: forall k a c b.
    Ord k =>
    (a -> c)
    -> (b -> c) -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    outerJoin a -> c
    fa b -> c
    fb k -> a -> b -> c
    fab (Map Map k a
    ma Keys k
    ksA) (Map Map k b
    mb Keys k
    ksB) = Map k c -> Keys k -> Map k c
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k c
    m Keys k
    ks
      where
        m :: Map k c
    m = (k -> a -> b -> Maybe c)
    -> (Map k a -> Map k c)
    -> (Map k b -> Map k c)
    -> Map k a
    -> Map k b
    -> Map k c
    forall k a b c.
    Ord k =>
    (k -> a -> b -> Maybe c)
    -> (Map k a -> Map k c)
    -> (Map k b -> Map k c)
    -> Map k a
    -> Map k b
    -> Map k c
    Data.Map.Strict.mergeWithKey
                (\k
    k a
    a b
    b -> c -> Maybe c
    forall a. a -> Maybe a
    Just (k -> a -> b -> c
    fab k
    k a
    a b
    b))
                ((a -> c) -> Map k a -> Map k c
    forall a b. (a -> b) -> Map k a -> Map k b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> c
    fa)
                ((b -> c) -> Map k b -> Map k c
    forall a b. (a -> b) -> Map k a -> Map k b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap b -> c
    fb)
                Map k a
    ma
                Map k b
    mb

        ks :: Keys k
    ks = case (Keys k
    ksA, Keys k
    ksB) of
            (Original [k]
    l, Original [k]
    r) -> [k] -> Keys k
    forall a. [a] -> Keys a
    Original ([k] -> Keys k) -> [k] -> Keys k
    forall a b. (a -> b) -> a -> b
    $
                [k]
    l [k] -> [k] -> [k]
    forall a. [a] -> [a] -> [a]
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (k -> Bool) -> [k] -> [k]
    forall a. (a -> Bool) -> [a] -> [a]
    Prelude.filter (\k
    k -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.notMember k
    k Map k a
    ma) [k]
    r
            (Keys k, Keys k)
    _                        -> Keys k
    forall a. Keys a
    Sorted
    {-# INLINABLE outerJoin #-}

    {-| Combine two `Map` on their shared keys, keeping the value from the first
        `Map`

    > intersection = intersectionWith (\v _ -> v)

    >>> intersection (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])
    fromList [("B",2)]
    -}
    intersection :: Ord k => Map k a -> Map k b -> Map k a
    intersection :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
    intersection (Map Map k a
    mL Keys k
    ksL) (Map Map k b
    mR Keys k
    _) = Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    m Keys k
    ks
      where
        m :: Map k a
    m = Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    Data.Map.Strict.intersection Map k a
    mL Map k b
    mR

        -- Or forget order unless both maps are ordered?!
        ks :: Keys k
    ks = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k a
    m) Keys k
    ksL
    {-# INLINABLE intersection #-}

    {-| Combine two `Map`s on their shared keys, using the supplied function to
        combine values from the first and second `Map`

    >>> intersectionWith (+) (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])
    fromList [("B",5)]
    -}
    intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
    intersectionWith :: forall k a b c.
    Ord k =>
    (a -> b -> c) -> Map k a -> Map k b -> Map k c
    intersectionWith a -> b -> c
    combine (Map Map k a
    mL Keys k
    ksL) (Map Map k b
    mR Keys k
    _) = Map k c -> Keys k -> Map k c
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k c
    m Keys k
    ks
      where
        m :: Map k c
    m = (a -> b -> c) -> Map k a -> Map k b -> Map k c
    forall k a b c.
    Ord k =>
    (a -> b -> c) -> Map k a -> Map k b -> Map k c
    Data.Map.Strict.intersectionWith a -> b -> c
    combine Map k a
    mL Map k b
    mR

        -- Or forget order unless both maps are ordered?!
        ks :: Keys k
    ks = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Map k c -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.member k
    k Map k c
    m) Keys k
    ksL
    {-# INLINABLE intersectionWith #-}

    {-| Compute the difference of two `Map`s by subtracting all keys from the
        second `Map` from the first `Map`

    >>> difference (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])
    fromList [("C",1)]
    -}
    difference :: Ord k => Map k a -> Map k b -> Map k a
    difference :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
    difference (Map Map k a
    mL Keys k
    ksL) (Map Map k b
    mR Keys k
    _) = Map k a -> Keys k -> Map k a
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k a
    m Keys k
    ks
      where
        m :: Map k a
    m = Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    Data.Map.Strict.difference Map k a
    mL Map k b
    mR

        ks :: Keys k
    ks = (k -> Bool) -> Keys k -> Keys k
    forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys (\k
    k -> k -> Map k b -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Data.Map.Strict.notMember k
    k Map k b
    mR) Keys k
    ksL
    {-# INLINABLE difference #-}

    {-| Fold all of the key-value pairs in a `Map`, in their original order

    >>> foldMapWithKey (,) (fromList [("B",[1]),("A",[2])])
    ("BA",[1,2])
    -}
    foldMapWithKey :: (Monoid m, Ord k) => (k -> a -> m) -> Map k a -> m
    foldMapWithKey :: forall m k a. (Monoid m, Ord k) => (k -> a -> m) -> Map k a -> m
    foldMapWithKey k -> a -> m
    f (Map Map k a
    m Keys k
    Sorted) = (k -> a -> m) -> Map k a -> m
    forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
    Data.Map.Strict.foldMapWithKey k -> a -> m
    f Map k a
    m
    foldMapWithKey k -> a -> m
    f Map k a
    m              = ((k, a) -> m) -> [(k, a)] -> m
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap ((k -> a -> m) -> (k, a) -> m
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry k -> a -> m
    f) (Map k a -> [(k, a)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k a
    m)
    {-# INLINABLE foldMapWithKey #-}

    {-| Transform the values of a `Map` using their corresponding key

    > mapWithKey (pure id) = id
    >
    > mapWithKey (liftA2 (.) f g) = mapWithKey f . mapWithKey g

    > mapWithKey f mempty = mempty
    >
    > mapWithKey f (x <> y) = mapWithKey f x <> mapWithKey f y

    >>> mapWithKey (,) (fromList [("B",1),("A",2)])
    fromList [("B",("B",1)),("A",("A",2))]
    -}
    mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
    mapWithKey :: forall k a b. (k -> a -> b) -> Map k a -> Map k b
    mapWithKey k -> a -> b
    f (Map Map k a
    m Keys k
    ks) = Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k b
    m' Keys k
    ks
      where
        m' :: Map k b
    m' = (k -> a -> b) -> Map k a -> Map k b
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    Data.Map.Strict.mapWithKey k -> a -> b
    f Map k a
    m
    {-# INLINABLE mapWithKey #-}

    {-| Traverse all of the key-value pairs in a `Map`, in their original order

    >>> traverseWithKey (,) (fromList [("B",1),("A",2)])
    ("BA",fromList [("B",1),("A",2)])
    -}
    traverseWithKey
        :: Ord k => Applicative f => (k -> a -> f b) -> Map k a -> f (Map k b)
    traverseWithKey :: forall k (f :: * -> *) a b.
    (Ord k, Applicative f) =>
    (k -> a -> f b) -> Map k a -> f (Map k b)
    traverseWithKey k -> a -> f b
    f (Map Map k a
    m Keys k
    Sorted) =
        (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (\Map k b
    m' -> Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k b
    m' Keys k
    forall a. Keys a
    Sorted) ((k -> a -> f b) -> Map k a -> f (Map k b)
    forall (t :: * -> *) k a b.
    Applicative t =>
    (k -> a -> t b) -> Map k a -> t (Map k b)
    Data.Map.Strict.traverseWithKey k -> a -> f b
    f Map k a
    m)
    traverseWithKey k -> a -> f b
    f m :: Map k a
    m@(Map Map k a
    _ Keys k
    ks) =
        (Map k b -> Keys k -> Map k b) -> Keys k -> Map k b -> Map k b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map Keys k
    ks (Map k b -> Map k b)
    -> ([(k, b)] -> Map k b) -> [(k, b)] -> Map k b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(k, b)] -> Map k b
    forall k a. Ord k => [(k, a)] -> Map k a
    Data.Map.Strict.fromList ([(k, b)] -> Map k b) -> f [(k, b)] -> f (Map k b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> ((k, a) -> f (k, b)) -> [(k, a)] -> f [(k, b)]
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    traverse (k, a) -> f (k, b)
    f' (Map k a -> [(k, a)]
    forall k v. Ord k => Map k v -> [(k, v)]
    toList Map k a
    m)
      where
        f' :: (k, a) -> f (k, b)
    f' (k
    k, a
    a) = (b -> (k, b)) -> f b -> f (k, b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((,) k
    k) (k -> a -> f b
    f k
    k a
    a)
    {-# INLINABLE traverseWithKey #-}

    {-| Same as `traverseWithKey`, except that the order of effects is not
        necessarily the same as the order of the keys
    -}
    unorderedTraverseWithKey
        :: Ord k => Applicative f => (k -> a -> f b) -> Map k a -> f (Map k b)
    unorderedTraverseWithKey :: forall k (f :: * -> *) a b.
    (Ord k, Applicative f) =>
    (k -> a -> f b) -> Map k a -> f (Map k b)
    unorderedTraverseWithKey k -> a -> f b
    f (Map Map k a
    m Keys k
    ks) =
        (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (\Map k b
    m' -> Map k b -> Keys k -> Map k b
    forall k v. Map k v -> Keys k -> Map k v
    Map Map k b
    m' Keys k
    ks) ((k -> a -> f b) -> Map k a -> f (Map k b)
    forall (t :: * -> *) k a b.
    Applicative t =>
    (k -> a -> t b) -> Map k a -> t (Map k b)
    Data.Map.Strict.traverseWithKey k -> a -> f b
    f Map k a
    m)
    {-# INLINABLE unorderedTraverseWithKey #-}

    {-| Traverse all of the key-value pairs in a 'Map', not preserving their
        original order, where the result of the computation can be forgotten.

        Note that this is a strict traversal, fully traversing the map even
        when the Applicative is lazy in the remaining elements.
    -}
    unorderedTraverseWithKey_
        :: Ord k => Applicative f => (k -> a -> f ()) -> Map k a -> f ()
    unorderedTraverseWithKey_ :: forall k (f :: * -> *) a.
    (Ord k, Applicative f) =>
    (k -> a -> f ()) -> Map k a -> f ()
    unorderedTraverseWithKey_ k -> a -> f ()
    f (Map Map k a
    m Keys k
    _) =
        (f () -> k -> a -> f ()) -> f () -> Map k a -> f ()
    forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
    Data.Map.Strict.foldlWithKey' (\f ()
    acc k
    k a
    v -> f ()
    acc f () -> f () -> f ()
    forall a b. f a -> f b -> f b
    forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
    *> k -> a -> f ()
    f k
    k a
    v) (() -> f ()
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ()) Map k a
    m
    {-# INLINABLE unorderedTraverseWithKey_ #-}

    {-| Convert a `Map` to a list of key-value pairs in the original order of keys

    >>> toList (fromList [("B",1),("A",2)])
    [("B",1),("A",2)]
    -}
    toList :: Ord k => Map k v -> [(k, v)]
    toList :: forall k v. Ord k => Map k v -> [(k, v)]
    toList (Map Map k v
    m Keys k
    Sorted)        = Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Data.Map.Strict.toList Map k v
    m
    toList (Map Map k v
    m (Original [k]
    ks)) = (k -> (k, v)) -> [k] -> [(k, v)]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (\k
    k -> (k
    k, Map k v
    m Map k v -> k -> v
    forall k a. Ord k => Map k a -> k -> a
    Data.Map.Strict.! k
    k)) [k]
    ks
    {-# INLINABLE toList #-}

    {-| Convert a `Map` to a list of key-value pairs in ascending order of keys
    -}
    toAscList :: Map k v -> [(k, v)]
    toAscList :: forall k v. Map k v -> [(k, v)]
    toAscList (Map Map k v
    m Keys k
    _) = Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Data.Map.Strict.toAscList Map k v
    m
    {-# INLINABLE toAscList #-}

    {-| Convert a @"Dhall.Map".`Map`@ to a @"Data.Map.Strict".`Data.Map.Strict.Map`@

    >>> toMap (fromList [("B",1),("A",2)]) -- Order is lost upon conversion
    fromList [("A",2),("B",1)]
    -}
    toMap :: Map k v -> Data.Map.Strict.Map k v
    toMap :: forall k v. Map k v -> Map k v
    toMap (Map Map k v
    m Keys k
    _) = Map k v
    m
    {-# INLINABLE toMap #-}

    {-| Return the keys from a `Map` in their original order

    >>> keys (fromList [("B",1),("A",2)])
    ["B","A"]
    -}
    keys :: Map k v -> [k]
    keys :: forall k v. Map k v -> [k]
    keys (Map Map k v
    m Keys k
    Sorted)        = Map k v -> [k]
    forall k a. Map k a -> [k]
    Data.Map.Strict.keys Map k v
    m
    keys (Map Map k v
    _ (Original [k]
    ks)) = [k]
    ks
    {-# INLINABLE keys #-}

    {-| Return the values from a `Map` in their original order.

    >>> elems (fromList [("B",1),("A",2)])
    [1,2]
    -}
    elems :: Ord k => Map k v -> [v]
    elems :: forall k v. Ord k => Map k v -> [v]
    elems (Map Map k v
    m Keys k
    Sorted)        = Map k v -> [v]
    forall k a. Map k a -> [a]
    Data.Map.Strict.elems Map k v
    m
    elems (Map Map k v
    m (Original [k]
    ks)) = (k -> v) -> [k] -> [v]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (\k
    k -> Map k v
    m Map k v -> k -> v
    forall k a. Ord k => Map k a -> k -> a
    Data.Map.Strict.! k
    k) [k]
    ks
    {-# INLINABLE elems #-}

    {-| Return the @"Data.Set".'Data.Set.Set'@ of the keys

    >>> keysSet (fromList [("B",1),("A",2)])
    fromList ["A","B"]
    -}
    keysSet :: Map k v -> Data.Set.Set k
    keysSet :: forall k v. Map k v -> Set k
    keysSet (Map Map k v
    m Keys k
    _) = Map k v -> Set k
    forall k a. Map k a -> Set k
    Data.Map.Strict.keysSet Map k v
    m
    {-# INLINABLE keysSet #-}

    filterKeys :: (a -> Bool) -> Keys a -> Keys a
    filterKeys :: forall a. (a -> Bool) -> Keys a -> Keys a
    filterKeys a -> Bool
    _ Keys a
    Sorted        = Keys a
    forall a. Keys a
    Sorted
    filterKeys a -> Bool
    f (Original [a]
    ks) = [a] -> Keys a
    forall a. [a] -> Keys a
    Original ((a -> Bool) -> [a] -> [a]
    forall a. (a -> Bool) -> [a] -> [a]
    Prelude.filter a -> Bool
    f [a]
    ks)
    {-# INLINABLE filterKeys #-}

    partitionKeys :: (a -> Bool) -> Keys a -> (Keys a, Keys a)
    partitionKeys :: forall a. (a -> Bool) -> Keys a -> (Keys a, Keys a)
    partitionKeys a -> Bool
    _ Keys a
    Sorted        = (Keys a
    forall a. Keys a
    Sorted, Keys a
    forall a. Keys a
    Sorted)
    partitionKeys a -> Bool
    f (Original [a]
    ks) =
        let ([a]
    kpass, [a]
    kfail) = (a -> Bool) -> [a] -> ([a], [a])
    forall a. (a -> Bool) -> [a] -> ([a], [a])
    Data.List.partition a -> Bool
    f [a]
    ks
        in ([a] -> Keys a
    forall a. [a] -> Keys a
    Original [a]
    kpass, [a] -> Keys a
    forall a. [a] -> Keys a
    Original [a]
    kfail)
    {-# INLINABLE partitionKeys #-}

    {- $setup
    >>> import Test.QuickCheck (Arbitrary(..), oneof)
    >>> :{
      instance (Ord k, Arbitrary k, Arbitrary v) => Arbitrary (Map k v) where
        arbitrary = oneof [fromList <$> arbitrary, unorderedFromList <$> arbitrary]
    :}
    -}