{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TemplateHaskellQuotes #-}
{-# LANGUAGE TypeFamilies #-}

-- |
-- An abstract interface for maps from JSON keys to values.

module Data.Aeson.KeyMap (
    -- * Map Type
    KeyMap,

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

    -- * Construction
    empty,
    singleton,

    -- ** Insertion
    insert,

    -- * Deletion
    delete,

    -- * Update
    alterF,

    -- * Combine
    difference,
    union,
    unionWith,
    unionWithKey,
    intersection,
    intersectionWith,
    intersectionWithKey,
    alignWith,
    alignWithKey,

    -- * Lists
    fromList,
    fromListWith,
    toList,
    toAscList,
    elems,

    -- * Maps
    fromHashMap,
    toHashMap,
    fromHashMapText,
    toHashMapText,
    coercionToHashMap,
    fromMap,
    toMap,
    fromMapText,
    toMapText,
    coercionToMap,

    -- * Traversal
    -- ** Map
    map,
    mapKeyVal,
    traverse,
    traverseWithKey,

    -- * Folds
    foldr,
    foldr',
    foldl,
    foldl',
    foldMapWithKey,
    foldrWithKey,

    -- * Conversions
    keys,

    -- * Filter
    filter,
    filterWithKey,
    mapMaybe,
    mapMaybeWithKey,
) where

-- Import stuff from Prelude explicitly
import Prelude (Eq(..), Ord((>)), Int, Bool(..), Maybe(..))
import Prelude ((.), ($))
import Prelude (Functor(fmap), Monad(..))
import Prelude (Show, showsPrec, showParen, shows, showString)

import Control.Applicative (Applicative)
import Control.DeepSeq (NFData(..))
import Data.Aeson.Key (Key)
import Data.Bifunctor (first)
import Data.Data (Data)
import Data.Hashable (Hashable(..))
import Data.HashMap.Strict (HashMap)
import Data.Map (Map)
import Data.Monoid (Monoid(mempty, mappend))
import Data.Semigroup (Semigroup((<>)))
import Data.Text (Text)
import Data.These (These (..))
import Data.Type.Coercion (Coercion (..))
import Data.Typeable (Typeable)
import Text.Read (Read (..), Lexeme(..), readListPrecDefault, prec, lexP, parens)

import qualified Data.Aeson.Key as Key
import qualified Data.Foldable as F
import qualified Data.Traversable as T
import qualified Data.HashMap.Strict as H
import qualified Data.List as L
import qualified Data.Map.Strict as M
import qualified Language.Haskell.TH.Syntax as TH
import qualified Data.Foldable.WithIndex    as WI (FoldableWithIndex (..))
import qualified Data.Functor.WithIndex     as WI (FunctorWithIndex (..))
import qualified Data.Traversable.WithIndex as WI (TraversableWithIndex (..))
import qualified Data.Semialign as SA
import qualified Data.Semialign.Indexed as SAI
import qualified GHC.Exts
import qualified Test.QuickCheck as QC
import qualified Witherable as W

#ifdef USE_ORDEREDMAP

-------------------------------------------------------------------------------
-- Map
-------------------------------------------------------------------------------

-- | A map from JSON key type 'Key' to 'v'.
newtype KeyMap v = KeyMap { KeyMap v -> Map Key v
unKeyMap :: Map Key v }
  deriving (KeyMap v -> KeyMap v -> Bool
(KeyMap v -> KeyMap v -> Bool)
-> (KeyMap v -> KeyMap v -> Bool) -> Eq (KeyMap v)
forall v. Eq v => KeyMap v -> KeyMap v -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: KeyMap v -> KeyMap v -> Bool
$c/= :: forall v. Eq v => KeyMap v -> KeyMap v -> Bool
== :: KeyMap v -> KeyMap v -> Bool
$c== :: forall v. Eq v => KeyMap v -> KeyMap v -> Bool
Eq, Eq (KeyMap v)
Eq (KeyMap v)
-> (KeyMap v -> KeyMap v -> Ordering)
-> (KeyMap v -> KeyMap v -> Bool)
-> (KeyMap v -> KeyMap v -> Bool)
-> (KeyMap v -> KeyMap v -> Bool)
-> (KeyMap v -> KeyMap v -> Bool)
-> (KeyMap v -> KeyMap v -> KeyMap v)
-> (KeyMap v -> KeyMap v -> KeyMap v)
-> Ord (KeyMap v)
KeyMap v -> KeyMap v -> Bool
KeyMap v -> KeyMap v -> Ordering
KeyMap v -> KeyMap v -> KeyMap v
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v. Ord v => Eq (KeyMap v)
forall v. Ord v => KeyMap v -> KeyMap v -> Bool
forall v. Ord v => KeyMap v -> KeyMap v -> Ordering
forall v. Ord v => KeyMap v -> KeyMap v -> KeyMap v
min :: KeyMap v -> KeyMap v -> KeyMap v
$cmin :: forall v. Ord v => KeyMap v -> KeyMap v -> KeyMap v
max :: KeyMap v -> KeyMap v -> KeyMap v
$cmax :: forall v. Ord v => KeyMap v -> KeyMap v -> KeyMap v
>= :: KeyMap v -> KeyMap v -> Bool
$c>= :: forall v. Ord v => KeyMap v -> KeyMap v -> Bool
> :: KeyMap v -> KeyMap v -> Bool
$c> :: forall v. Ord v => KeyMap v -> KeyMap v -> Bool
<= :: KeyMap v -> KeyMap v -> Bool
$c<= :: forall v. Ord v => KeyMap v -> KeyMap v -> Bool
< :: KeyMap v -> KeyMap v -> Bool
$c< :: forall v. Ord v => KeyMap v -> KeyMap v -> Bool
compare :: KeyMap v -> KeyMap v -> Ordering
$ccompare :: forall v. Ord v => KeyMap v -> KeyMap v -> Ordering
$cp1Ord :: forall v. Ord v => Eq (KeyMap v)
Ord, Typeable, Typeable (KeyMap v)
DataType
Constr
Typeable (KeyMap v)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (KeyMap v))
-> (KeyMap v -> Constr)
-> (KeyMap v -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (KeyMap v)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (KeyMap v)))
-> ((forall b. Data b => b -> b) -> KeyMap v -> KeyMap v)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> KeyMap v -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> KeyMap v -> r)
-> (forall u. (forall d. Data d => d -> u) -> KeyMap v -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> KeyMap v -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v))
-> Data (KeyMap v)
KeyMap v -> DataType
KeyMap v -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (KeyMap v))
(forall b. Data b => b -> b) -> KeyMap v -> KeyMap v
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (KeyMap v)
forall v. Data v => Typeable (KeyMap v)
forall v. Data v => KeyMap v -> DataType
forall v. Data v => KeyMap v -> Constr
forall v.
Data v =>
(forall b. Data b => b -> b) -> KeyMap v -> KeyMap v
forall v u.
Data v =>
Int -> (forall d. Data d => d -> u) -> KeyMap v -> u
forall v u.
Data v =>
(forall d. Data d => d -> u) -> KeyMap v -> [u]
forall v r r'.
Data v =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
forall v r r'.
Data v =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
forall v (m :: * -> *).
(Data v, Monad m) =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
forall v (m :: * -> *).
(Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
forall v (c :: * -> *).
Data v =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (KeyMap v)
forall v (c :: * -> *).
Data v =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v)
forall v (t :: * -> *) (c :: * -> *).
(Data v, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (KeyMap v))
forall v (t :: * -> * -> *) (c :: * -> *).
(Data v, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (KeyMap 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) -> KeyMap v -> u
forall u. (forall d. Data d => d -> u) -> KeyMap v -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (KeyMap v)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (KeyMap v))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (KeyMap v))
$cKeyMap :: Constr
$tKeyMap :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
$cgmapMo :: forall v (m :: * -> *).
(Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
gmapMp :: (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
$cgmapMp :: forall v (m :: * -> *).
(Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
gmapM :: (forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
$cgmapM :: forall v (m :: * -> *).
(Data v, Monad m) =>
(forall d. Data d => d -> m d) -> KeyMap v -> m (KeyMap v)
gmapQi :: Int -> (forall d. Data d => d -> u) -> KeyMap v -> u
$cgmapQi :: forall v u.
Data v =>
Int -> (forall d. Data d => d -> u) -> KeyMap v -> u
gmapQ :: (forall d. Data d => d -> u) -> KeyMap v -> [u]
$cgmapQ :: forall v u.
Data v =>
(forall d. Data d => d -> u) -> KeyMap v -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
$cgmapQr :: forall v r r'.
Data v =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
$cgmapQl :: forall v r r'.
Data v =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> KeyMap v -> r
gmapT :: (forall b. Data b => b -> b) -> KeyMap v -> KeyMap v
$cgmapT :: forall v.
Data v =>
(forall b. Data b => b -> b) -> KeyMap v -> KeyMap v
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (KeyMap v))
$cdataCast2 :: forall v (t :: * -> * -> *) (c :: * -> *).
(Data v, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (KeyMap v))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (KeyMap v))
$cdataCast1 :: forall v (t :: * -> *) (c :: * -> *).
(Data v, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (KeyMap v))
dataTypeOf :: KeyMap v -> DataType
$cdataTypeOf :: forall v. Data v => KeyMap v -> DataType
toConstr :: KeyMap v -> Constr
$ctoConstr :: forall v. Data v => KeyMap v -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (KeyMap v)
$cgunfold :: forall v (c :: * -> *).
Data v =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (KeyMap v)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v)
$cgfoldl :: forall v (c :: * -> *).
Data v =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> KeyMap v -> c (KeyMap v)
$cp1Data :: forall v. Data v => Typeable (KeyMap v)
Data, a -> KeyMap b -> KeyMap a
(a -> b) -> KeyMap a -> KeyMap b
(forall a b. (a -> b) -> KeyMap a -> KeyMap b)
-> (forall a b. a -> KeyMap b -> KeyMap a) -> Functor KeyMap
forall a b. a -> KeyMap b -> KeyMap a
forall a b. (a -> b) -> KeyMap a -> KeyMap b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> KeyMap b -> KeyMap a
$c<$ :: forall a b. a -> KeyMap b -> KeyMap a
fmap :: (a -> b) -> KeyMap a -> KeyMap b
$cfmap :: forall a b. (a -> b) -> KeyMap a -> KeyMap b
Functor)


-- | Construct an empty map.
empty :: KeyMap v
empty :: KeyMap v
empty = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap Map Key v
forall k a. Map k a
M.empty

-- | Is the map empty?
null :: KeyMap v -> Bool
null :: KeyMap v -> Bool
null = Map Key v -> Bool
forall k a. Map k a -> Bool
M.null (Map Key v -> Bool) -> (KeyMap v -> Map Key v) -> KeyMap v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Return the number of key-value mappings in this map.
size :: KeyMap v -> Int
size :: KeyMap v -> Int
size = Map Key v -> Int
forall k a. Map k a -> Int
M.size (Map Key v -> Int) -> (KeyMap v -> Map Key v) -> KeyMap v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Construct a map with a single element.
singleton :: Key -> v -> KeyMap v
singleton :: Key -> v -> KeyMap v
singleton Key
k v
v = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Key -> v -> Map Key v
forall k a. k -> a -> Map k a
M.singleton Key
k v
v)

-- | Is the key a member of the map?
member :: Key -> KeyMap a -> Bool
member :: Key -> KeyMap a -> Bool
member Key
t (KeyMap Map Key a
m) = Key -> Map Key a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.member Key
t Map Key a
m

-- | Remove the mapping for the specified key from this map if present.
delete :: Key -> KeyMap v -> KeyMap v
delete :: Key -> KeyMap v -> KeyMap v
delete Key
k (KeyMap Map Key v
m) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Key -> Map Key v -> Map Key v
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Key
k Map Key v
m)

-- | 'alterF' can be used to insert, delete, or update a value in a map.
alterF :: Functor f => (Maybe v -> f (Maybe v)) -> Key -> KeyMap v -> f (KeyMap v)
#if MIN_VERSION_containers(0,5,8)
alterF :: (Maybe v -> f (Maybe v)) -> Key -> KeyMap v -> f (KeyMap v)
alterF Maybe v -> f (Maybe v)
f Key
k = (Map Key v -> KeyMap v) -> f (Map Key v) -> f (KeyMap v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (f (Map Key v) -> f (KeyMap v))
-> (KeyMap v -> f (Map Key v)) -> KeyMap v -> f (KeyMap v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe v -> f (Maybe v)) -> Key -> Map Key v -> f (Map Key v)
forall (f :: * -> *) k a.
(Functor f, Ord k) =>
(Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
M.alterF Maybe v -> f (Maybe v)
f Key
k (Map Key v -> f (Map Key v))
-> (KeyMap v -> Map Key v) -> KeyMap v -> f (Map Key v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap
#else
alterF f k m = fmap g (f mv) where
    g r =  case r of
        Nothing -> case mv of
            Nothing -> m
            Just _  -> delete k m
        Just v' -> insert k v' m

    mv = lookup k m
#endif

-- | Return the value to which the specified key is mapped,
-- or Nothing if this map contains no mapping for the key.
lookup :: Key -> KeyMap v -> Maybe v
lookup :: Key -> KeyMap v -> Maybe v
lookup Key
t KeyMap v
tm = Key -> Map Key v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Key
t (KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap KeyMap v
tm)

-- | Associate the specified value with the specified key
-- in this map. If this map previously contained a mapping
-- for the key, the old value is replaced.
insert :: Key -> v -> KeyMap v -> KeyMap v
insert :: Key -> v -> KeyMap v -> KeyMap v
insert Key
k v
v KeyMap v
tm = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Key -> v -> Map Key v -> Map Key v
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Key
k v
v (KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap KeyMap v
tm))

-- | Map a function over all values in the map.
map :: (a -> b) -> KeyMap a -> KeyMap b
map :: (a -> b) -> KeyMap a -> KeyMap b
map = (a -> b) -> KeyMap a -> KeyMap b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- | Map a function over all values in the map.
mapWithKey :: (Key -> a -> b) -> KeyMap a -> KeyMap b
mapWithKey :: (Key -> a -> b) -> KeyMap a -> KeyMap b
mapWithKey Key -> a -> b
f (KeyMap Map Key a
m) = Map Key b -> KeyMap b
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> a -> b) -> Map Key a -> Map Key b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
M.mapWithKey Key -> a -> b
f Map Key a
m)

foldMapWithKey :: Monoid m => (Key -> a -> m) -> KeyMap a -> m
foldMapWithKey :: (Key -> a -> m) -> KeyMap a -> m
foldMapWithKey Key -> a -> m
f (KeyMap Map Key a
m) = (Key -> a -> m) -> Map Key a -> m
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
M.foldMapWithKey Key -> a -> m
f Map Key a
m

foldr :: (a -> b -> b) -> b -> KeyMap a -> b
foldr :: (a -> b -> b) -> b -> KeyMap a -> b
foldr a -> b -> b
f b
z (KeyMap Map Key a
m) = (a -> b -> b) -> b -> Map Key a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
M.foldr a -> b -> b
f b
z Map Key a
m

foldr' :: (a -> b -> b) -> b -> KeyMap a -> b
foldr' :: (a -> b -> b) -> b -> KeyMap a -> b
foldr' a -> b -> b
f b
z (KeyMap Map Key a
m) = (a -> b -> b) -> b -> Map Key a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
M.foldr' a -> b -> b
f b
z Map Key a
m

foldl :: (b -> a -> b) -> b -> KeyMap a -> b
foldl :: (b -> a -> b) -> b -> KeyMap a -> b
foldl b -> a -> b
f b
z (KeyMap Map Key a
m) = (b -> a -> b) -> b -> Map Key a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
M.foldl b -> a -> b
f b
z Map Key a
m

foldl' :: (b -> a -> b) -> b -> KeyMap a -> b
foldl' :: (b -> a -> b) -> b -> KeyMap a -> b
foldl' b -> a -> b
f b
z (KeyMap Map Key a
m) = (b -> a -> b) -> b -> Map Key a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
M.foldl' b -> a -> b
f b
z Map Key a
m

-- | Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator).
foldrWithKey :: (Key -> v -> a -> a) -> a -> KeyMap v -> a
foldrWithKey :: (Key -> v -> a -> a) -> a -> KeyMap v -> a
foldrWithKey Key -> v -> a -> a
f a
a = (Key -> v -> a -> a) -> a -> Map Key v -> a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
M.foldrWithKey Key -> v -> a -> a
f a
a (Map Key v -> a) -> (KeyMap v -> Map Key v) -> KeyMap v -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Perform an Applicative action for each key-value pair
-- in a 'KeyMap' and produce a 'KeyMap' of all the results.
traverse :: Applicative f => (v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverse :: (v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverse v1 -> f v2
f = (Map Key v2 -> KeyMap v2) -> f (Map Key v2) -> f (KeyMap v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Key v2 -> KeyMap v2
forall v. Map Key v -> KeyMap v
KeyMap (f (Map Key v2) -> f (KeyMap v2))
-> (KeyMap v1 -> f (Map Key v2)) -> KeyMap v1 -> f (KeyMap v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v1 -> f v2) -> Map Key v1 -> f (Map Key v2)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
T.traverse v1 -> f v2
f (Map Key v1 -> f (Map Key v2))
-> (KeyMap v1 -> Map Key v1) -> KeyMap v1 -> f (Map Key v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v1 -> Map Key v1
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Perform an Applicative action for each key-value pair
-- in a 'KeyMap' and produce a 'KeyMap' of all the results.
traverseWithKey :: Applicative f => (Key -> v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverseWithKey :: (Key -> v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverseWithKey Key -> v1 -> f v2
f = (Map Key v2 -> KeyMap v2) -> f (Map Key v2) -> f (KeyMap v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map Key v2 -> KeyMap v2
forall v. Map Key v -> KeyMap v
KeyMap (f (Map Key v2) -> f (KeyMap v2))
-> (KeyMap v1 -> f (Map Key v2)) -> KeyMap v1 -> f (KeyMap v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Key -> v1 -> f v2) -> Map Key v1 -> f (Map Key v2)
forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
M.traverseWithKey Key -> v1 -> f v2
f  (Map Key v1 -> f (Map Key v2))
-> (KeyMap v1 -> Map Key v1) -> KeyMap v1 -> f (Map Key v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v1 -> Map Key v1
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Construct a map from a list of elements. Uses the
-- provided function, f, to merge duplicate entries with
-- (f newVal oldVal).
fromListWith :: (v -> v -> v) ->  [(Key, v)] -> KeyMap v
fromListWith :: (v -> v -> v) -> [(Key, v)] -> KeyMap v
fromListWith v -> v -> v
op = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Map Key v -> KeyMap v)
-> ([(Key, v)] -> Map Key v) -> [(Key, v)] -> KeyMap v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v -> v -> v) -> [(Key, v)] -> Map Key v
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
M.fromListWith v -> v -> v
op

-- |  Construct a map with the supplied mappings. If the
-- list contains duplicate mappings, the later mappings take
-- precedence.
fromList :: [(Key, v)] -> KeyMap v
fromList :: [(Key, v)] -> KeyMap v
fromList = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Map Key v -> KeyMap v)
-> ([(Key, v)] -> Map Key v) -> [(Key, v)] -> KeyMap v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Key, v)] -> Map Key v
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList

-- | Return a list of this map's keys and elements.
--
-- The order is not stable. Use 'toAscList' for stable ordering.
toList :: KeyMap v -> [(Key, v)]
toList :: KeyMap v -> [(Key, v)]
toList = Map Key v -> [(Key, v)]
forall k a. Map k a -> [(k, a)]
M.toList (Map Key v -> [(Key, v)])
-> (KeyMap v -> Map Key v) -> KeyMap v -> [(Key, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Return a list of this map' elements.
--
-- @since 2.0.2.0
elems :: KeyMap v -> [v]
elems :: KeyMap v -> [v]
elems = Map Key v -> [v]
forall k a. Map k a -> [a]
M.elems (Map Key v -> [v]) -> (KeyMap v -> Map Key v) -> KeyMap v -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Return a list of this map's elements in ascending order
-- based of the textual key.
toAscList :: KeyMap v -> [(Key, v)]
toAscList :: KeyMap v -> [(Key, v)]
toAscList = Map Key v -> [(Key, v)]
forall k a. Map k a -> [(k, a)]
M.toAscList (Map Key v -> [(Key, v)])
-> (KeyMap v -> Map Key v) -> KeyMap v -> [(Key, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Difference of two maps. Return elements of the first
-- map not existing in the second.
difference :: KeyMap v -> KeyMap v' -> KeyMap v
difference :: KeyMap v -> KeyMap v' -> KeyMap v
difference KeyMap v
tm1 KeyMap v'
tm2 = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Map Key v -> Map Key v' -> Map Key v
forall k a b. Ord k => Map k a -> Map k b -> Map k a
M.difference (KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap KeyMap v
tm1) (KeyMap v' -> Map Key v'
forall v. KeyMap v -> Map Key v
unKeyMap KeyMap v'
tm2))

-- The (left-biased) union of two maps. It prefers the first map when duplicate
-- keys are encountered, i.e. ('union' == 'unionWith' 'const').
union :: KeyMap v -> KeyMap v -> KeyMap v
union :: KeyMap v -> KeyMap v -> KeyMap v
union (KeyMap Map Key v
x) (KeyMap Map Key v
y) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap (Map Key v -> Map Key v -> Map Key v
forall k a. Ord k => Map k a -> Map k a -> Map k a
M.union Map Key v
x Map Key v
y)

-- | The union with a combining function.
unionWith :: (v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWith :: (v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWith v -> v -> v
f (KeyMap Map Key v
x) (KeyMap Map Key v
y) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap ((v -> v -> v) -> Map Key v -> Map Key v -> Map Key v
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith v -> v -> v
f Map Key v
x Map Key v
y)

-- | The union with a combining function.
unionWithKey :: (Key -> v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWithKey :: (Key -> v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWithKey Key -> v -> v -> v
f (KeyMap Map Key v
x) (KeyMap Map Key v
y) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> v -> v -> v) -> Map Key v -> Map Key v -> Map Key v
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWithKey Key -> v -> v -> v
f Map Key v
x Map Key v
y)

-- | The (left-biased) intersection of two maps (based on keys).
intersection :: KeyMap a -> KeyMap b -> KeyMap a
intersection :: KeyMap a -> KeyMap b -> KeyMap a
intersection (KeyMap Map Key a
x) (KeyMap Map Key b
y) = Map Key a -> KeyMap a
forall v. Map Key v -> KeyMap v
KeyMap (Map Key a -> Map Key b -> Map Key a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
M.intersection Map Key a
x Map Key b
y)

-- | The intersection with a combining function.
intersectionWith :: (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWith :: (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWith a -> b -> c
f (KeyMap Map Key a
x) (KeyMap Map Key b
y) = Map Key c -> KeyMap c
forall v. Map Key v -> KeyMap v
KeyMap ((a -> b -> c) -> Map Key a -> Map Key b -> Map Key c
forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
M.intersectionWith a -> b -> c
f Map Key a
x Map Key b
y)

-- | The intersection with a combining function.
intersectionWithKey :: (Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWithKey :: (Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWithKey Key -> a -> b -> c
f (KeyMap Map Key a
x) (KeyMap Map Key b
y) = Map Key c -> KeyMap c
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> a -> b -> c) -> Map Key a -> Map Key b -> Map Key c
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
M.intersectionWithKey Key -> a -> b -> c
f Map Key a
x Map Key b
y)

-- | Return a list of this map's keys.
keys :: KeyMap v -> [Key]
keys :: KeyMap v -> [Key]
keys = Map Key v -> [Key]
forall k a. Map k a -> [k]
M.keys (Map Key v -> [Key])
-> (KeyMap v -> Map Key v) -> KeyMap v -> [Key]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Convert a 'KeyMap' to a 'HashMap'.
toHashMap :: KeyMap v -> HashMap Key v
toHashMap :: KeyMap v -> HashMap Key v
toHashMap = [(Key, v)] -> HashMap Key v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
H.fromList ([(Key, v)] -> HashMap Key v)
-> (KeyMap v -> [(Key, v)]) -> KeyMap v -> HashMap Key v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList

-- | Convert a 'HashMap' to a 'KeyMap'.
fromHashMap :: HashMap Key v -> KeyMap v
fromHashMap :: HashMap Key v -> KeyMap v
fromHashMap = [(Key, v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList ([(Key, v)] -> KeyMap v)
-> (HashMap Key v -> [(Key, v)]) -> HashMap Key v -> KeyMap v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap Key v -> [(Key, v)]
forall k v. HashMap k v -> [(k, v)]
H.toList

-- | Convert a 'KeyMap' to a 'Map'.
toMap :: KeyMap v -> Map Key v
toMap :: KeyMap v -> Map Key v
toMap = KeyMap v -> Map Key v
forall v. KeyMap v -> Map Key v
unKeyMap

-- | Convert a 'Map' to a 'KeyMap'.
fromMap :: Map Key v -> KeyMap v
fromMap :: Map Key v -> KeyMap v
fromMap = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap

coercionToHashMap :: Maybe (Coercion (HashMap Key v) (KeyMap v))
coercionToHashMap :: Maybe (Coercion (HashMap Key v) (KeyMap v))
coercionToHashMap = Maybe (Coercion (HashMap Key v) (KeyMap v))
forall a. Maybe a
Nothing
{-# INLINE coercionToHashMap #-}

coercionToMap :: Maybe (Coercion (Map Key v) (KeyMap v))
coercionToMap :: Maybe (Coercion (Map Key v) (KeyMap v))
coercionToMap = Coercion (Map Key v) (KeyMap v)
-> Maybe (Coercion (Map Key v) (KeyMap v))
forall a. a -> Maybe a
Just Coercion (Map Key v) (KeyMap v)
forall k (a :: k) (b :: k). Coercible a b => Coercion a b
Coercion
{-# INLINE coercionToMap #-}

-- | Transform the keys and values of a 'KeyMap'.
mapKeyVal :: (Key -> Key) -> (v1 -> v2)
          -> KeyMap v1 -> KeyMap v2
mapKeyVal :: (Key -> Key) -> (v1 -> v2) -> KeyMap v1 -> KeyMap v2
mapKeyVal Key -> Key
fk v1 -> v2
kv = (Key -> v1 -> KeyMap v2 -> KeyMap v2)
-> KeyMap v2 -> KeyMap v1 -> KeyMap v2
forall v a. (Key -> v -> a -> a) -> a -> KeyMap v -> a
foldrWithKey (\Key
k v1
v -> Key -> v2 -> KeyMap v2 -> KeyMap v2
forall v. Key -> v -> KeyMap v -> KeyMap v
insert (Key -> Key
fk Key
k) (v1 -> v2
kv v1
v)) KeyMap v2
forall v. KeyMap v
empty
{-# INLINE mapKeyVal #-}

-- | Filter all keys/values that satisfy some predicate.
filter :: (v -> Bool) -> KeyMap v -> KeyMap v
filter :: (v -> Bool) -> KeyMap v -> KeyMap v
filter v -> Bool
f (KeyMap Map Key v
m) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap ((v -> Bool) -> Map Key v -> Map Key v
forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter v -> Bool
f Map Key v
m)

-- | Filter all keys/values that satisfy some predicate.
filterWithKey :: (Key -> v -> Bool) -> KeyMap v -> KeyMap v
filterWithKey :: (Key -> v -> Bool) -> KeyMap v -> KeyMap v
filterWithKey Key -> v -> Bool
f (KeyMap Map Key v
m) = Map Key v -> KeyMap v
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> v -> Bool) -> Map Key v -> Map Key v
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
M.filterWithKey Key -> v -> Bool
f Map Key v
m)

-- | Map values and collect the Just results.
mapMaybe :: (a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybe :: (a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybe a -> Maybe b
f (KeyMap Map Key a
m) = Map Key b -> KeyMap b
forall v. Map Key v -> KeyMap v
KeyMap ((a -> Maybe b) -> Map Key a -> Map Key b
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
M.mapMaybe a -> Maybe b
f Map Key a
m)

-- | Map values and collect the Just results.
mapMaybeWithKey :: (Key -> v -> Maybe u) -> KeyMap v -> KeyMap u
mapMaybeWithKey :: (Key -> v -> Maybe u) -> KeyMap v -> KeyMap u
mapMaybeWithKey Key -> v -> Maybe u
f (KeyMap Map Key v
m) = Map Key u -> KeyMap u
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> v -> Maybe u) -> Map Key v -> Map Key u
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
M.mapMaybeWithKey Key -> v -> Maybe u
f Map Key v
m)

#else

-------------------------------------------------------------------------------
-- HashMap
-------------------------------------------------------------------------------

import Data.List (sortBy)
import Data.Ord (comparing)
import Prelude (fst)

-- | A map from JSON key type 'Key' to 'v'.
newtype KeyMap v = KeyMap { unKeyMap :: HashMap Key v }
  deriving (Eq, Ord, Typeable, Data, Functor)

-- | Construct an empty map.
empty :: KeyMap v
empty = KeyMap H.empty

-- | Is the map empty?
null :: KeyMap v -> Bool
null = H.null . unKeyMap

-- | Return the number of key-value mappings in this map.
size :: KeyMap v -> Int
size = H.size . unKeyMap

-- | Construct a map with a single element.
singleton :: Key -> v -> KeyMap v
singleton k v = KeyMap (H.singleton k v)

-- | Is the key a member of the map?
member :: Key -> KeyMap a -> Bool
member t (KeyMap m) = H.member t m

-- | Remove the mapping for the specified key from this map if present.
delete :: Key -> KeyMap v -> KeyMap v
delete k (KeyMap m) = KeyMap (H.delete k m)

-- | 'alterF' can be used to insert, delete, or update a value in a map.
alterF :: Functor f => (Maybe v -> f (Maybe v)) -> Key -> KeyMap v -> f (KeyMap v)
alterF f k = fmap KeyMap . H.alterF f k . unKeyMap

-- | Return the value to which the specified key is mapped,
-- or Nothing if this map contains no mapping for the key.
lookup :: Key -> KeyMap v -> Maybe v
lookup t tm = H.lookup t (unKeyMap tm)

-- | Associate the specified value with the specified key
-- in this map. If this map previously contained a mapping
-- for the key, the old value is replaced.
insert :: Key -> v -> KeyMap v -> KeyMap v
insert k v tm = KeyMap (H.insert k v (unKeyMap tm))

-- | Map a function over all values in the map.
map :: (a -> b) -> KeyMap a -> KeyMap b
map = fmap

-- | Map a function over all values in the map.
mapWithKey :: (Key -> a -> b) -> KeyMap a -> KeyMap b
mapWithKey f (KeyMap m) = KeyMap (H.mapWithKey f m)

foldMapWithKey :: Monoid m => (Key -> a -> m) -> KeyMap a -> m
foldMapWithKey f (KeyMap m) = H.foldMapWithKey f m

foldr :: (a -> b -> b) -> b -> KeyMap a -> b
foldr f z (KeyMap m) = H.foldr f z m

foldr' :: (a -> b -> b) -> b -> KeyMap a -> b
foldr' f z (KeyMap m) = H.foldr' f z m

foldl :: (b -> a -> b) -> b -> KeyMap a -> b
foldl f z (KeyMap m) = H.foldl f z m

foldl' :: (b -> a -> b) -> b -> KeyMap a -> b
foldl' f z (KeyMap m) = H.foldl' f z m

-- | Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator).
foldrWithKey :: (Key -> v -> a -> a) -> a -> KeyMap v -> a
foldrWithKey f a = H.foldrWithKey f a . unKeyMap

-- | Perform an Applicative action for each key-value pair
-- in a 'KeyMap' and produce a 'KeyMap' of all the results.
traverse :: Applicative f => (v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverse f = fmap KeyMap . T.traverse f . unKeyMap

-- | Perform an Applicative action for each key-value pair
-- in a 'KeyMap' and produce a 'KeyMap' of all the results.
traverseWithKey :: Applicative f => (Key -> v1 -> f v2) -> KeyMap v1 -> f (KeyMap v2)
traverseWithKey f = fmap KeyMap . H.traverseWithKey f  . unKeyMap

-- | Construct a map from a list of elements. Uses the
-- provided function, f, to merge duplicate entries with
-- (f newVal oldVal).
fromListWith :: (v -> v -> v) ->  [(Key, v)] -> KeyMap v
fromListWith op = KeyMap . H.fromListWith op

-- |  Construct a map with the supplied mappings. If the
-- list contains duplicate mappings, the later mappings take
-- precedence.
fromList :: [(Key, v)] -> KeyMap v
fromList = KeyMap . H.fromList

-- | Return a list of this map's elements.
--
-- The order is not stable. Use 'toAscList' for stable ordering.
toList :: KeyMap v -> [(Key, v)]
toList = H.toList . unKeyMap

-- | Return a list of this map' elements.
--
-- @since 2.0.2.0
elems :: KeyMap v -> [v]
elems = H.elems . unKeyMap

-- | Return a list of this map's elements in ascending order
-- based of the textual key.
toAscList :: KeyMap v -> [(Key, v)]
toAscList = sortBy (comparing fst) . toList

-- | Difference of two maps. Return elements of the first
-- map not existing in the second.
difference :: KeyMap v -> KeyMap v' -> KeyMap v
difference tm1 tm2 = KeyMap (H.difference (unKeyMap tm1) (unKeyMap tm2))

-- The (left-biased) union of two maps. It prefers the first map when duplicate
-- keys are encountered, i.e. ('union' == 'unionWith' 'const').
union :: KeyMap v -> KeyMap v -> KeyMap v
union (KeyMap x) (KeyMap y) = KeyMap (H.union x y)

-- | The union with a combining function.
unionWith :: (v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWith f (KeyMap x) (KeyMap y) = KeyMap (H.unionWith f x y)

-- | The union with a combining function.
unionWithKey :: (Key -> v -> v -> v) -> KeyMap v -> KeyMap v -> KeyMap v
unionWithKey f (KeyMap x) (KeyMap y) = KeyMap (H.unionWithKey f x y)

-- | The (left-biased) intersection of two maps (based on keys).
intersection :: KeyMap a -> KeyMap b -> KeyMap a
intersection (KeyMap x) (KeyMap y) = KeyMap (H.intersection x y)

-- | The intersection with a combining function.
intersectionWith :: (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWith f (KeyMap x) (KeyMap y) = KeyMap (H.intersectionWith f x y)

-- | The intersection with a combining function.
intersectionWithKey :: (Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWithKey f (KeyMap x) (KeyMap y) = KeyMap (H.intersectionWithKey f x y)

-- | Return a list of this map's keys.
keys :: KeyMap v -> [Key]
keys = H.keys . unKeyMap

-- | Convert a 'KeyMap' to a 'HashMap'.
toHashMap :: KeyMap v -> HashMap Key v
toHashMap = unKeyMap

-- | Convert a 'HashMap' to a 'KeyMap'.
fromHashMap :: HashMap Key v -> KeyMap v
fromHashMap = KeyMap

-- | Convert a 'KeyMap' to a 'Map'.
toMap :: KeyMap v -> Map Key v
toMap = M.fromList . toList

-- | Convert a 'Map' to a 'KeyMap'.
fromMap :: Map Key v -> KeyMap v
fromMap = fromList . M.toList

coercionToHashMap :: Maybe (Coercion (HashMap Key v) (KeyMap v))
coercionToHashMap = Just Coercion
{-# INLINE coercionToHashMap #-}

coercionToMap :: Maybe (Coercion (Map Key v) (KeyMap v))
coercionToMap = Nothing
{-# INLINE coercionToMap #-}

-- | Transform the keys and values of a 'KeyMap'.
mapKeyVal :: (Key -> Key) -> (v1 -> v2)
          -> KeyMap v1 -> KeyMap v2
mapKeyVal fk kv = foldrWithKey (\k v -> insert (fk k) (kv v)) empty
{-# INLINE mapKeyVal #-}

-- | Filter all keys/values that satisfy some predicate.
filter :: (v -> Bool) -> KeyMap v -> KeyMap v
filter f (KeyMap m) = KeyMap (H.filter f m)

-- | Filter all keys/values that satisfy some predicate.
filterWithKey :: (Key -> v -> Bool) -> KeyMap v -> KeyMap v
filterWithKey f (KeyMap m) = KeyMap (H.filterWithKey f m)

-- | Map values and collect the Just results.
mapMaybe :: (a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybe f (KeyMap m) = KeyMap (H.mapMaybe f m)

-- | Map values and collect the Just results.
mapMaybeWithKey :: (Key -> v -> Maybe u) -> KeyMap v -> KeyMap u
mapMaybeWithKey f (KeyMap m) = KeyMap (H.mapMaybeWithKey f m)

#endif

-------------------------------------------------------------------------------
-- combinators using existing abstractions
-------------------------------------------------------------------------------

-- | Generalized union with combining function.
alignWith :: (These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWith :: (These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWith These a b -> c
f (KeyMap Map Key a
x) (KeyMap Map Key b
y) = Map Key c -> KeyMap c
forall v. Map Key v -> KeyMap v
KeyMap ((These a b -> c) -> Map Key a -> Map Key b -> Map Key c
forall (f :: * -> *) a b c.
Semialign f =>
(These a b -> c) -> f a -> f b -> f c
SA.alignWith These a b -> c
f Map Key a
x Map Key b
y)

-- | Generalized union with combining function.
alignWithKey :: (Key -> These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWithKey :: (Key -> These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWithKey Key -> These a b -> c
f (KeyMap Map Key a
x) (KeyMap Map Key b
y) = Map Key c -> KeyMap c
forall v. Map Key v -> KeyMap v
KeyMap ((Key -> These a b -> c) -> Map Key a -> Map Key b -> Map Key c
forall i (f :: * -> *) a b c.
SemialignWithIndex i f =>
(i -> These a b -> c) -> f a -> f b -> f c
SAI.ialignWith Key -> These a b -> c
f Map Key a
x Map Key b
y)

-- | Convert a 'KeyMap' to a @'HashMap' 'Text'@.
toHashMapText :: KeyMap v -> HashMap Text  v
toHashMapText :: KeyMap v -> HashMap Text v
toHashMapText = [(Text, v)] -> HashMap Text v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
H.fromList ([(Text, v)] -> HashMap Text v)
-> (KeyMap v -> [(Text, v)]) -> KeyMap v -> HashMap Text v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Key, v) -> (Text, v)) -> [(Key, v)] -> [(Text, v)]
forall a b. (a -> b) -> [a] -> [b]
L.map ((Key -> Text) -> (Key, v) -> (Text, v)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Key -> Text
Key.toText) ([(Key, v)] -> [(Text, v)])
-> (KeyMap v -> [(Key, v)]) -> KeyMap v -> [(Text, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList

-- | Convert a @'HashMap' 'Text'@to a 'KeyMap'.
fromHashMapText :: HashMap Text v -> KeyMap v
fromHashMapText :: HashMap Text v -> KeyMap v
fromHashMapText = [(Key, v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList ([(Key, v)] -> KeyMap v)
-> (HashMap Text v -> [(Key, v)]) -> HashMap Text v -> KeyMap v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Text, v) -> (Key, v)) -> [(Text, v)] -> [(Key, v)]
forall a b. (a -> b) -> [a] -> [b]
L.map ((Text -> Key) -> (Text, v) -> (Key, v)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Text -> Key
Key.fromText) ([(Text, v)] -> [(Key, v)])
-> (HashMap Text v -> [(Text, v)]) -> HashMap Text v -> [(Key, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap Text v -> [(Text, v)]
forall k v. HashMap k v -> [(k, v)]
H.toList

-- | Convert a 'KeyMap' to a @'Map' 'Text'@.
--
-- @since 2.0.2.0
toMapText :: KeyMap v -> Map Text v
toMapText :: KeyMap v -> Map Text v
toMapText = [(Text, v)] -> Map Text v
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(Text, v)] -> Map Text v)
-> (KeyMap v -> [(Text, v)]) -> KeyMap v -> Map Text v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Key, v) -> (Text, v)) -> [(Key, v)] -> [(Text, v)]
forall a b. (a -> b) -> [a] -> [b]
L.map ((Key -> Text) -> (Key, v) -> (Text, v)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Key -> Text
Key.toText) ([(Key, v)] -> [(Text, v)])
-> (KeyMap v -> [(Key, v)]) -> KeyMap v -> [(Text, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList

-- | Convert a @'Map' 'Text'@to a 'KeyMap'.
--
-- @since 2.0.2.0
fromMapText :: Map Text v -> KeyMap v
fromMapText :: Map Text v -> KeyMap v
fromMapText = [(Key, v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList ([(Key, v)] -> KeyMap v)
-> (Map Text v -> [(Key, v)]) -> Map Text v -> KeyMap v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Text, v) -> (Key, v)) -> [(Text, v)] -> [(Key, v)]
forall a b. (a -> b) -> [a] -> [b]
L.map ((Text -> Key) -> (Text, v) -> (Key, v)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Text -> Key
Key.fromText) ([(Text, v)] -> [(Key, v)])
-> (Map Text v -> [(Text, v)]) -> Map Text v -> [(Key, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map Text v -> [(Text, v)]
forall k a. Map k a -> [(k, a)]
M.toList

-------------------------------------------------------------------------------
-- Instances
-------------------------------------------------------------------------------

-- This are defined using concrete combinators above.

instance Read v => Read (KeyMap v) where
    readPrec :: ReadPrec (KeyMap v)
readPrec = ReadPrec (KeyMap v) -> ReadPrec (KeyMap v)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (KeyMap v) -> ReadPrec (KeyMap v))
-> ReadPrec (KeyMap v) -> ReadPrec (KeyMap v)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (KeyMap v) -> ReadPrec (KeyMap v)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (KeyMap v) -> ReadPrec (KeyMap v))
-> ReadPrec (KeyMap v) -> ReadPrec (KeyMap v)
forall a b. (a -> b) -> a -> b
$ do
      Ident [Char]
"fromList" <- ReadPrec Lexeme
lexP
      [(Key, v)]
xs <- ReadPrec [(Key, v)]
forall a. Read a => ReadPrec a
readPrec
      KeyMap v -> ReadPrec (KeyMap v)
forall (m :: * -> *) a. Monad m => a -> m a
return ([(Key, v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList [(Key, v)]
xs)

    readListPrec :: ReadPrec [KeyMap v]
readListPrec = ReadPrec [KeyMap v]
forall a. Read a => ReadPrec [a]
readListPrecDefault

instance Show v => Show (KeyMap v) where
    showsPrec :: Int -> KeyMap v -> ShowS
showsPrec Int
d KeyMap v
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      [Char] -> ShowS
showString [Char]
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Key, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toAscList KeyMap v
m)

instance F.Foldable KeyMap where
    foldMap :: (a -> m) -> KeyMap a -> m
foldMap a -> m
f = (Key -> a -> m) -> KeyMap a -> m
forall m a. Monoid m => (Key -> a -> m) -> KeyMap a -> m
foldMapWithKey (\ Key
_k a
v -> a -> m
f a
v)
    {-# INLINE foldMap #-}
    foldr :: (a -> b -> b) -> b -> KeyMap a -> b
foldr = (a -> b -> b) -> b -> KeyMap a -> b
forall a b. (a -> b -> b) -> b -> KeyMap a -> b
foldr
    foldr' :: (a -> b -> b) -> b -> KeyMap a -> b
foldr' = (a -> b -> b) -> b -> KeyMap a -> b
forall a b. (a -> b -> b) -> b -> KeyMap a -> b
foldr'
    foldl :: (b -> a -> b) -> b -> KeyMap a -> b
foldl = (b -> a -> b) -> b -> KeyMap a -> b
forall b a. (b -> a -> b) -> b -> KeyMap a -> b
foldl
    foldl' :: (b -> a -> b) -> b -> KeyMap a -> b
foldl' = (b -> a -> b) -> b -> KeyMap a -> b
forall b a. (b -> a -> b) -> b -> KeyMap a -> b
foldl'
    null :: KeyMap a -> Bool
null = KeyMap a -> Bool
forall a. KeyMap a -> Bool
null
    length :: KeyMap a -> Int
length = KeyMap a -> Int
forall a. KeyMap a -> Int
size

instance T.Traversable KeyMap where
    traverse :: (a -> f b) -> KeyMap a -> f (KeyMap b)
traverse = (a -> f b) -> KeyMap a -> f (KeyMap b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> KeyMap a -> f (KeyMap b)
traverse

instance Semigroup (KeyMap v) where
    <> :: KeyMap v -> KeyMap v -> KeyMap v
(<>) = KeyMap v -> KeyMap v -> KeyMap v
forall v. KeyMap v -> KeyMap v -> KeyMap v
union

instance Monoid (KeyMap v) where
    mempty :: KeyMap v
mempty = KeyMap v
forall v. KeyMap v
empty
    mappend :: KeyMap v -> KeyMap v -> KeyMap v
mappend = KeyMap v -> KeyMap v -> KeyMap v
forall a. Semigroup a => a -> a -> a
(<>)

-- | @since 2.0.2.0
instance GHC.Exts.IsList (KeyMap v) where
    type Item (KeyMap v) = (Key, v)
    fromList :: [Item (KeyMap v)] -> KeyMap v
fromList = [Item (KeyMap v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList
    toList :: KeyMap v -> [Item (KeyMap v)]
toList   = KeyMap v -> [Item (KeyMap v)]
forall v. KeyMap v -> [(Key, v)]
toAscList

-------------------------------------------------------------------------------
-- template-haskell
-------------------------------------------------------------------------------

instance TH.Lift v => TH.Lift (KeyMap v) where
    lift :: KeyMap v -> Q Exp
lift KeyMap v
m = [| fromList m' |] where m' :: [(Key, v)]
m' = KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList KeyMap v
m

#if MIN_VERSION_template_haskell(2,17,0)
    liftTyped = TH.unsafeCodeCoerce . TH.lift
#elif MIN_VERSION_template_haskell(2,16,0)
    liftTyped :: KeyMap v -> Q (TExp (KeyMap v))
liftTyped = Q Exp -> Q (TExp (KeyMap v))
forall a. Q Exp -> Q (TExp a)
TH.unsafeTExpCoerce (Q Exp -> Q (TExp (KeyMap v)))
-> (KeyMap v -> Q Exp) -> KeyMap v -> Q (TExp (KeyMap v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> Q Exp
forall t. Lift t => t -> Q Exp
TH.lift
#endif

-------------------------------------------------------------------------------
-- hashable
-------------------------------------------------------------------------------

instance Hashable v => Hashable (KeyMap v) where
#ifdef USE_ORDEREDMAP
    hashWithSalt :: Int -> KeyMap v -> Int
hashWithSalt Int
salt (KeyMap Map Key v
m) = (Int -> Key -> v -> Int) -> Int -> Map Key v -> Int
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
M.foldlWithKey'
        (\Int
acc Key
k v
v -> Int
acc Int -> Key -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` Key
k Int -> v -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` v
v)
        (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (Map Key v -> Int
forall k a. Map k a -> Int
M.size Map Key v
m)) Map Key v
m
#else
    hashWithSalt salt (KeyMap hm) = hashWithSalt salt hm
#endif

-------------------------------------------------------------------------------
-- deepseq
-------------------------------------------------------------------------------

instance NFData v => NFData (KeyMap v) where
    rnf :: KeyMap v -> ()
rnf (KeyMap Map Key v
hm) = Map Key v -> ()
forall a. NFData a => a -> ()
rnf Map Key v
hm

-------------------------------------------------------------------------------
-- indexed-traversable
-------------------------------------------------------------------------------

instance WI.FunctorWithIndex Key KeyMap where
    imap :: (Key -> a -> b) -> KeyMap a -> KeyMap b
imap = (Key -> a -> b) -> KeyMap a -> KeyMap b
forall a b. (Key -> a -> b) -> KeyMap a -> KeyMap b
mapWithKey

instance WI.FoldableWithIndex Key KeyMap where
    ifoldr :: (Key -> a -> b -> b) -> b -> KeyMap a -> b
ifoldr   = (Key -> a -> b -> b) -> b -> KeyMap a -> b
forall v a. (Key -> v -> a -> a) -> a -> KeyMap v -> a
foldrWithKey

instance WI.TraversableWithIndex Key KeyMap where
    itraverse :: (Key -> a -> f b) -> KeyMap a -> f (KeyMap b)
itraverse = (Key -> a -> f b) -> KeyMap a -> f (KeyMap b)
forall (f :: * -> *) a b.
Applicative f =>
(Key -> a -> f b) -> KeyMap a -> f (KeyMap b)
traverseWithKey

-------------------------------------------------------------------------------
-- semialign
-------------------------------------------------------------------------------

instance SA.Zip KeyMap where
    zipWith :: (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
zipWith = (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
forall a b c. (a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWith

instance SAI.ZipWithIndex Key KeyMap where
    izipWith :: (Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
izipWith = (Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
forall a b c.
(Key -> a -> b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
intersectionWithKey

instance SA.Semialign KeyMap where
    alignWith :: (These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWith = (These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
forall a b c. (These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWith

instance SAI.SemialignWithIndex Key KeyMap where
    ialignWith :: (Key -> These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
ialignWith = (Key -> These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
forall a b c.
(Key -> These a b -> c) -> KeyMap a -> KeyMap b -> KeyMap c
alignWithKey

instance SA.Align KeyMap where
    nil :: KeyMap a
nil = KeyMap a
forall v. KeyMap v
empty

-------------------------------------------------------------------------------
-- witherable
-------------------------------------------------------------------------------

instance W.Filterable KeyMap where
    filter :: (a -> Bool) -> KeyMap a -> KeyMap a
filter = (a -> Bool) -> KeyMap a -> KeyMap a
forall a. (a -> Bool) -> KeyMap a -> KeyMap a
filter
    mapMaybe :: (a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybe = (a -> Maybe b) -> KeyMap a -> KeyMap b
forall a b. (a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybe

instance W.Witherable KeyMap where

instance W.FilterableWithIndex Key KeyMap where
    ifilter :: (Key -> a -> Bool) -> KeyMap a -> KeyMap a
ifilter = (Key -> a -> Bool) -> KeyMap a -> KeyMap a
forall a. (Key -> a -> Bool) -> KeyMap a -> KeyMap a
filterWithKey
    imapMaybe :: (Key -> a -> Maybe b) -> KeyMap a -> KeyMap b
imapMaybe = (Key -> a -> Maybe b) -> KeyMap a -> KeyMap b
forall a b. (Key -> a -> Maybe b) -> KeyMap a -> KeyMap b
mapMaybeWithKey

instance W.WitherableWithIndex Key KeyMap where

-------------------------------------------------------------------------------
-- QuickCheck
-------------------------------------------------------------------------------

-- | @since 2.0.3.0
instance QC.Arbitrary1 KeyMap where
    liftArbitrary :: Gen a -> Gen (KeyMap a)
liftArbitrary Gen a
a  = ([(Key, a)] -> KeyMap a) -> Gen [(Key, a)] -> Gen (KeyMap a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(Key, a)] -> KeyMap a
forall v. [(Key, v)] -> KeyMap v
fromList (Gen (Key, a) -> Gen [(Key, a)]
forall (f :: * -> *) a. Arbitrary1 f => Gen a -> Gen (f a)
QC.liftArbitrary (Gen a -> Gen (Key, a)
forall (f :: * -> *) a. Arbitrary1 f => Gen a -> Gen (f a)
QC.liftArbitrary Gen a
a))
    liftShrink :: (a -> [a]) -> KeyMap a -> [KeyMap a]
liftShrink a -> [a]
shr KeyMap a
m = ([(Key, a)] -> KeyMap a) -> [[(Key, a)]] -> [KeyMap a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(Key, a)] -> KeyMap a
forall v. [(Key, v)] -> KeyMap v
fromList (((Key, a) -> [(Key, a)]) -> [(Key, a)] -> [[(Key, a)]]
forall (f :: * -> *) a. Arbitrary1 f => (a -> [a]) -> f a -> [f a]
QC.liftShrink ((a -> [a]) -> (Key, a) -> [(Key, a)]
forall (f :: * -> *) a. Arbitrary1 f => (a -> [a]) -> f a -> [f a]
QC.liftShrink a -> [a]
shr) (KeyMap a -> [(Key, a)]
forall v. KeyMap v -> [(Key, v)]
toList KeyMap a
m))

-- | @since 2.0.3.0
instance QC.Arbitrary v => QC.Arbitrary (KeyMap v) where
    arbitrary :: Gen (KeyMap v)
arbitrary = Gen (KeyMap v)
forall (f :: * -> *) a. (Arbitrary1 f, Arbitrary a) => Gen (f a)
QC.arbitrary1
    shrink :: KeyMap v -> [KeyMap v]
shrink    = KeyMap v -> [KeyMap v]
forall (f :: * -> *) a. (Arbitrary1 f, Arbitrary a) => f a -> [f a]
QC.shrink1

-- | @since 2.0.3.0
instance QC.CoArbitrary v => QC.CoArbitrary (KeyMap v) where
    coarbitrary :: KeyMap v -> Gen b -> Gen b
coarbitrary = [(Key, v)] -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
QC.coarbitrary ([(Key, v)] -> Gen b -> Gen b)
-> (KeyMap v -> [(Key, v)]) -> KeyMap v -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList

-- | @since 2.0.3.0
instance QC.Function v => QC.Function (KeyMap v) where
    function :: (KeyMap v -> b) -> KeyMap v :-> b
function = (KeyMap v -> [(Key, v)])
-> ([(Key, v)] -> KeyMap v) -> (KeyMap v -> b) -> KeyMap v :-> b
forall b a c.
Function b =>
(a -> b) -> (b -> a) -> (a -> c) -> a :-> c
QC.functionMap KeyMap v -> [(Key, v)]
forall v. KeyMap v -> [(Key, v)]
toList [(Key, v)] -> KeyMap v
forall v. [(Key, v)] -> KeyMap v
fromList