{-# LANGUAGE DataKinds             #-}
{-# LANGUAGE DeriveAnyClass        #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE DeriveGeneric         #-}
{-# LANGUAGE DeriveLift            #-}
{-# LANGUAGE DerivingStrategies    #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE LambdaCase            #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TemplateHaskell       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeApplications      #-}
{-# LANGUAGE TypeFamilies          #-}
{-# 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.Kind (Type)
import Data.Map.Strict qualified as HMap
import GHC.Generics (Generic)
import Language.Haskell.TH.Syntax as TH (Lift)
import PlutusTx.Blueprint.Class (HasBlueprintSchema (..))
import PlutusTx.Blueprint.Definition.Id (definitionIdFromTypeK)
import PlutusTx.Blueprint.Definition.Unroll (HasBlueprintDefinition (..))
import PlutusTx.Blueprint.Schema (MapSchema (..), Schema (..))
import PlutusTx.Blueprint.Schema.Annotation (emptySchemaInfo)
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 []            = BuiltinList (BuiltinPair BuiltinData BuiltinData)
forall arep. MkNil arep => BuiltinList arep
P.mkNil
          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
  (HasBlueprintDefinition k, HasBlueprintDefinition v)
  => HasBlueprintDefinition (Map k v)
  where
  type Unroll (Map k v) = [Map k v, k, v]
  definitionId :: DefinitionId
definitionId =
    forall k (t :: k). Typeable t => DefinitionId
definitionIdFromTypeK @(Type -> Type -> Type) @Map
      DefinitionId -> DefinitionId -> DefinitionId
forall a. Semigroup a => a -> a -> a
Haskell.<> forall t. HasBlueprintDefinition t => DefinitionId
definitionId @k
      DefinitionId -> DefinitionId -> DefinitionId
forall a. Semigroup a => a -> a -> a
Haskell.<> forall t. HasBlueprintDefinition t => DefinitionId
definitionId @v

instance
  ( HasBlueprintSchema k referencedTypes
  , HasBlueprintSchema v referencedTypes
  ) =>
  HasBlueprintSchema (Map k v) referencedTypes where
  schema :: Schema referencedTypes
schema = SchemaInfo -> MapSchema referencedTypes -> Schema referencedTypes
forall (referencedTypes :: [*]).
SchemaInfo -> MapSchema referencedTypes -> Schema referencedTypes
SchemaMap SchemaInfo
emptySchemaInfo MkMapSchema
    { $sel:keySchema:MkMapSchema :: Schema referencedTypes
keySchema = forall t (referencedTypes :: [*]).
HasBlueprintSchema t referencedTypes =>
Schema referencedTypes
schema @k
    , $sel:valueSchema:MkMapSchema :: Schema referencedTypes
valueSchema = forall t (referencedTypes :: [*]).
HasBlueprintSchema t referencedTypes =>
Schema referencedTypes
schema @v
    , $sel:minItems:MkMapSchema :: Maybe Natural
minItems = Maybe Natural
forall a. Maybe a
Nothing
    , $sel:maxItems:MkMapSchema :: Maybe Natural
maxItems = Maybe Natural
forall a. Maybe a
Nothing
    }


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

----------------------------------------------------------------------------------------------------
-- TH Splices --------------------------------------------------------------------------------------

$(makeLift ''Map)