{-# LANGUAGE CPP                #-}
{-# LANGUAGE DeriveAnyClass     #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveGeneric      #-}
{-# LANGUAGE DeriveLift         #-}
{-# LANGUAGE DeriveTraversable  #-}
{-# LANGUAGE RecordWildCards    #-}
{-# LANGUAGE TypeFamilies       #-}

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

module Dhall.Map
    ( -- * Type
      Map

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

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

      -- * Sorting
    , sort
    , isSorted

      -- * Insertion
    , insert
    , insertWith

      -- * Deletion/Update
    , delete
    , filter
    , 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 Data.Semigroup
import GHC.Generics (Generic)
import Instances.TH.Lift ()
import Language.Haskell.TH.Syntax (Lift)
import Prelude hiding (filter, lookup)

import qualified Data.List
import qualified Data.Map
import qualified Data.Set
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.Map k v) (Keys k)
    deriving (Typeable (Map k v)
DataType
Constr
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 -> DataType
Map k v -> Constr
(forall b. Data b => b -> b) -> Map k v -> Map k v
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Map k v -> c (Map k v)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Map k v)
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (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 -> DataType
forall k v. (Data k, Data v, Ord k) => Map k v -> Constr
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))
$cMap :: Constr
$tMap :: DataType
gmapMo :: (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)
gmapMp :: (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)
gmapM :: (forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
$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)
gmapQi :: Int -> (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
gmapQ :: (forall d. Data d => d -> u) -> Map k v -> [u]
$cgmapQ :: forall k v u.
(Data k, Data v, Ord k) =>
(forall d. Data d => d -> u) -> Map k v -> [u]
gmapQr :: (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
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
$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
gmapT :: (forall b. Data b => b -> b) -> Map k v -> 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
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> 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))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Map k v))
$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))
dataTypeOf :: Map k v -> DataType
$cdataTypeOf :: forall k v. (Data k, Data v, Ord k) => Map k v -> DataType
toConstr :: Map k v -> Constr
$ctoConstr :: forall k v. (Data k, Data v, Ord k) => Map k v -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> 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)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Map k v -> 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)
$cp1Data :: forall k v. (Data k, Data v, Ord k) => Typeable (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
$cto :: forall k v x. Rep (Map k v) x -> Map k v
$cfrom :: forall k v x. Map k v -> Rep (Map k v) x
Generic, Map k v -> Q Exp
(Map k v -> Q Exp) -> Lift (Map k v)
forall t. (t -> Q Exp) -> Lift t
forall k v. (Lift k, Lift v) => Map k v -> Q Exp
lift :: Map k v -> Q Exp
$clift :: forall k v. (Lift k, Lift v) => Map k v -> Q Exp
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 -> ()
rnf :: Map k v -> ()
$crnf :: forall k v. (NFData k, NFData v) => Map k v -> ()
NFData)

data Keys a
    = Sorted
    | Original [a]
    deriving (Typeable (Keys a)
DataType
Constr
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 -> DataType
Keys a -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (Keys a))
(forall b. Data b => b -> b) -> Keys a -> Keys a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Keys a -> c (Keys a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Keys a)
forall a. Data a => Typeable (Keys a)
forall a. Data a => Keys a -> DataType
forall a. Data a => Keys a -> Constr
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))
$cOriginal :: Constr
$cSorted :: Constr
$tKeys :: DataType
gmapMo :: (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)
gmapMp :: (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)
gmapM :: (forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Keys a -> m (Keys a)
gmapQi :: Int -> (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
gmapQ :: (forall d. Data d => d -> u) -> Keys a -> [u]
$cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Keys a -> [u]
gmapQr :: (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
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Keys a -> r
gmapT :: (forall b. Data b => b -> b) -> Keys a -> Keys a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> Keys a -> Keys a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> 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))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Keys a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Keys a))
dataTypeOf :: Keys a -> DataType
$cdataTypeOf :: forall a. Data a => Keys a -> DataType
toConstr :: Keys a -> Constr
$ctoConstr :: forall a. Data a => Keys a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> 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)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Keys a -> 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)
$cp1Data :: forall a. Data a => Typeable (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
$cto :: forall a x. Rep (Keys a) x -> Keys a
$cfrom :: forall a x. Keys a -> Rep (Keys a) x
Generic, Keys a -> Q Exp
(Keys a -> Q Exp) -> Lift (Keys a)
forall a. Lift a => Keys a -> Q Exp
forall t. (t -> Q Exp) -> Lift t
lift :: Keys a -> Q Exp
$clift :: forall a. Lift a => Keys a -> Q Exp
Lift, Keys a -> ()
(Keys a -> ()) -> NFData (Keys a)
forall a. NFData a => Keys a -> ()
forall a. (a -> ()) -> NFData a
rnf :: Keys a -> ()
$crnf :: forall a. NFData a => Keys a -> ()
NFData)

instance (Ord k, Eq v) => Eq (Map k v) where
  m1 :: Map k v
m1 == :: Map k v -> Map k v -> Bool
== m2 :: Map k v
m2 =
      Map k v -> Int
forall k a. Map k a -> Int
Data.Map.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.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 m1 :: Map k v
m1 m2 :: 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 :: (a -> b) -> Map k a -> Map k b
fmap f :: a -> b
f (Map m :: Map k a
m ks :: 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 (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 :: (a -> b -> b) -> b -> Map k a -> b
foldr f :: a -> b -> b
f z :: b
z (Map m :: Map k a
m Sorted) = (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 f :: a -> b -> b
f z :: b
z m :: Map k a
m              = (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 :: Map k a -> Int
length m :: Map k a
m = Map k a -> Int
forall k v. Map k v -> Int
size Map k a
m
  {-# INLINABLE length #-}

  null :: Map k a -> Bool
null (Map m :: Map k a
m _) = 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 :: (a -> f b) -> Map k a -> f (Map k b)
traverse f :: a -> f b
f m :: 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 (\_ v :: 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 => Data.Semigroup.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.empty ([k] -> Keys k
forall a. [a] -> Keys a
Original [])
    {-# INLINABLE mempty #-}

#if !(MIN_VERSION_base(4,11,0))
    mappend = (<>)
    {-# INLINABLE mappend #-}
#endif

instance (Show k, Show v, Ord k) => Show (Map k v) where
    showsPrec :: Int -> Map k v -> ShowS
showsPrec d :: Int
d m :: Map k v
m =
        Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 10) (String -> ShowS
showString "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 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 = [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 -> [Item (Map k v)]
forall k v. Ord k => Map k v -> [(k, v)]
Dhall.Map.toList

-- | Create an empty `Map`
empty :: Ord k => Map k v
empty :: 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 :: k -> v -> Map k v
singleton k :: k
k v :: 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.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 :: [(k, v)] -> Map k v
fromList kvs :: [(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.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 :: (k -> v -> v -> v) -> [(k, v)] -> Map k v
fromListWithKey f :: k -> v -> v -> v
f kvs :: [(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.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 #-}

{-| Remove duplicates from a  list

>>> nubOrd [1,2,3]
[1,2,3]
>>> nubOrd [1,1,3]
[1,3]
-}
nubOrd :: Ord k => [k] -> [k]
nubOrd :: [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 _      []  = []
    go set :: Set a
set (k :: a
k:ks :: [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 :: k -> v -> Map k v
unorderedSingleton k :: k
k v :: 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.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 :: [(k, v)] -> Map k v
unorderedFromList kvs :: [(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.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 :: Map k v -> Map k v
sort (Map m :: 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
{-# 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 :: Map k v -> Bool
isSorted (Map _ Sorted)        = Bool
True
isSorted (Map m :: Map k v
m (Original ks :: [k]
ks)) = Map k v -> [k]
forall k a. Map k a -> [k]
Data.Map.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 :: k -> v -> Map k v -> Map k v
insert k :: k
k v :: v
v (Map m :: Map k v
m 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.insert k
k v
v Map k v
m) Keys k
forall a. Keys a
Sorted
insert k :: k
k v :: v
v (Map m :: Map k v
m (Original ks :: [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
    (mayOldV :: Maybe v
mayOldV, m' :: 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.insertLookupWithKey (\_k :: k
_k new :: v
new _old :: v
_old -> v
new) k
k v
v Map k v
m

    ks' :: [k]
ks' | Just _ <- 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 :: (v -> v -> v) -> k -> v -> Map k v -> Map k v
insertWith f :: v -> v -> v
f k :: k
k v :: v
v (Map m :: Map k v
m 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.insertWith v -> v -> v
f k
k v
v Map k v
m) Keys k
forall a. Keys a
Sorted
insertWith f :: v -> v -> v
f k :: k
k v :: v
v (Map m :: Map k v
m (Original ks :: [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
    (mayOldV :: Maybe v
mayOldV, m' :: 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.insertLookupWithKey (\_k :: k
_k new :: v
new old :: v
old -> v -> v -> v
f v
new v
old) k
k v
v Map k v
m

    ks' :: [k]
ks' | Just _ <- 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 :: k -> Map k v -> Map k v
delete k :: k
k (Map m :: Map k v
m ks :: 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.delete k
k Map k v
m

    ks' :: Keys k
ks' = case Keys k
ks of
        Sorted        -> Keys k
forall a. Keys a
Sorted
        Original ks'' :: [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 :: (a -> Bool) -> Map k a -> Map k a
filter predicate :: a -> Bool
predicate (Map m :: Map k a
m ks :: 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.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 -> k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.member k
k Map k a
m') Keys k
ks
{-# INLINABLE filter #-}

{-| Restrict a 'Map' to only those keys found in a @"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 :: Map k a -> Set k -> Map k a
restrictKeys (Map m :: Map k a
m ks :: Keys k
ks) s :: 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
#if MIN_VERSION_containers(0,5,8)
    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.restrictKeys Map k a
m Set k
s
#else
    m' = Data.Map.filterWithKey (\k _ -> Data.Set.member k s) m
#endif

    ks' :: Keys k
ks' = (k -> Bool) -> Keys k -> Keys k
forall a. (a -> Bool) -> Keys a -> Keys a
filterKeys (\k :: 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".'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 :: Map k a -> Set k -> Map k a
withoutKeys (Map m :: Map k a
m ks :: Keys k
ks) s :: 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
#if MIN_VERSION_containers(0,5,8)
    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.withoutKeys Map k a
m Set k
s
#else
    m' = Data.Map.filterWithKey (\k _ -> Data.Set.notMember k s) m
#endif

    ks' :: Keys k
ks' = (k -> Bool) -> Keys k -> Keys k
forall a. (a -> Bool) -> Keys a -> Keys a
filterKeys (\k :: 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 :: (a -> Maybe b) -> Map k a -> Map k b
mapMaybe f :: a -> Maybe b
f (Map m :: Map k a
m ks :: 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.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 -> k -> Map k b -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.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 :: k -> Map k v -> Maybe v
lookup k :: k
k (Map m :: Map k v
m _) = k -> Map k v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
Data.Map.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 :: Map k v -> Maybe (k, v, Map k v)
uncons (Map _ (Original []))     = Maybe (k, v, Map k v)
forall a. Maybe a
Nothing
uncons (Map m :: Map k v
m (Original (k :: k
k:ks :: [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.! 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.delete k
k Map k v
m) ([k] -> Keys k
forall a. [a] -> Keys a
Original [k]
ks))
uncons (Map m :: Map k v
m Sorted)
  | Just ((k :: k
k, v :: v
v), m' :: 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.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 :: k -> Map k v -> Bool
member k :: k
k (Map m :: Map k v
m _) = k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.member k
k Map k v
m
{-# INLINABLE member #-}

{-|
>>> size (fromList [("A",1)])
1
-}
size :: Map k v -> Int
size :: Map k v -> Int
size (Map m :: Map k v
m _) = Map k v -> Int
forall k a. Map k a -> Int
Data.Map.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 :: Map k v -> Map k v -> Map k v
union (Map mL :: Map k v
mL ksL :: Keys k
ksL) (Map mR :: Map k v
mR ksR :: 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.union Map k v
mL Map k v
mR

    ks :: Keys k
ks = case (Keys k
ksL, Keys k
ksR) of
        (Original l :: [k]
l, Original r :: [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 (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 -> k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.notMember k
k Map k v
mL) [k]
r
        _                        -> 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 :: (v -> v -> v) -> Map k v -> Map k v -> Map k v
unionWith combine :: v -> v -> v
combine (Map mL :: Map k v
mL ksL :: Keys k
ksL) (Map mR :: Map k v
mR ksR :: 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.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 l :: [k]
l, Original r :: [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 (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 -> k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.notMember k
k Map k v
mL) [k]
r
        _                        -> 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 :: (a -> c)
-> (b -> c) -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
outerJoin fa :: a -> c
fa fb :: b -> c
fb fab :: k -> a -> b -> c
fab (Map ma :: Map k a
ma ksA :: Keys k
ksA) (Map mb :: Map k b
mb ksB :: 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.mergeWithKey
            (\k :: k
k a :: a
a b :: 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 (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> c
fa)
            ((b -> c) -> Map k b -> Map k c
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 l :: [k]
l, Original r :: [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 (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 -> k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.notMember k
k Map k a
ma) [k]
r
        _                        -> 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 :: Map k a -> Map k b -> Map k a
intersection (Map mL :: Map k a
mL ksL :: Keys k
ksL) (Map mR :: Map k b
mR _) = 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.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 -> k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.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 :: (a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith combine :: a -> b -> c
combine (Map mL :: Map k a
mL ksL :: Keys k
ksL) (Map mR :: Map k b
mR _) = 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.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 -> k -> Map k c -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.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 :: Map k a -> Map k b -> Map k a
difference (Map mL :: Map k a
mL ksL :: Keys k
ksL) (Map mR :: Map k b
mR _) = 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.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 -> k -> Map k b -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.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 :: (k -> a -> m) -> Map k a -> m
foldMapWithKey f :: k -> a -> m
f (Map m :: Map k a
m Sorted) = (k -> a -> m) -> Map k a -> m
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Data.Map.foldMapWithKey k -> a -> m
f Map k a
m
foldMapWithKey f :: k -> a -> m
f m :: Map k a
m              = ((k, a) -> m) -> [(k, 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 :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey f :: k -> a -> b
f (Map m :: Map k a
m ks :: 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.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 :: (k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey f :: k -> a -> f b
f (Map m :: Map k a
m Sorted) =
    (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\m' :: 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.traverseWithKey k -> a -> f b
f Map k a
m)
traverseWithKey f :: k -> a -> f b
f m :: Map k a
m =
    ([(k, b)] -> Map k b) -> f [(k, b)] -> f (Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(k, b)] -> Map k b
forall k v. Ord k => [(k, v)] -> Map k v
fromList (((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)
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
k, a :: a
a) = (b -> (k, b)) -> f b -> f (k, 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 :: (k -> a -> f b) -> Map k a -> f (Map k b)
unorderedTraverseWithKey f :: k -> a -> f b
f (Map m :: Map k a
m ks :: Keys k
ks) =
    (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\m' :: 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.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_ :: (k -> a -> f ()) -> Map k a -> f ()
unorderedTraverseWithKey_ f :: k -> a -> f ()
f (Map m :: Map k a
m _) =
    (f () -> k -> a -> f ()) -> f () -> Map k a -> f ()
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Data.Map.foldlWithKey' (\acc :: f ()
acc k :: k
k v :: a
v -> f ()
acc f () -> f () -> f ()
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> k -> a -> f ()
f k
k a
v) (() -> f ()
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 :: Map k v -> [(k, v)]
toList (Map m :: Map k v
m Sorted)        = Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Data.Map.toList Map k v
m
toList (Map m :: Map k v
m (Original ks :: [k]
ks)) = (k -> (k, v)) -> [k] -> [(k, v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\k :: 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.! 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 :: Map k v -> [(k, v)]
toAscList (Map m :: Map k v
m _) = Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Data.Map.toAscList Map k v
m
{-# INLINABLE toAscList #-}

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

>>> toMap (fromList [("B",1),("A",2)]) -- Order is lost upon conversion
fromList [("A",2),("B",1)]
-}
toMap :: Map k v -> Data.Map.Map k v
toMap :: Map k v -> Map k v
toMap (Map m :: Map k v
m _) = 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 :: Map k v -> [k]
keys (Map m :: Map k v
m Sorted)        = Map k v -> [k]
forall k a. Map k a -> [k]
Data.Map.keys Map k v
m
keys (Map _ (Original ks :: [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 :: Map k v -> [v]
elems (Map m :: Map k v
m Sorted)        = Map k v -> [v]
forall k a. Map k a -> [a]
Data.Map.elems Map k v
m
elems (Map m :: Map k v
m (Original ks :: [k]
ks)) = (k -> v) -> [k] -> [v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\k :: k
k -> Map k v
m Map k v -> k -> v
forall k a. Ord k => Map k a -> k -> a
Data.Map.! k
k) [k]
ks
{-# INLINABLE elems #-}

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

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

filterKeys :: (a -> Bool) -> Keys a -> Keys a
filterKeys :: (a -> Bool) -> Keys a -> Keys a
filterKeys _ Sorted        = Keys a
forall a. Keys a
Sorted
filterKeys f :: a -> Bool
f (Original ks :: [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 #-}

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