{-# LANGUAGE DeriveAnyClass        #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE DeriveGeneric         #-}
{-# LANGUAGE DeriveLift            #-}
{-# LANGUAGE DerivingStrategies    #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE LambdaCase            #-}
{-# LANGUAGE MonoLocalBinds        #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TemplateHaskell       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE UndecidableInstances  #-}
{-# OPTIONS_GHC -Wno-name-shadowing #-}

-- | A map represented as an "association list" of key-value pairs.
module PlutusTx.AssocMap (
  Map,
  singleton,
  empty,
  null,
  unsafeFromList,
  safeFromList,
  toList,
  keys,
  elems,
  lookup,
  member,
  insert,
  delete,
  union,
  unionWith,
  filter,
  mapWithKey,
  mapMaybe,
  mapMaybeWithKey,
  all,
  mapThese,
) where

import Prelude qualified as Haskell

import PlutusTx.Builtins qualified as P hiding (null)
import PlutusTx.Builtins.Internal qualified as BI
import PlutusTx.IsData
import PlutusTx.Lift (makeLift)
import PlutusTx.Prelude hiding (all, filter, mapMaybe, null, toList)
import PlutusTx.Prelude qualified as P
import PlutusTx.These

import Control.DeepSeq (NFData)
import Data.Data
import Data.Function (on)
import Data.Map.Strict qualified as HMap
import GHC.Generics (Generic)
import Language.Haskell.TH.Syntax as TH (Lift)
import Prettyprinter (Pretty (..))

-- See Note [Optimising Value].
-- | A 'Map' of key-value pairs.
-- A 'Map' is considered well-defined if there are no key collisions, meaning that each value
-- is uniquely identified by a key.
--
-- Use 'safeFromList' to create well-defined 'Map's from arbitrary lists of pairs.
--
-- If cost minimisation is required, then you can use 'unsafeFromList' but you must
-- be certain that the list you are converting to a 'Map' abides by the well-definedness condition.
--
-- Most operations on 'Map's are definedness-preserving, meaning that for the resulting 'Map' to be
-- well-defined then the input 'Map'(s) have to also be well-defined. This is not checked explicitly
-- unless mentioned in the documentation.
--
-- Take care when using 'fromBuiltinData' and 'unsafeFromBuiltinData', as neither function performs
-- deduplication of the input collection and may create invalid 'Map's!
newtype Map k v = Map {forall k v. Map k v -> [(k, v)]
unMap :: [(k, v)]}
  deriving stock ((forall x. Map k v -> Rep (Map k v) x)
-> (forall x. Rep (Map k v) x -> Map k v) -> Generic (Map k v)
forall x. Rep (Map k v) x -> Map k v
forall x. Map k v -> Rep (Map k v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (Map k v) x -> Map k v
forall k v x. Map k v -> Rep (Map k v) x
$cfrom :: forall k v x. Map k v -> Rep (Map k v) x
from :: forall x. Map k v -> Rep (Map k v) x
$cto :: forall k v x. Rep (Map k v) x -> Map k v
to :: forall x. Rep (Map k v) x -> Map k v
Generic, Int -> Map k v -> ShowS
[Map k v] -> ShowS
Map k v -> String
(Int -> Map k v -> ShowS)
-> (Map k v -> String) -> ([Map k v] -> ShowS) -> Show (Map k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> Map k v -> ShowS
forall k v. (Show k, Show v) => [Map k v] -> ShowS
forall k v. (Show k, Show v) => Map k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> Map k v -> ShowS
showsPrec :: Int -> Map k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => Map k v -> String
show :: Map k v -> String
$cshowList :: forall k v. (Show k, Show v) => [Map k v] -> ShowS
showList :: [Map k v] -> ShowS
Haskell.Show, Typeable (Map k v)
Typeable (Map k v) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Map k v -> c (Map k v))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Map k v))
-> (Map k v -> Constr)
-> (Map k v -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Map k v)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v)))
-> ((forall b. Data b => b -> b) -> Map k v -> Map k v)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Map k v -> r)
-> (forall u. (forall d. Data d => d -> u) -> Map k v -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Map k v -> m (Map k v))
-> Data (Map k v)
Map k v -> Constr
Map k v -> DataType
(forall b. Data b => b -> b) -> Map k v -> Map k v
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u
forall u. (forall d. Data d => d -> u) -> Map k v -> [u]
forall k v. (Data k, Data v) => Typeable (Map k v)
forall k v. (Data k, Data v) => Map k v -> Constr
forall k v. (Data k, Data v) => Map k v -> DataType
forall k v.
(Data k, Data v) =>
(forall b. Data b => b -> b) -> Map k v -> Map k v
forall k v u.
(Data k, Data v) =>
Int -> (forall d. Data d => d -> u) -> Map k v -> u
forall k v u.
(Data k, Data v) =>
(forall d. Data d => d -> u) -> Map k v -> [u]
forall k v r r'.
(Data k, Data v) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
forall k v r r'.
(Data k, Data v) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
forall k v (m :: * -> *).
(Data k, Data v, Monad m) =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
forall k v (m :: * -> *).
(Data k, Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
forall k v (c :: * -> *).
(Data k, Data v) =>
(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) =>
(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, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
forall k v (t :: * -> * -> *) (c :: * -> *).
(Data k, Data v, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Map k v)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Map k v -> c (Map k v)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
$cgfoldl :: forall k v (c :: * -> *).
(Data k, Data v) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Map k v -> c (Map k v)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Map k v -> c (Map k v)
$cgunfold :: forall k v (c :: * -> *).
(Data k, Data v) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Map k v)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Map k v)
$ctoConstr :: forall k v. (Data k, Data v) => Map k v -> Constr
toConstr :: Map k v -> Constr
$cdataTypeOf :: forall k v. (Data k, Data v) => Map k v -> DataType
dataTypeOf :: Map k v -> DataType
$cdataCast1 :: forall k v (t :: * -> *) (c :: * -> *).
(Data k, Data v, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
$cdataCast2 :: forall k v (t :: * -> * -> *) (c :: * -> *).
(Data k, Data v, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
$cgmapT :: forall k v.
(Data k, Data v) =>
(forall b. Data b => b -> b) -> Map k v -> Map k v
gmapT :: (forall b. Data b => b -> b) -> Map k v -> Map k v
$cgmapQl :: forall k v r r'.
(Data k, Data v) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
$cgmapQr :: forall k v r r'.
(Data k, Data v) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
$cgmapQ :: forall k v u.
(Data k, Data v) =>
(forall d. Data d => d -> u) -> Map k v -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Map k v -> [u]
$cgmapQi :: forall k v u.
(Data k, Data v) =>
Int -> (forall d. Data d => d -> u) -> Map k v -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Map k v -> u
$cgmapM :: forall k v (m :: * -> *).
(Data k, Data v, Monad m) =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
$cgmapMp :: forall k v (m :: * -> *).
(Data k, Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
$cgmapMo :: forall k v (m :: * -> *).
(Data k, Data v, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
Data, (forall (m :: * -> *). Quote m => Map k v -> m Exp)
-> (forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v))
-> Lift (Map k v)
forall k v (m :: * -> *).
(Lift k, Lift v, Quote m) =>
Map k v -> m Exp
forall k v (m :: * -> *).
(Lift k, Lift v, Quote m) =>
Map k v -> Code m (Map k v)
forall t.
(forall (m :: * -> *). Quote m => t -> m Exp)
-> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
forall (m :: * -> *). Quote m => Map k v -> m Exp
forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v)
$clift :: forall k v (m :: * -> *).
(Lift k, Lift v, Quote m) =>
Map k v -> m Exp
lift :: forall (m :: * -> *). Quote m => Map k v -> m Exp
$cliftTyped :: forall k v (m :: * -> *).
(Lift k, Lift v, Quote m) =>
Map k v -> Code m (Map k v)
liftTyped :: forall (m :: * -> *). Quote m => Map k v -> Code m (Map k v)
TH.Lift)
  deriving newtype (Map k v -> ()
(Map k v -> ()) -> NFData (Map k v)
forall a. (a -> ()) -> NFData a
forall k v. (NFData k, NFData v) => Map k v -> ()
$crnf :: forall k v. (NFData k, NFData v) => Map k v -> ()
rnf :: Map k v -> ()
NFData)

instance (Haskell.Ord k, Haskell.Eq v) => Haskell.Eq (Map k v) where
  Map [(k, v)]
l == :: Map k v -> Map k v -> Bool
== Map [(k, v)]
r =
    (Map k v -> Map k v -> Bool)
-> ([(k, v)] -> Map k v) -> [(k, v)] -> [(k, v)] -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on Map k v -> Map k v -> Bool
forall a. Eq a => a -> a -> Bool
(Haskell.==) [(k, v)] -> Map k v
forall k a. Ord k => [(k, a)] -> Map k a
HMap.fromList [(k, v)]
l [(k, v)]
r

instance (Haskell.Ord k, Haskell.Ord v) => Haskell.Ord (Map k v) where
  Map [(k, v)]
l <= :: Map k v -> Map k v -> Bool
<= Map [(k, v)]
r =
    (Map k v -> Map k v -> Bool)
-> ([(k, v)] -> Map k v) -> [(k, v)] -> [(k, v)] -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on Map k v -> Map k v -> Bool
forall a. Ord a => a -> a -> Bool
(Haskell.<=) [(k, v)] -> Map k v
forall k a. Ord k => [(k, a)] -> Map k a
HMap.fromList [(k, v)]
l [(k, v)]
r

-- | Hand-written instances to use the underlying 'Map' type in 'Data', and
-- to be reasonably efficient.
instance (ToData k, ToData v) => ToData (Map k v) where
  toBuiltinData :: Map k v -> BuiltinData
toBuiltinData (Map [(k, v)]
es) = BuiltinList (BuiltinPair BuiltinData BuiltinData) -> BuiltinData
BI.mkMap ([(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
mapToBuiltin [(k, v)]
es)
    where
      {-# INLINE mapToBuiltin #-}
      mapToBuiltin :: [(k, v)] -> BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData)
      mapToBuiltin :: [(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
mapToBuiltin = [(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
go
        where
          go :: [(k, v)] -> BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData)
          go :: [(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
go []            = BuiltinUnit -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
BI.mkNilPairData BuiltinUnit
BI.unitval
          go ((k
k, v
v) : [(k, v)]
xs) = BuiltinPair BuiltinData BuiltinData
-> BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> BuiltinList (BuiltinPair BuiltinData BuiltinData)
forall a. a -> BuiltinList a -> BuiltinList a
BI.mkCons (BuiltinData -> BuiltinData -> BuiltinPair BuiltinData BuiltinData
BI.mkPairData (k -> BuiltinData
forall a. ToData a => a -> BuiltinData
toBuiltinData k
k) (v -> BuiltinData
forall a. ToData a => a -> BuiltinData
toBuiltinData v
v)) ([(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
go [(k, v)]
xs)

-- | A hand-written transformation from 'Data' to 'Map'. Compared to 'unsafeFromBuiltinData',
-- it is safe to call when it is unknown if the 'Data' is built with 'Data's 'Map' constructor.
-- Note that it is, however, unsafe in the sense that it assumes that any map
-- encoded in the 'Data' is well-formed, i.e. 'fromBuiltinData' does not perform any
-- deduplication of keys or of key-value pairs!
instance (FromData k, FromData v) => FromData (Map k v) where
  fromBuiltinData :: BuiltinData -> Maybe (Map k v)
fromBuiltinData BuiltinData
d =
    BuiltinData
-> (Integer -> BuiltinList BuiltinData -> Maybe (Map k v))
-> (BuiltinList (BuiltinPair BuiltinData BuiltinData)
    -> Maybe (Map k v))
-> (BuiltinList BuiltinData -> Maybe (Map k v))
-> (Integer -> Maybe (Map k v))
-> (BuiltinByteString -> Maybe (Map k v))
-> Maybe (Map k v)
forall r.
BuiltinData
-> (Integer -> BuiltinList BuiltinData -> r)
-> (BuiltinList (BuiltinPair BuiltinData BuiltinData) -> r)
-> (BuiltinList BuiltinData -> r)
-> (Integer -> r)
-> (BuiltinByteString -> r)
-> r
P.matchData'
      BuiltinData
d
      (\Integer
_ BuiltinList BuiltinData
_ -> Maybe (Map k v)
forall a. Maybe a
Nothing)
      (\BuiltinList (BuiltinPair BuiltinData BuiltinData)
es -> [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([(k, v)] -> Map k v) -> Maybe [(k, v)] -> Maybe (Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
traverseFromBuiltin BuiltinList (BuiltinPair BuiltinData BuiltinData)
es)
      (Maybe (Map k v) -> BuiltinList BuiltinData -> Maybe (Map k v)
forall a b. a -> b -> a
const Maybe (Map k v)
forall a. Maybe a
Nothing)
      (Maybe (Map k v) -> Integer -> Maybe (Map k v)
forall a b. a -> b -> a
const Maybe (Map k v)
forall a. Maybe a
Nothing)
      (Maybe (Map k v) -> BuiltinByteString -> Maybe (Map k v)
forall a b. a -> b -> a
const Maybe (Map k v)
forall a. Maybe a
Nothing)
    where
      {-# INLINE traverseFromBuiltin #-}
      traverseFromBuiltin ::
        BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData) ->
        Maybe [(k, v)]
      traverseFromBuiltin :: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
traverseFromBuiltin = BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
go
        where
          go :: BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData) -> Maybe [(k, v)]
          go :: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
go BuiltinList (BuiltinPair BuiltinData BuiltinData)
l =
            BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> (() -> Maybe [(k, v)])
-> (() -> Maybe [(k, v)])
-> ()
-> Maybe [(k, v)]
forall a b. BuiltinList a -> b -> b -> b
BI.chooseList
              BuiltinList (BuiltinPair BuiltinData BuiltinData)
l
              (Maybe [(k, v)] -> () -> Maybe [(k, v)]
forall a b. a -> b -> a
const ([(k, v)] -> Maybe [(k, v)]
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure []))
              ( \()
_ ->
                  let tup :: BuiltinPair BuiltinData BuiltinData
tup = BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> BuiltinPair BuiltinData BuiltinData
forall a. BuiltinList a -> a
BI.head BuiltinList (BuiltinPair BuiltinData BuiltinData)
l
                   in ((k, v) -> [(k, v)] -> [(k, v)])
-> Maybe (k, v) -> Maybe [(k, v)] -> Maybe [(k, v)]
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2
                        (:)
                        ((k -> v -> (k, v)) -> Maybe k -> Maybe v -> Maybe (k, v)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (,) (BuiltinData -> Maybe k
forall a. FromData a => BuiltinData -> Maybe a
fromBuiltinData (BuiltinData -> Maybe k) -> BuiltinData -> Maybe k
forall a b. (a -> b) -> a -> b
$ BuiltinPair BuiltinData BuiltinData -> BuiltinData
forall a b. BuiltinPair a b -> a
BI.fst BuiltinPair BuiltinData BuiltinData
tup) (BuiltinData -> Maybe v
forall a. FromData a => BuiltinData -> Maybe a
fromBuiltinData (BuiltinData -> Maybe v) -> BuiltinData -> Maybe v
forall a b. (a -> b) -> a -> b
$ BuiltinPair BuiltinData BuiltinData -> BuiltinData
forall a b. BuiltinPair a b -> b
BI.snd BuiltinPair BuiltinData BuiltinData
tup))
                        (BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
go (BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> BuiltinList (BuiltinPair BuiltinData BuiltinData)
forall a. BuiltinList a -> BuiltinList a
BI.tail BuiltinList (BuiltinPair BuiltinData BuiltinData)
l))
              )
              ()

-- | A hand-written transformation from 'Data' to 'Map'. It is unsafe because the
-- caller must provide the guarantee that the 'Data' is constructed using the 'Data's
-- 'Map' constructor.
-- Note that it assumes, like the 'fromBuiltinData' transformation, that the map
-- encoded in the 'Data' is well-formed, i.e. 'unsafeFromBuiltinData' does not perform
-- any deduplication of keys or of key-value pairs!
instance (UnsafeFromData k, UnsafeFromData v) => UnsafeFromData (Map k v) where
  -- The `~` here enables `BI.unsafeDataAsMap d` to be inlined, which reduces costs slightly.
  -- Without the `~`, the inliner would consider it not effect safe to inline.
  -- We can remove the `~` once we make the inliner smart enough to inline them.
  -- See https://github.com/IntersectMBO/plutus/pull/5371#discussion_r1297833685
  unsafeFromBuiltinData :: BuiltinData -> Map k v
unsafeFromBuiltinData BuiltinData
d = let ~BuiltinList (BuiltinPair BuiltinData BuiltinData)
es = BuiltinData -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
BI.unsafeDataAsMap BuiltinData
d in [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([(k, v)] -> Map k v) -> [(k, v)] -> Map k v
forall a b. (a -> b) -> a -> b
$ BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
mapFromBuiltin BuiltinList (BuiltinPair BuiltinData BuiltinData)
es
    where
      {-# INLINE mapFromBuiltin #-}
      mapFromBuiltin :: BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData) -> [(k, v)]
      mapFromBuiltin :: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
mapFromBuiltin = BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
go
        where
          go :: BI.BuiltinList (BI.BuiltinPair BI.BuiltinData BI.BuiltinData) -> [(k, v)]
          go :: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
go BuiltinList (BuiltinPair BuiltinData BuiltinData)
l =
            BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> (() -> [(k, v)]) -> (() -> [(k, v)]) -> () -> [(k, v)]
forall a b. BuiltinList a -> b -> b -> b
BI.chooseList
              BuiltinList (BuiltinPair BuiltinData BuiltinData)
l
              ([(k, v)] -> () -> [(k, v)]
forall a b. a -> b -> a
const [])
              ( \()
_ ->
                  let tup :: BuiltinPair BuiltinData BuiltinData
tup = BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> BuiltinPair BuiltinData BuiltinData
forall a. BuiltinList a -> a
BI.head BuiltinList (BuiltinPair BuiltinData BuiltinData)
l
                   in (BuiltinData -> k
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData (BuiltinData -> k) -> BuiltinData -> k
forall a b. (a -> b) -> a -> b
$ BuiltinPair BuiltinData BuiltinData -> BuiltinData
forall a b. BuiltinPair a b -> a
BI.fst BuiltinPair BuiltinData BuiltinData
tup, BuiltinData -> v
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData (BuiltinData -> v) -> BuiltinData -> v
forall a b. (a -> b) -> a -> b
$ BuiltinPair BuiltinData BuiltinData -> BuiltinData
forall a b. BuiltinPair a b -> b
BI.snd BuiltinPair BuiltinData BuiltinData
tup)
                        (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
go (BuiltinList (BuiltinPair BuiltinData BuiltinData)
-> BuiltinList (BuiltinPair BuiltinData BuiltinData)
forall a. BuiltinList a -> BuiltinList a
BI.tail BuiltinList (BuiltinPair BuiltinData BuiltinData)
l)
              )
              ()

instance Functor (Map k) where
  {-# INLINEABLE fmap #-}
  fmap :: forall a b. (a -> b) -> Map k a -> Map k b
fmap a -> b
f (Map [(k, a)]
mp) = [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map (((k, a) -> (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> (k, a) -> (k, b)
forall a b. (a -> b) -> (k, a) -> (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) [(k, a)]
mp)

instance Foldable (Map k) where
  {-# INLINEABLE foldr #-}
  foldr :: forall a b. (a -> b -> b) -> b -> Map k a -> b
foldr a -> b -> b
f b
z (Map [(k, a)]
mp) = ((k, a) -> b -> b) -> b -> [(k, a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (a -> b -> b
f (a -> b -> b) -> ((k, a) -> a) -> (k, a) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) b
z [(k, a)]
mp

instance Traversable (Map k) where
  {-# INLINEABLE traverse #-}
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map k a -> f (Map k b)
traverse a -> f b
f (Map [(k, a)]
mp) = [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map ([(k, b)] -> Map k b) -> f [(k, b)] -> f (Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((k, a) -> f (k, b)) -> [(k, a)] -> f [(k, b)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse ((a -> f b) -> (k, a) -> f (k, b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> (k, a) -> f (k, b)
traverse a -> f b
f) [(k, a)]
mp

-- This is the "better" instance for Maps that various people
-- have suggested, which merges conflicting entries with
-- the underlying semigroup for values.
instance (Eq k, Semigroup v) => Semigroup (Map k v) where
  <> :: Map k v -> Map k v -> Map k v
(<>) = (v -> v -> v) -> Map k v -> Map k v -> Map k v
forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith v -> v -> v
forall a. Semigroup a => a -> a -> a
(<>)

instance (Eq k, Semigroup v) => Monoid (Map k v) where
  mempty :: Map k v
mempty = Map k v
forall k v. Map k v
empty

instance (Pretty k, Pretty v) => Pretty (Map k v) where
  pretty :: forall ann. Map k v -> Doc ann
pretty (Map [(k, v)]
mp) = [(k, v)] -> Doc ann
forall ann. [(k, v)] -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty [(k, v)]
mp

{-# INLINEABLE unsafeFromList #-}
-- | Unsafely create a 'Map' from a list of pairs. This should _only_ be applied to lists which
-- have been checked to not contain duplicate keys, otherwise the resulting 'Map' will contain
-- conflicting entries (two entries sharing the same key).
-- As usual, the "keys" are considered to be the first element of the pair.
unsafeFromList :: [(k, v)] -> Map k v
unsafeFromList :: forall k v. [(k, v)] -> Map k v
unsafeFromList = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map

{-# INLINEABLE safeFromList #-}
-- | In case of duplicates, this function will keep only one entry (the one that precedes).
-- In other words, this function de-duplicates the input list.
safeFromList :: Eq k => [(k, v)] -> Map k v
safeFromList :: forall k v. Eq k => [(k, v)] -> Map k v
safeFromList = ((k, v) -> Map k v -> Map k v) -> Map k v -> [(k, v)] -> Map k v
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((k -> v -> Map k v -> Map k v) -> (k, v) -> Map k v -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v -> Map k v
forall k v. Eq k => k -> v -> Map k v -> Map k v
insert) Map k v
forall k v. Map k v
empty

{-# INLINEABLE toList #-}
toList :: Map k v -> [(k, v)]
toList :: forall k v. Map k v -> [(k, v)]
toList (Map [(k, v)]
l) = [(k, v)]
l

{-# INLINEABLE lookup #-}
-- | Find an entry in a 'Map'. If the 'Map' is not well-formed (it contains duplicate keys)
-- then this will return the value of the left-most pair in the underlying list of pairs.
lookup :: forall k v. (Eq k) => k -> Map k v -> Maybe v
lookup :: forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
c (Map [(k, v)]
xs) =
  let
    go :: [(k, v)] -> Maybe v
    go :: [(k, v)] -> Maybe v
go []              = Maybe v
forall a. Maybe a
Nothing
    go ((k
c', v
i) : [(k, v)]
xs') = if k
c' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
c then v -> Maybe v
forall a. a -> Maybe a
Just v
i else [(k, v)] -> Maybe v
go [(k, v)]
xs'
   in
    [(k, v)] -> Maybe v
go [(k, v)]
xs

{-# INLINEABLE member #-}
-- | Is the key a member of the map?
member :: forall k v. (Eq k) => k -> Map k v -> Bool
member :: forall k v. Eq k => k -> Map k v -> Bool
member k
k Map k v
m = Maybe v -> Bool
forall a. Maybe a -> Bool
isJust (k -> Map k v -> Maybe v
forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
k Map k v
m)

{-# INLINEABLE insert #-}
-- | If a key already exists in the map, its entry will be replaced with the new value.
insert :: forall k v. (Eq k) => k -> v -> Map k v -> Map k v
insert :: forall k v. Eq k => k -> v -> Map k v -> Map k v
insert k
k v
v (Map [(k, v)]
xs) = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([(k, v)] -> [(k, v)]
go [(k, v)]
xs)
  where
    go :: [(k, v)] -> [(k, v)]
go []                = [(k
k, v
v)]
    go ((k
k', v
v') : [(k, v)]
rest) = if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k' then (k
k, v
v) (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: [(k, v)]
rest else (k
k', v
v') (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: [(k, v)] -> [(k, v)]
go [(k, v)]
rest

{-# INLINEABLE delete #-}
-- | Delete an entry from the 'Map'. Assumes that the 'Map' is well-formed, i.e. if the
-- underlying list of pairs contains pairs with duplicate keys then only the left-most
-- pair will be removed.
delete :: forall k v. (Eq k) => k -> Map k v -> Map k v
delete :: forall k v. Eq k => k -> Map k v -> Map k v
delete k
key (Map [(k, v)]
ls) = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([(k, v)] -> [(k, v)]
go [(k, v)]
ls)
  where
    go :: [(k, v)] -> [(k, v)]
go [] = []
    go ((k
k, v
v) : [(k, v)]
rest)
      | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key = [(k, v)]
rest
      | Bool
otherwise = (k
k, v
v) (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: [(k, v)] -> [(k, v)]
go [(k, v)]
rest

{-# INLINEABLE keys #-}
-- | The keys of a 'Map'. Semantically, the resulting list is only a set if the 'Map'
-- didn't contain duplicate keys.
keys :: Map k v -> [k]
keys :: forall k v. Map k v -> [k]
keys (Map [(k, v)]
xs) = ((k, v) -> k) -> [(k, v)] -> [k]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
k, v
_ :: v) -> k
k) [(k, v)]
xs

-- | Combine two 'Map's. Keeps both values on key collisions.
-- Note that well-formedness is only preserved if the two input maps
-- are also well-formed.
-- Also, as an implementation detail, in the case that the right map contains
-- duplicate keys, and there exists a collision between the two maps,
-- then only the left-most value of the right map will be kept.
union :: forall k v r. (Eq k) => Map k v -> Map k r -> Map k (These v r)
union :: forall k v r. Eq k => Map k v -> Map k r -> Map k (These v r)
union (Map [(k, v)]
ls) (Map [(k, r)]
rs) =
  let
    f :: v -> Maybe r -> These v r
    f :: v -> Maybe r -> These v r
f v
a Maybe r
b' = case Maybe r
b' of
      Maybe r
Nothing -> v -> These v r
forall a b. a -> These a b
This v
a
      Just r
b  -> v -> r -> These v r
forall a b. a -> b -> These a b
These v
a r
b

    ls' :: [(k, These v r)]
    ls' :: [(k, These v r)]
ls' = ((k, v) -> (k, These v r)) -> [(k, v)] -> [(k, These v r)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
c, v
i) -> (k
c, v -> Maybe r -> These v r
f v
i (k -> Map k r -> Maybe r
forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
c ([(k, r)] -> Map k r
forall k v. [(k, v)] -> Map k v
Map [(k, r)]
rs)))) [(k, v)]
ls

    -- Keeps only those keys which don't appear in the left map.
    rs' :: [(k, r)]
    rs' :: [(k, r)]
rs' = ((k, r) -> Bool) -> [(k, r)] -> [(k, r)]
forall a. (a -> Bool) -> [a] -> [a]
P.filter (\(k
c, r
_) -> Bool -> Bool
not (((k, v) -> Bool) -> [(k, v)] -> Bool
forall a. (a -> Bool) -> [a] -> Bool
any (\(k
c', v
_) -> k
c' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
c) [(k, v)]
ls)) [(k, r)]
rs

    rs'' :: [(k, These v r)]
    rs'' :: [(k, These v r)]
rs'' = ((k, r) -> (k, These v r)) -> [(k, r)] -> [(k, These v r)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap ((r -> These v r) -> (k, r) -> (k, These v r)
forall a b. (a -> b) -> (k, a) -> (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap r -> These v r
forall a b. b -> These a b
That) [(k, r)]
rs'
   in
    [(k, These v r)] -> Map k (These v r)
forall k v. [(k, v)] -> Map k v
Map ([(k, These v r)]
ls' [(k, These v r)] -> [(k, These v r)] -> [(k, These v r)]
forall a. [a] -> [a] -> [a]
++ [(k, These v r)]
rs'')

{-# INLINEABLE unionWith #-}
-- | Combine two 'Map's with the given combination function.
-- Note that well-formedness of the resulting map depends on the two input maps
-- being well-formed.
-- Also, as an implementation detail, in the case that the right map contains
-- duplicate keys, and there exists a collision between the two maps,
-- then only the left-most value of the right map will be kept.
unionWith :: forall k a. (Eq k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith :: forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith a -> a -> a
merge (Map [(k, a)]
ls) (Map [(k, a)]
rs) =
  let
    f :: a -> Maybe a -> a
    f :: a -> Maybe a -> a
f a
a Maybe a
b' = case Maybe a
b' of
      Maybe a
Nothing -> a
a
      Just a
b  -> a -> a -> a
merge a
a a
b

    ls' :: [(k, a)]
    ls' :: [(k, a)]
ls' = ((k, a) -> (k, a)) -> [(k, a)] -> [(k, a)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
c, a
i) -> (k
c, a -> Maybe a -> a
f a
i (k -> Map k a -> Maybe a
forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
c ([(k, a)] -> Map k a
forall k v. [(k, v)] -> Map k v
Map [(k, a)]
rs)))) [(k, a)]
ls

    rs' :: [(k, a)]
    rs' :: [(k, a)]
rs' = ((k, a) -> Bool) -> [(k, a)] -> [(k, a)]
forall a. (a -> Bool) -> [a] -> [a]
P.filter (\(k
c, a
_) -> Bool -> Bool
not (((k, a) -> Bool) -> [(k, a)] -> Bool
forall a. (a -> Bool) -> [a] -> Bool
any (\(k
c', a
_) -> k
c' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
c) [(k, a)]
ls)) [(k, a)]
rs
   in
    [(k, a)] -> Map k a
forall k v. [(k, v)] -> Map k v
Map ([(k, a)]
ls' [(k, a)] -> [(k, a)] -> [(k, a)]
forall a. [a] -> [a] -> [a]
++ [(k, a)]
rs')

{-# INLINEABLE mapThese #-}
-- | A version of 'Data.Map.Lazy.mapEither' that works with 'These'.
mapThese :: (v -> These a b) -> Map k v -> (Map k a, Map k b)
mapThese :: forall v a b k. (v -> These a b) -> Map k v -> (Map k a, Map k b)
mapThese v -> These a b
f Map k v
mps = ([(k, a)] -> Map k a
forall k v. [(k, v)] -> Map k v
Map [(k, a)]
mpl, [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map [(k, b)]
mpr)
  where
    ([(k, a)]
mpl, [(k, b)]
mpr) = ((k, These a b) -> ([(k, a)], [(k, b)]) -> ([(k, a)], [(k, b)]))
-> ([(k, a)], [(k, b)]) -> [(k, These a b)] -> ([(k, a)], [(k, b)])
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
P.foldr (k, These a b) -> ([(k, a)], [(k, b)]) -> ([(k, a)], [(k, b)])
forall {a} {b} {b}.
(a, These b b) -> ([(a, b)], [(a, b)]) -> ([(a, b)], [(a, b)])
f' ([], []) [(k, These a b)]
mps'
    Map [(k, These a b)]
mps' = (v -> These a b) -> Map k v -> Map k (These a b)
forall a b. (a -> b) -> Map k a -> Map k b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap v -> These a b
f Map k v
mps
    f' :: (a, These b b) -> ([(a, b)], [(a, b)]) -> ([(a, b)], [(a, b)])
f' (a
k, These b b
v) ([(a, b)]
as, [(a, b)]
bs) = case These b b
v of
      This b
a    -> ((a
k, b
a) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
as, [(a, b)]
bs)
      That b
b    -> ([(a, b)]
as, (a
k, b
b) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
bs)
      These b
a b
b -> ((a
k, b
a) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
as, (a
k, b
b) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
bs)

-- | A singleton map.
singleton :: k -> v -> Map k v
singleton :: forall k v. k -> v -> Map k v
singleton k
c v
i = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map [(k
c, v
i)]

{-# INLINEABLE empty #-}

-- | An empty 'Map'.
empty :: Map k v
empty :: forall k v. Map k v
empty = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([] :: [(k, v)])

{-# INLINEABLE null #-}

-- | Is the map empty?
null :: Map k v -> Bool
null :: forall k v. Map k v -> Bool
null = [(k, v)] -> Bool
forall a. [a] -> Bool
P.null ([(k, v)] -> Bool) -> (Map k v -> [(k, v)]) -> Map k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> [(k, v)]
forall k v. Map k v -> [(k, v)]
unMap

{-# INLINEABLE filter #-}

-- | Filter all values that satisfy the predicate.
filter :: (v -> Bool) -> Map k v -> Map k v
filter :: forall v k. (v -> Bool) -> Map k v -> Map k v
filter v -> Bool
f (Map [(k, v)]
m) = [(k, v)] -> Map k v
forall k v. [(k, v)] -> Map k v
Map ([(k, v)] -> Map k v) -> [(k, v)] -> Map k v
forall a b. (a -> b) -> a -> b
$ ((k, v) -> Bool) -> [(k, v)] -> [(k, v)]
forall a. (a -> Bool) -> [a] -> [a]
P.filter (v -> Bool
f (v -> Bool) -> ((k, v) -> v) -> (k, v) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, v) -> v
forall a b. (a, b) -> b
snd) [(k, v)]
m

{-# INLINEABLE elems #-}

-- | Return all elements of the map.
elems :: Map k v -> [v]
elems :: forall k v. Map k v -> [v]
elems (Map [(k, v)]
xs) = ((k, v) -> v) -> [(k, v)] -> [v]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
_ :: k, v
v) -> v
v) [(k, v)]
xs

{-# INLINEABLE mapWithKey #-}

-- | Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey :: forall k a b. (k -> a -> b) -> Map k a -> Map k b
mapWithKey k -> a -> b
f (Map [(k, a)]
xs) = [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map ([(k, b)] -> Map k b) -> [(k, b)] -> Map k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(k
k, a
v) -> (k
k, k -> a -> b
f k
k a
v)) [(k, a)]
xs

{-# INLINEABLE mapMaybe #-}

-- | Map keys\/values and collect the 'Just' results.
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
mapMaybe :: forall a b k. (a -> Maybe b) -> Map k a -> Map k b
mapMaybe a -> Maybe b
f (Map [(k, a)]
xs) = [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map ([(k, b)] -> Map k b) -> [(k, b)] -> Map k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Maybe (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> Maybe b) -> [a] -> [b]
P.mapMaybe (\(k
k, a
v) -> (k
k,) (b -> (k, b)) -> Maybe b -> Maybe (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe b
f a
v) [(k, a)]
xs

{-# INLINEABLE mapMaybeWithKey #-}

-- | Map keys\/values and collect the 'Just' results.
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
mapMaybeWithKey :: forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
mapMaybeWithKey k -> a -> Maybe b
f (Map [(k, a)]
xs) = [(k, b)] -> Map k b
forall k v. [(k, v)] -> Map k v
Map ([(k, b)] -> Map k b) -> [(k, b)] -> Map k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Maybe (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> Maybe b) -> [a] -> [b]
P.mapMaybe (\(k
k, a
v) -> (k
k,) (b -> (k, b)) -> Maybe b -> Maybe (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> Maybe b
f k
k a
v) [(k, a)]
xs

{-# INLINEABLE all #-}

-- | Determines whether all elements in the map satisfy the predicate.
all :: (a -> Bool) -> Map k a -> Bool
all :: forall a k. (a -> Bool) -> Map k a -> Bool
all a -> Bool
f (Map [(k, a)]
m) = [(k, a)] -> Bool
go [(k, a)]
m
  where
    go :: [(k, a)] -> Bool
go = \case
      []          -> Bool
True
      (k
_, a
x) : [(k, a)]
xs -> if a -> Bool
f a
x then [(k, a)] -> Bool
go [(k, a)]
xs else Bool
False

makeLift ''Map