{-# LANGUAGE DeriveAnyClass     #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveGeneric      #-}
{-# LANGUAGE DeriveLift         #-}
{-# LANGUAGE ExplicitForAll     #-}
{-# 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.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 (TExp (Map k v))
(Map k v -> Q Exp)
-> (Map k v -> Q (TExp (Map k v))) -> Lift (Map k v)
forall k v. (Lift k, Lift v) => Map k v -> Q Exp
forall k v. (Lift k, Lift v) => Map k v -> Q (TExp (Map k v))
forall t. (t -> Q Exp) -> (t -> Q (TExp t)) -> Lift t
liftTyped :: Map k v -> Q (TExp (Map k v))
$cliftTyped :: forall k v. (Lift k, Lift v) => Map k v -> Q (TExp (Map k v))
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 (TExp (Keys a))
(Keys a -> Q Exp) -> (Keys a -> Q (TExp (Keys a))) -> Lift (Keys a)
forall a. Lift a => Keys a -> Q Exp
forall a. Lift a => Keys a -> Q (TExp (Keys a))
forall t. (t -> Q Exp) -> (t -> Q (TExp t)) -> Lift t
liftTyped :: Keys a -> Q (TExp (Keys a))
$cliftTyped :: forall a. Lift a => Keys a -> Q (TExp (Keys a))
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
  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.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 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 :: (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 (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 a -> b -> b
f b
z (Map Map k a
m Keys k
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 a -> b -> b
f b
z 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 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 Map k a
m Keys k
_) = 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 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.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 = [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 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 [(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 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.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".`Data.Map.Map`@
fromMap :: Data.Map.Map k v -> Map k v
fromMap :: 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 :: [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 :: 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.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 [(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 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 :: 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.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 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.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.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 :: (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.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.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 :: 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.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 :: (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.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.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 :: (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.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.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 :: 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.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 :: 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.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 :: (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.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.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 (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.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 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.! 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 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.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 (Map Map k v
m Keys k
_) = 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 Map k v
m Keys k
_) = 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 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.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 (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.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 :: (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.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 (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.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 :: (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.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 (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 [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 (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.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 :: 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.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.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 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.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.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 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.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.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 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.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 (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 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.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 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 (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.traverseWithKey k -> a -> f b
f Map k a
m)
traverseWithKey k -> a -> f b
f 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, 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 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 (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.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_ 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.foldlWithKey' (\f ()
acc k
k 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 Map k v
m Keys k
Sorted)        = Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Data.Map.toList Map k v
m
toList (Map Map k v
m (Original [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, 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 Map k v
m Keys k
_) = 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 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 :: 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.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 :: 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.elems Map k v
m
elems (Map Map k v
m (Original [k]
ks)) = (k -> v) -> [k] -> [v]
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.! 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 :: 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.keysSet Map k v
m
{-# INLINABLE keysSet #-}

filterKeys :: (a -> Bool) -> Keys a -> Keys a
filterKeys :: (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 :: (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]
:}
-}