-- | This module defines a way to prove that a key exists in a map, so that the
-- key can be used to index into the map without using a 'Maybe', or manually
-- handling the \"impossible\" case with 'error' or other partial functions.
--
-- To do this, @'Map' s k v@ has a type parameter @s@ that identifies its set of
-- keys, so that if another map has the same type parameter, you know that map
-- has the same set of keys. There is @'Key' s k@, a type of keys that have been
-- validated to belong to the set identified by @s@, and for which the operation
-- of indexing into a @'Map' s k v@ (only for the same @s@) can proceed without
-- failure (see '!'). The type @s@ itself has no internal structure, rather it
-- is merely a skolem type variable (rank-2 polymorphism
-- 'Control.Monad.ST.runST' trick) introduced by "Data.Reflection".
--
-- Like "Data.Map.Strict", functions in this module are strict in the keys and
-- values. The "Data.Map.Refined" module reuses the same 'Map' type but provides
-- functions that operate lazily on the values.
--
-- = Warning
-- This module together with "Data.Map.Strict" rely on 'Eq' and 'Ord' instances
-- being lawful: that '==' is an equivalence relation, and that the 'Ord'
-- operations define a total order on the quotient defined by this equivalence
-- relation; at least for the subset of keys that are actually encountered at
-- runtime. If this assumption is violated, this module may not be able to
-- uphold its invariants and may throw errors. In particular beware of NaN in
-- 'Float' and 'Double'.
module Data.Map.Strict.Refined
  (
  -- * Map type
    Common.Map
  , Common.Key
  -- * Existentials and common proofs
  , Common.SomeMap(..)
  , Common.withMap
  , Common.SomeMapWith(..)
  , Common.withMapWith
  , Common.Some2MapWith(..)
  , Common.with2MapWith
  , SupersetProof(..)
  , EmptyProof(..)
  -- * Construction
  , Common.empty
  , singleton
  , SingletonProof(..)
  , fromSet
  , Common.fromMap
  , fromTraversableWithKey
  , FromTraversableProof(..)
  -- * Insertion
  , insert
  , InsertProof(..)
  , reinsert
  , insertLookupWithKey
  -- * Deletion/Update
  , Common.delete
  , adjust
  , adjustWithKey
  , update
  , updateLookupWithKey
  -- * Query
  , Common.lookup
  , (Common.!)
  , Common.member
  , Common.lookupLT
  , Common.lookupGT
  , Common.lookupLE
  , Common.lookupGE
  , Common.null
  , Common.isSubmapOfBy
  , SubsetProof(..)
  , Common.disjoint
  , DisjointProof(..)
  -- * Combine
  , zipWithKey
  , bind
  , unionWithKey
  , UnionProof(..)
  , Common.difference
  , DifferenceProof(..)
  , differenceWithKey
  , PartialDifferenceProof(..)
  , intersectionWithKey
  , IntersectionProof(..)
  -- * Traversal
  , mapWithKey
  , traverseWithKey
  , mapAccumLWithKey
  , mapAccumRWithKey
  , mapKeysWith
  , MapProof(..)
  , backpermuteKeys
  -- * Folds
  , Common.foldMapWithKey
  , Common.foldrWithKey
  , Common.foldlWithKey
  , Common.foldrWithKey'
  , Common.foldlWithKey'
  -- * Conversion
  , Common.toMap
  , Common.keysSet
  , Common.toList
  , Common.toDescList
  -- * Filter
  , Common.restrictKeys
  , Common.withoutKeys
  , Common.filterWithKey
  , Common.partitionWithKey
  , PartitionProof(..)
  , Common.spanAntitone
  , PartialPartitionProof(..)
  , mapMaybeWithKey
  , mapEitherWithKey
  , Common.splitLookup
  , SplitProof(..)
  -- * Min/Max
  , updateMinWithKey
  , updateMaxWithKey
  , adjustMinWithKey
  , adjustMaxWithKey
  , Common.minViewWithKey
  , Common.maxViewWithKey
  -- * Casts
  , Common.castKey
  , Common.cast
  , castFlavor
  ) where

import           Data.Coerce
import           Data.Container.Refined.Proofs
import           Data.Container.Refined.Unsafe
import           Data.Functor
import qualified Data.Map.Strict as Map
import           Data.Map.Common.Refined
  ( Map(..), Key, unsafeCastKey, unsafeKey, SomeMapWith(..), Some2MapWith(..)
  , (!)
  )
import qualified Data.Map.Common.Refined as Common
import           Data.Proxy
import           Data.Reflection
import           Data.Traversable
import           Data.Type.Coercion
import           Prelude hiding (lookup, null)
import           Refined
import           Refined.Unsafe


-- | Create a map with a single key-value pair, and return a proof that the
-- key is in the resulting map.
singleton :: forall k a. k -> a -> SomeMapWith (SingletonProof 'Regular k) k a
singleton :: forall k a. k -> a -> SomeMapWith (SingletonProof 'Regular k) k a
singleton k
k a
v = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. k -> a -> Map k a
Map.singleton k
k a
v)
  forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) a r.
Refined (InSet f r) a -> SingletonProof f a r
SingletonProof (forall k s. k -> Key s k
unsafeKey k
k)

-- | Create a map from a set of keys, and a function that for each key computes
-- the corresponding value.
fromSet :: forall s k a. KnownSet s k => (Key s k -> a) -> Map s k a
fromSet :: forall s k a. KnownSet s k => (Key s k -> a) -> Map s k a
fromSet Key s k -> a
f = forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a) -> Set k -> Map k a
Map.fromSet (Key s k -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) (forall {k} (s :: k) a (proxy :: k -> *).
Reifies s a =>
proxy s -> a
reflect forall a b. (a -> b) -> a -> b
$ forall {k} (t :: k). Proxy t
Proxy @s)

-- | Create a map from an arbitrary traversable of key-value pairs.
fromTraversableWithKey
  :: forall t k a. (Traversable t, Ord k)
  => (k -> a -> a -> a)
  -> t (k, a)
  -> SomeMapWith (FromTraversableProof 'Regular t k) k a
fromTraversableWithKey :: forall (t :: * -> *) k a.
(Traversable t, Ord k) =>
(k -> a -> a -> a)
-> t (k, a) -> SomeMapWith (FromTraversableProof 'Regular t k) k a
fromTraversableWithKey k -> a -> a -> a
f t (k, a)
xs = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map Map k a
m) forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) (t :: * -> *) a r.
t (Refined (InSet f r) a) -> FromTraversableProof f t a r
FromTraversableProof t (Key Any k)
proof
  where
    (Map k a
m, t (Key Any k)
proof) = forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL
      (\Map k a
s (k
k, a
v) -> let !s' :: Map k a
s' = forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWithKey k -> a -> a -> a
f k
k a
v Map k a
s in (Map k a
s', forall k s. k -> Key s k
unsafeKey k
k))
      forall k a. Map k a
Map.empty
      t (k, a)
xs

-- | Insert a key-value pair into the map to obtain a potentially larger map,
-- guaranteed to contain the given key. If the key was already present, the
-- associated value is replaced with the supplied value.
insert
  :: forall s k a. Ord k
  => k -> a -> Map s k a -> SomeMapWith (InsertProof 'Regular k s) k a
insert :: forall s k a.
Ord k =>
k -> a -> Map s k a -> SomeMapWith (InsertProof 'Regular k s) k a
insert k
k a
v (Map Map k a
m) = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k a
v Map k a
m)
  forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) a s r.
Refined (InSet f r) a
-> (InSet f s :-> InSet f r) -> InsertProof f a s r
InsertProof (forall k s. k -> Key s k
unsafeKey k
k) forall p q. p :-> q
unsafeSubset

-- | Overwrite a key-value pair that is known to already be in the map. The set
-- of keys remains the same.
reinsert
  :: forall s k a. Ord k
  => Key s k -> a -> Map s k a -> Map s k a
reinsert :: forall s k a. Ord k => Key s k -> a -> Map s k a -> Map s k a
reinsert = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert @k @a

-- | Insert a key-value pair into the map using a combining function, and if
-- the key was already present, the old value is returned along with the proof
-- that the key was present.
insertLookupWithKey
  :: forall s k a. Ord k
  => (Key s k -> a -> a -> a)
  -> k
  -> a
  -> Map s k a
  -> (Maybe (Key s k, a), SomeMapWith (InsertProof 'Regular k s) k a)
insertLookupWithKey :: forall s k a.
Ord k =>
(Key s k -> a -> a -> a)
-> k
-> a
-> Map s k a
-> (Maybe (Key s k, a), SomeMapWith (InsertProof 'Regular k s) k a)
insertLookupWithKey Key s k -> a -> a -> a
f k
k a
v (Map Map k a
m)
  = case forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
Map.insertLookupWithKey (Key s k -> a -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) k
k a
v Map k a
m of
    (Maybe a
v', !Map k a
m') -> ((forall k s. k -> Key s k
unsafeKey k
k,) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
v',)
      forall a b. (a -> b) -> a -> b
$ forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map Map k a
m') forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) a s r.
Refined (InSet f r) a
-> (InSet f s :-> InSet f r) -> InsertProof f a s r
InsertProof (forall k s. k -> Key s k
unsafeKey k
k) forall p q. p :-> q
unsafeSubset

-- | Update the value at a specific key known the be in the map using the given
-- function. The set of keys remains the same.
adjust :: forall s k a. Ord k => (a -> a) -> Key s k -> Map s k a -> Map s k a
adjust :: forall s k a.
Ord k =>
(a -> a) -> Key s k -> Map s k a -> Map s k a
adjust = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust @k @a

-- | If the given key is in the map, update the associated value using the given
-- function with a proof that the key was in the map; otherwise return the map
-- unchanged. In any case the set of keys remains the same.
adjustWithKey
  :: forall s k a. Ord k => (Key s k -> a -> a) -> k -> Map s k a -> Map s k a
adjustWithKey :: forall s k a.
Ord k =>
(Key s k -> a -> a) -> k -> Map s k a -> Map s k a
adjustWithKey = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce
  forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
Map.adjustWithKey @k @a

-- | Update or delete a key known to be in the map using the given function,
-- returning a potentially smaller map.
update
  :: forall s k a. Ord k
  => (a -> Maybe a)
  -> Key s k
  -> Map s k a
  -> SomeMapWith (SupersetProof 'Regular s) k a
update :: forall s k a.
Ord k =>
(a -> Maybe a)
-> Key s k
-> Map s k a
-> SomeMapWith (SupersetProof 'Regular s) k a
update a -> Maybe a
f Key s k
k (Map Map k a
m) = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
Map.update a -> Maybe a
f (forall {k} (p :: k) x. Refined p x -> x
unrefine Key s k
k) Map k a
m)
  forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s r.
(InSet f r :-> InSet f s) -> SupersetProof f s r
SupersetProof forall p q. p :-> q
unsafeSubset

-- | If the given key is in the map, update or delete it using the given
-- function with a proof that the key was in the map; otherwise the map is
-- unchanged. Alongside return the new value if it was updated, or the old value
-- if it was deleted, and a proof that the key was in the map.
updateLookupWithKey
  :: forall s k a. Ord k
  => (Key s k -> a -> Maybe a)
  -> k
  -> Map s k a
  -> (Maybe (Key s k, a), SomeMapWith (SupersetProof 'Regular s) k a)
updateLookupWithKey :: forall s k a.
Ord k =>
(Key s k -> a -> Maybe a)
-> k
-> Map s k a
-> (Maybe (Key s k, a), SomeMapWith (SupersetProof 'Regular s) k a)
updateLookupWithKey Key s k -> a -> Maybe a
f k
k (Map Map k a
m)
  = case forall k a.
Ord k =>
(k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
Map.updateLookupWithKey (Key s k -> a -> Maybe a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) k
k Map k a
m of
    (Maybe a
v', !Map k a
m') -> ((forall k s. k -> Key s k
unsafeKey k
k,) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
v',)
      forall a b. (a -> b) -> a -> b
$ forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map Map k a
m') forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s r.
(InSet f r :-> InSet f s) -> SupersetProof f s r
SupersetProof forall p q. p :-> q
unsafeSubset

-- | Given two maps proven to have the same keys, for each key apply the
-- function to the associated values, to obtain a new map with the same keys.
zipWithKey
  :: forall s k a b c. Ord k
  => (Key s k -> a -> b -> c) -> Map s k a -> Map s k b -> Map s k c
zipWithKey :: forall s k a b c.
Ord k =>
(Key s k -> a -> b -> c) -> Map s k a -> Map s k b -> Map s k c
zipWithKey Key s k -> a -> b -> c
f (Map Map k a
m1) (Map Map k b
m2) = forall s k a. Map k a -> Map s k a
Map
  forall a b. (a -> b) -> a -> b
$ 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
Map.mergeWithKey (\k
k a
x b
y -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ Key s k -> a -> b -> c
f (forall k s. k -> Key s k
unsafeKey k
k) a
x b
y)
    (\Map k a
m -> if forall k a. Map k a -> Bool
Map.null Map k a
m
      then forall k a. Map k a
Map.empty
      else forall a. HasCallStack => [Char] -> a
error [Char]
"zipWithKey: bug: Data.Map.Strict.Refined has been subverted")
    (\Map k b
m -> if forall k a. Map k a -> Bool
Map.null Map k b
m
      then forall k a. Map k a
Map.empty
      else forall a. HasCallStack => [Char] -> a
error [Char]
"zipWithKey: bug: Data.Map.Strict.Refined has been subverted")
    --  ^ Work around https://github.com/haskell/containers/issues/979
    Map k a
m1
    Map k b
m2

-- | Return the union of two maps, with a given combining function for keys that
-- exist in both maps simultaneously.
--
-- You can use 'andLeft' and 'andRight' to obtain @'Key' s k@ and @'Key' t k@
-- respectively.
unionWithKey
  :: forall s t k a. Ord k
  => (Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> a -> a)
  -> Map s k a
  -> Map t k a
  -> SomeMapWith (UnionProof 'Regular s t) k a
unionWithKey :: forall s t k a.
Ord k =>
(Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> a -> a)
-> Map s k a
-> Map t k a
-> SomeMapWith (UnionProof 'Regular s t) k a
unionWithKey Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> a -> a
f (Map Map k a
m1) (Map Map k a
m2)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWithKey (Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} x (p :: k). x -> Refined p x
reallyUnsafeRefine) Map k a
m1 Map k a
m2)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s t r.
((InSet f s || InSet f t) :-> InSet f r)
-> (forall u.
    (InSet f s :-> InSet f u)
    -> (InSet f t :-> InSet f u) -> InSet f r :-> InSet f u)
-> UnionProof f s t r
UnionProof forall p q. p :-> q
unsafeSubset forall p' q' p'' q'' p q. (p' :-> q') -> (p'' :-> q'') -> p :-> q
unsafeSubsetWith2

-- | For keys that appear in both maps, the given function decides whether the
-- key is removed from the first map.
--
-- You can use 'andLeft' and 'andRight' to obtain @'Key' s k@ and @'Key' t k@
-- respectively.
differenceWithKey
  :: forall s t k a b. Ord k
  => (Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> b -> Maybe a)
  -> Map s k a
  -> Map t k b
  -> SomeMapWith (PartialDifferenceProof 'Regular s t) k a
differenceWithKey :: forall s t k a b.
Ord k =>
(Refined (InSet 'Regular s && InSet 'Regular t) k
 -> a -> b -> Maybe a)
-> Map s k a
-> Map t k b
-> SomeMapWith (PartialDifferenceProof 'Regular s t) k a
differenceWithKey Refined (InSet 'Regular s && InSet 'Regular t) k
-> a -> b -> Maybe a
f (Map Map k a
m1) (Map Map k b
m2)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWithKey (Refined (InSet 'Regular s && InSet 'Regular t) k
-> a -> b -> Maybe a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} x (p :: k). x -> Refined p x
reallyUnsafeRefine) Map k a
m1 Map k b
m2)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s t r.
(InSet f r :-> InSet f s)
-> (InSet f s :-> (InSet f t || InSet f r))
-> PartialDifferenceProof f s t r
PartialDifferenceProof forall p q. p :-> q
unsafeSubset forall p q. p :-> q
unsafeSubset

-- | Return the intersection of two maps with the given combining function.
--
-- You can use 'andLeft' and 'andRight' to obtain @'Key' s k@ and @'Key' t k@
-- respectively.
intersectionWithKey
  :: forall s t k a b c. Ord k
  => (Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> b -> c)
  -> Map s k a
  -> Map t k b
  -> SomeMapWith (IntersectionProof 'Regular s t) k c
intersectionWithKey :: forall s t k a b c.
Ord k =>
(Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> b -> c)
-> Map s k a
-> Map t k b
-> SomeMapWith (IntersectionProof 'Regular s t) k c
intersectionWithKey Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> b -> c
f (Map Map k a
m1) (Map Map k b
m2)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
Map.intersectionWithKey (Refined (InSet 'Regular s && InSet 'Regular t) k -> a -> b -> c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} x (p :: k). x -> Refined p x
reallyUnsafeRefine) Map k a
m1 Map k b
m2)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s t r.
(InSet f r :-> (InSet f s && InSet f t))
-> (forall u.
    (InSet f u :-> InSet f s)
    -> (InSet f u :-> InSet f t) -> InSet f u :-> InSet f r)
-> IntersectionProof f s t r
IntersectionProof forall p q. p :-> q
unsafeSubset forall p' q' p'' q'' p q. (p' :-> q') -> (p'' :-> q'') -> p :-> q
unsafeSubsetWith2

-- | Apply a function to all values in a map, together with their corresponding
-- keys, that are proven to be in the map. The set of keys remains the same.
mapWithKey :: forall s k a b. (Key s k -> a -> b) -> Map s k a -> Map s k b
mapWithKey :: forall s k a b. (Key s k -> a -> b) -> Map s k a -> Map s k b
mapWithKey = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce
  forall a b. (a -> b) -> a -> b
$ forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey @k @a @b

-- | Map an 'Applicative' transformation in ascending order of keys, with access
-- to each value's corresponding key and a proof that it is in the map. The set
-- of keys remains unchanged.
traverseWithKey
  :: forall s f k a b. Applicative f
  => (Key s k -> a -> f b) -> Map s k a -> f (Map s k b)
traverseWithKey :: forall s (f :: * -> *) k a b.
Applicative f =>
(Key s k -> a -> f b) -> Map s k a -> f (Map s k b)
traverseWithKey Key s k -> a -> f b
f (Map Map k a
m) = forall s k a. Map k a -> Map s k a
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.traverseWithKey (Key s k -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m

-- | Thread an accumularing argument through the map in ascending order of keys.
mapAccumLWithKey
  :: forall s k a b c. (a -> Key s k -> b -> (a, c))
  -> a
  -> Map s k b
  -> (a, Map s k c)
mapAccumLWithKey :: forall s k a b c.
(a -> Key s k -> b -> (a, c)) -> a -> Map s k b -> (a, Map s k c)
mapAccumLWithKey = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce
  forall a b. (a -> b) -> a -> b
$ forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
Map.mapAccumWithKey @a @k @b @c

-- | Thread an accumularing argument through the map in descending order of
-- keys.
mapAccumRWithKey
  :: forall s k a b c. (a -> Key s k -> b -> (a, c))
  -> a
  -> Map s k b
  -> (a, Map s k c)
mapAccumRWithKey :: forall s k a b c.
(a -> Key s k -> b -> (a, c)) -> a -> Map s k b -> (a, Map s k c)
mapAccumRWithKey = forall {k} (a :: k) (b :: k) r.
Coercion a b -> (Coercible a b => r) -> r
gcoerceWith (forall s k. Coercion k (Key s k)
unsafeCastKey @s @k) forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce
  forall a b. (a -> b) -> a -> b
$ forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
Map.mapAccumRWithKey @a @k @b @c

-- | @'mapKeysWith' c f m@ applies @f@ to each key of @m@ and collects the
-- results into a new map. For keys that were mapped to the same new key, @c@
-- acts as the combining function for corresponding values.
mapKeysWith
  :: forall s k1 k2 a. Ord k2
  => (a -> a -> a)
  -> (Key s k1 -> k2)
  -> Map s k1 a
  -> SomeMapWith (MapProof 'Regular s k1 k2) k2 a
mapKeysWith :: forall s k1 k2 a.
Ord k2 =>
(a -> a -> a)
-> (Key s k1 -> k2)
-> Map s k1 a
-> SomeMapWith (MapProof 'Regular s k1 k2) k2 a
mapKeysWith a -> a -> a
f Key s k1 -> k2
g (Map Map k1 a
m)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith a -> a -> a
f (Key s k1 -> k2
g forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k1 a
m)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s a b r.
(Refined (InSet f s) a -> Refined (InSet f r) b)
-> (Refined (InSet f r) b -> Refined (InSet f s) a)
-> MapProof f s a b r
MapProof (forall k s. k -> Key s k
unsafeKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. Key s k1 -> k2
g) \Refined (InSet 'Regular Any) k2
k2 -> case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (forall {k} (p :: k) x. Refined p x -> x
unrefine Refined (InSet 'Regular Any) k2
k2) Map k2 (Key s k1)
backMap of
      Maybe (Key s k1)
Nothing -> forall a. HasCallStack => [Char] -> a
error
        [Char]
"mapKeysWith: bug: Data.Map.Strict.Refined has been subverted"
      Just Key s k1
k1 -> Key s k1
k1
  where
    ~Map k2 (Key s k1)
backMap = forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList
      [ (k2
k2, forall k s. k -> Key s k
unsafeKey k1
k1)
      | k1
k1 <- forall k a. Map k a -> [k]
Map.keys Map k1 a
m
      , let !k2 :: k2
k2 = Key s k1 -> k2
g forall a b. (a -> b) -> a -> b
$ forall k s. k -> Key s k
unsafeKey k1
k1
      ]

-- | Apply a function to all values in a map, together with their corresponding
-- keys, and collect only the 'Just' results, returning a potentially smaller
-- map.
mapMaybeWithKey
  :: forall s k a b. (Key s k -> a -> Maybe b)
  -> Map s k a
  -> SomeMapWith (SupersetProof 'Regular s) k b
mapMaybeWithKey :: forall s k a b.
(Key s k -> a -> Maybe b)
-> Map s k a -> SomeMapWith (SupersetProof 'Regular s) k b
mapMaybeWithKey Key s k -> a -> Maybe b
f (Map Map k a
m)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey (Key s k -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s r.
(InSet f r :-> InSet f s) -> SupersetProof f s r
SupersetProof forall p q. p :-> q
unsafeSubset

-- | Apply a function to all values in a map, together with their corresponding
-- keys, and collect the 'Left' and 'Right' results into separate (disjoint)
-- maps.
mapEitherWithKey
  :: forall s k a b c. Ord k -- TODO: this is only used in the proof
  => (Key s k -> a -> Either b c)
  -> Map s k a
  -> Some2MapWith (PartitionProof 'Regular s k) k b c
mapEitherWithKey :: forall s k a b c.
Ord k =>
(Key s k -> a -> Either b c)
-> Map s k a -> Some2MapWith (PartitionProof 'Regular s k) k b c
mapEitherWithKey Key s k -> a -> Either b c
p (Map Map k a
m) = case forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
Map.mapEitherWithKey (Key s k -> a -> Either b c
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m of
  (Map k b
m1, Map k c
m2) -> forall s t k a b (p :: * -> * -> *).
Map s k a -> Map t k b -> p s t -> Some2MapWith p k a b
Some2MapWith (forall s k a. Map k a -> Map s k a
Map Map k b
m1) (forall s k a. Map k a -> Map s k a
Map Map k c
m2) forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s a r q.
(Refined (InSet f s) a
 -> Either (Refined (InSet f r) a) (Refined (InSet f q) a))
-> ((InSet f r || InSet f q) :-> InSet f s)
-> (forall t.
    (InSet f r :-> InSet f t)
    -> (InSet f q :-> InSet f t) -> InSet f s :-> InSet f t)
-> (forall t.
    (InSet f t :-> InSet f r)
    -> (InSet f t :-> InSet f q) -> forall u. InSet f t :-> InSet f u)
-> PartitionProof f s a r q
PartitionProof
    do \Key s k
k -> case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (forall {k} (p :: k) x. Refined p x -> x
unrefine Key s k
k) Map k a
m of
        Maybe a
Nothing -> forall a. HasCallStack => [Char] -> a
error
          [Char]
"mapEitherWithKey: bug: Data.Map.Strict.Refined has been subverted"
        Just a
x -> case Key s k -> a -> Either b c
p Key s k
k a
x of
          Left b
_ -> forall a b. a -> Either a b
Left forall a b. (a -> b) -> a -> b
$ forall k s. k -> Key s k
unsafeKey forall a b. (a -> b) -> a -> b
$ forall {k} (p :: k) x. Refined p x -> x
unrefine Key s k
k
          Right c
_ -> forall a b. b -> Either a b
Right forall a b. (a -> b) -> a -> b
$ forall k s. k -> Key s k
unsafeKey forall a b. (a -> b) -> a -> b
$ forall {k} (p :: k) x. Refined p x -> x
unrefine Key s k
k
    forall p q. p :-> q
unsafeSubset forall p' q' p'' q'' p q. (p' :-> q') -> (p'' :-> q'') -> p :-> q
unsafeSubsetWith2 \InSet 'Regular t :-> InSet 'Regular Any
f InSet 'Regular t :-> InSet 'Regular Any
g -> forall p' q' p'' q'' p q. (p' :-> q') -> (p'' :-> q'') -> p :-> q
unsafeSubsetWith2 InSet 'Regular t :-> InSet 'Regular Any
f InSet 'Regular t :-> InSet 'Regular Any
g

-- | Update or delete the value at the smallest key, returning a potentially
-- smaller map.
updateMinWithKey
  :: forall s k a. (Key s k -> a -> Maybe a)
  -> Map s k a
  -> SomeMapWith (SupersetProof 'Regular s) k a
updateMinWithKey :: forall s k a.
(Key s k -> a -> Maybe a)
-> Map s k a -> SomeMapWith (SupersetProof 'Regular s) k a
updateMinWithKey Key s k -> a -> Maybe a
f (Map Map k a
m)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
Map.updateMinWithKey (Key s k -> a -> Maybe a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s r.
(InSet f r :-> InSet f s) -> SupersetProof f s r
SupersetProof forall p q. p :-> q
unsafeSubset

-- | Update or delete the value at the largest key, returning a potentially
-- smaller map.
updateMaxWithKey
  :: forall s k a. (Key s k -> a -> Maybe a)
  -> Map s k a
  -> SomeMapWith (SupersetProof 'Regular s) k a
updateMaxWithKey :: forall s k a.
(Key s k -> a -> Maybe a)
-> Map s k a -> SomeMapWith (SupersetProof 'Regular s) k a
updateMaxWithKey Key s k -> a -> Maybe a
f (Map Map k a
m)
  = forall s k a (p :: * -> *). Map s k a -> p s -> SomeMapWith p k a
SomeMapWith (forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
Map.updateMaxWithKey (Key s k -> a -> Maybe a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m)
    forall a b. (a -> b) -> a -> b
$ forall (f :: Flavor) s r.
(InSet f r :-> InSet f s) -> SupersetProof f s r
SupersetProof forall p q. p :-> q
unsafeSubset

-- | Adjust the value at the smallest key. The set of keys remains unchanged.
adjustMinWithKey :: forall s k a. (Key s k -> a -> a) -> Map s k a -> Map s k a
adjustMinWithKey :: forall s k a. (Key s k -> a -> a) -> Map s k a -> Map s k a
adjustMinWithKey Key s k -> a -> a
f (Map Map k a
m)
  = forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
Map.updateMinWithKey ((forall a. a -> Maybe a
Just forall b c a. (b -> c) -> (a -> b) -> a -> c
.) forall b c a. (b -> c) -> (a -> b) -> a -> c
. Key s k -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m

-- | Adjust the value at the greatest key. The set of keys remains unchanged.
adjustMaxWithKey :: forall s k a. (Key s k -> a -> a) -> Map s k a -> Map s k a
adjustMaxWithKey :: forall s k a. (Key s k -> a -> a) -> Map s k a -> Map s k a
adjustMaxWithKey Key s k -> a -> a
f (Map Map k a
m)
  = forall s k a. Map k a -> Map s k a
Map forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
Map.updateMaxWithKey ((forall a. a -> Maybe a
Just forall b c a. (b -> c) -> (a -> b) -> a -> c
.) forall b c a. (b -> c) -> (a -> b) -> a -> c
. Key s k -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k s. k -> Key s k
unsafeKey) Map k a
m

-- | @'bind' m f@ is a map that for each key @k :: 'Key' s k@, contains the
-- value @f (m '!' k) '!' k@, similar to @'>>='@ for functions.
bind :: forall s k a b. Ord k => Map s k a -> (a -> Map s k b) -> Map s k b
bind :: forall s k a b. Ord k => Map s k a -> (a -> Map s k b) -> Map s k b
bind Map s k a
m a -> Map s k b
f = forall s k a b. (Key s k -> a -> b) -> Map s k a -> Map s k b
mapWithKey (\Key s k
k a
x -> a -> Map s k b
f a
x forall s k a. Ord k => Map s k a -> Key s k -> a
! Key s k
k) Map s k a
m

-- | Apply the inverse image of the given function to the keys of the given map,
-- so that for all @k :: 'Key' s2 k2@,
-- @'backpermuteKeys' f m '!' k = m '!' f k@.
--
-- If maps are identified with functions, this computes the composition.
backpermuteKeys
  :: forall s1 s2 k1 k2 a. (Ord k1, KnownSet s2 k2)
  => (Key s2 k2 -> Key s1 k1) -> Map s1 k1 a -> Map s2 k2 a
backpermuteKeys :: forall s1 s2 k1 k2 a.
(Ord k1, KnownSet s2 k2) =>
(Key s2 k2 -> Key s1 k1) -> Map s1 k1 a -> Map s2 k2 a
backpermuteKeys Key s2 k2 -> Key s1 k1
f Map s1 k1 a
m = forall s k a. KnownSet s k => (Key s k -> a) -> Map s k a
fromSet \Key s2 k2
k -> Map s1 k1 a
m forall s k a. Ord k => Map s k a -> Key s k -> a
! Key s2 k2 -> Key s1 k1
f Key s2 k2
k