-- editorconfig-checker-disable-file
{-# LANGUAGE DeriveAnyClass        #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE DeriveGeneric         #-}
{-# LANGUAGE DerivingStrategies    #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE LambdaCase            #-}
{-# LANGUAGE MonoLocalBinds        #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TemplateHaskell       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE UndecidableInstances  #-}
{-# OPTIONS_GHC -Wno-name-shadowing #-}
-- Prevent unboxing, which the plugin can't deal with
{-# OPTIONS_GHC -fno-specialise #-}
{-# OPTIONS_GHC -fno-omit-interface-pragmas #-}

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

import Control.DeepSeq (NFData)
import Data.Data
import GHC.Generics (Generic)
import PlutusTx.Builtins qualified as P
import PlutusTx.Builtins.Internal qualified as BI
import PlutusTx.IsData
import PlutusTx.Lift (makeLift)
import PlutusTx.Prelude hiding (filter, mapMaybe, null, toList)
import PlutusTx.Prelude qualified as P
import PlutusTx.These
import Prelude qualified as Haskell
import Prettyprinter (Pretty (..))

{- HLINT ignore "Use newtype instead of data" -}

-- | A 'Map' of key-value pairs.
newtype Map k v = Map { forall k v. Map k v -> [(k, v)]
unMap :: [(k, v)] }
    deriving stock (forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (Map k v) x -> Map k v
forall k v x. Map k v -> Rep (Map k v) x
$cto :: forall k v x. Rep (Map k v) x -> Map k v
$cfrom :: forall k v x. Map k v -> Rep (Map k v) x
Generic, Map k v -> Map k v -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
/= :: Map k v -> Map k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
== :: Map k v -> Map k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
Haskell.Eq, Int -> Map k v -> ShowS
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
showList :: [Map k v] -> ShowS
$cshowList :: forall k v. (Show k, Show v) => [Map k v] -> ShowS
show :: Map k v -> String
$cshow :: forall k v. (Show k, Show v) => Map k v -> String
showsPrec :: Int -> Map k v -> ShowS
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> Map k v -> ShowS
Haskell.Show, Map k v -> DataType
Map k v -> Constr
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 {k} {v}. (Data k, Data v) => Typeable (Map k v)
forall k v. (Data k, Data v) => Map k v -> DataType
forall k v. (Data k, Data v) => Map k v -> Constr
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 (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 e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k v))
gmapMo :: 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)
gmapMp :: forall (m :: * -> *).
MonadPlus 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)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Map k v -> m (Map k v)
$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)
gmapQi :: forall u. Int -> (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
gmapQ :: forall u. (forall d. Data d => d -> u) -> Map k v -> [u]
$cgmapQ :: forall k v u.
(Data k, Data v) =>
(forall d. Data d => d -> u) -> Map k v -> [u]
gmapQr :: 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
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
$cgmapQl :: forall k v r r'.
(Data k, Data v) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Map k v -> r
gmapT :: (forall b. Data b => b -> b) -> Map k v -> Map k v
$cgmapT :: forall k v.
(Data k, Data v) =>
(forall b. Data b => b -> b) -> Map k v -> 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))
$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))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
$cdataCast1 :: forall k v (t :: * -> *) (c :: * -> *).
(Data k, Data v, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Map k v))
dataTypeOf :: Map k v -> DataType
$cdataTypeOf :: forall k v. (Data k, Data v) => Map k v -> DataType
toConstr :: Map k v -> Constr
$ctoConstr :: forall k v. (Data k, Data v) => Map k v -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Map k v)
$cgunfold :: forall k v (c :: * -> *).
(Data k, Data v) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> 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)
$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)
Data)
    deriving newtype (Map k v -> Map k v -> Bool
forall a. (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
== :: Map k v -> Map k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
Eq, Map k v -> Map k v -> Bool
Map k v -> Map k v -> Ordering
Map k v -> Map k v -> Map k v
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {k} {v}. (Ord k, Ord v) => Eq (Map k v)
forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Bool
forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Ordering
forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Map k v
min :: Map k v -> Map k v -> Map k v
$cmin :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Map k v
max :: Map k v -> Map k v -> Map k v
$cmax :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Map k v
>= :: Map k v -> Map k v -> Bool
$c>= :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Bool
> :: Map k v -> Map k v -> Bool
$c> :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Bool
<= :: Map k v -> Map k v -> Bool
$c<= :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Bool
< :: Map k v -> Map k v -> Bool
$c< :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Bool
compare :: Map k v -> Map k v -> Ordering
$ccompare :: forall k v. (Ord k, Ord v) => Map k v -> Map k v -> Ordering
Ord, Map k v -> ()
forall a. (a -> ()) -> NFData a
forall k v. (NFData k, NFData v) => Map k v -> ()
rnf :: Map k v -> ()
$crnf :: forall k v. (NFData k, NFData v) => Map k v -> ()
NFData)

-- 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) = forall a. a -> BuiltinList a -> BuiltinList a
BI.mkCons (BuiltinData -> BuiltinData -> BuiltinPair BuiltinData BuiltinData
BI.mkPairData (forall a. ToData a => a -> BuiltinData
toBuiltinData k
k) (forall a. ToData a => a -> BuiltinData
toBuiltinData v
v)) ([(k, v)] -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
go [(k, v)]
xs)

instance (FromData k, FromData v) => FromData (Map k v) where
    fromBuiltinData :: BuiltinData -> Maybe (Map k v)
fromBuiltinData BuiltinData
d = 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
_ -> forall a. Maybe a
Nothing)
        (\BuiltinList (BuiltinPair BuiltinData BuiltinData)
es -> forall k v. [(k, v)] -> Map k v
Map 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)
        (forall a b. a -> b -> a
const forall a. Maybe a
Nothing)
        (forall a b. a -> b -> a
const forall a. Maybe a
Nothing)
        (forall a b. a -> b -> a
const 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 = forall a b. BuiltinList a -> b -> b -> b
BI.chooseList BuiltinList (BuiltinPair BuiltinData BuiltinData)
l (forall a b. a -> b -> a
const (forall (f :: * -> *) a. Applicative f => a -> f a
pure [])) (\()
_ -> let tup :: BuiltinPair BuiltinData BuiltinData
tup = forall a. BuiltinList a -> a
BI.head BuiltinList (BuiltinPair BuiltinData BuiltinData)
l in forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (:) (forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (,) (forall a. FromData a => BuiltinData -> Maybe a
fromBuiltinData forall a b. (a -> b) -> a -> b
$ forall a b. BuiltinPair a b -> a
BI.fst BuiltinPair BuiltinData BuiltinData
tup) (forall a. FromData a => BuiltinData -> Maybe a
fromBuiltinData forall a b. (a -> b) -> a -> b
$ forall a b. BuiltinPair a b -> b
BI.snd BuiltinPair BuiltinData BuiltinData
tup)) (BuiltinList (BuiltinPair BuiltinData BuiltinData) -> Maybe [(k, v)]
go (forall a. BuiltinList a -> BuiltinList a
BI.tail BuiltinList (BuiltinPair BuiltinData BuiltinData)
l))) ()

instance (UnsafeFromData k, UnsafeFromData v) => UnsafeFromData (Map k v) where
    unsafeFromBuiltinData :: BuiltinData -> Map k v
unsafeFromBuiltinData BuiltinData
d = let es :: BuiltinList (BuiltinPair BuiltinData BuiltinData)
es = BuiltinData -> BuiltinList (BuiltinPair BuiltinData BuiltinData)
BI.unsafeDataAsMap BuiltinData
d in forall k v. [(k, v)] -> Map k v
Map 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 = forall a b. BuiltinList a -> b -> b -> b
BI.chooseList BuiltinList (BuiltinPair BuiltinData BuiltinData)
l (forall a b. a -> b -> a
const []) (\()
_ -> let tup :: BuiltinPair BuiltinData BuiltinData
tup = forall a. BuiltinList a -> a
BI.head BuiltinList (BuiltinPair BuiltinData BuiltinData)
l in (forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData forall a b. (a -> b) -> a -> b
$ forall a b. BuiltinPair a b -> a
BI.fst BuiltinPair BuiltinData BuiltinData
tup, forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData forall a b. (a -> b) -> a -> b
$ forall a b. BuiltinPair a b -> b
BI.snd BuiltinPair BuiltinData BuiltinData
tup) forall a. a -> [a] -> [a]
: BuiltinList (BuiltinPair BuiltinData BuiltinData) -> [(k, v)]
go (forall a. BuiltinList a -> BuiltinList a
BI.tail BuiltinList (BuiltinPair BuiltinData BuiltinData)
l)) ()

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

instance Foldable (Map k) where
    {-# INLINABLE foldMap #-}
    foldMap :: forall m a. Monoid m => (a -> m) -> Map k a -> m
foldMap a -> m
f (Map [(k, a)]
mp) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f) [(k, a)]
mp

instance Traversable (Map k) where
    {-# INLINABLE 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) = forall k v. [(k, v)] -> Map k v
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t 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
(<>) = forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith forall a. Semigroup a => a -> a -> a
(<>)

instance (Eq k, Semigroup v) => Monoid (Map k v) where
    mempty :: Map k v
mempty = 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) = forall a ann. Pretty a => a -> Doc ann
pretty [(k, v)]
mp

{-# INLINABLE fromList #-}
fromList :: [(k, v)] -> Map k v
fromList :: forall k v. [(k, v)] -> Map k v
fromList = forall k v. [(k, v)] -> Map k v
Map

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

{-# INLINABLE lookup #-}
-- | Find an entry in a 'Map'.
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 []            = forall a. Maybe a
Nothing
        go ((k
c', v
i):[(k, v)]
xs') = if k
c' forall a. Eq a => a -> a -> Bool
== k
c then 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


{-# INLINABLE 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 = forall a. Maybe a -> Bool
isJust (forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
k Map k v
m)

{-# INLINABLE insert #-}
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
m = forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith (\v
_ v
b -> v
b) Map k v
m (forall k v. [(k, v)] -> Map k v
fromList [(k
k, v
v)])

{-# INLINABLE delete #-}
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) = 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 forall a. Eq a => a -> a -> Bool
== k
key = [(k, v)]
rest
                       | Bool
otherwise = (k
k, v
v) forall a. a -> [a] -> [a]
: [(k, v)] -> [(k, v)]
go [(k, v)]
rest

{-# INLINABLE keys #-}
-- | The keys of a 'Map'.
keys :: Map k v -> [k]
keys :: forall k v. Map k v -> [k]
keys (Map [(k, v)]
xs) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
k, v
_ :: v) -> k
k) [(k, v)]
xs

{-# INLINABLE union #-}
-- | Combine two 'Map's.
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 -> forall a b. a -> These a b
This v
a
            Just r
b  -> forall a b. a -> b -> These a b
These v
a r
b

        ls' :: [(k, These v r)]
        ls' :: [(k, These v r)]
ls' = 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 (forall k v. Eq k => k -> Map k v -> Maybe v
lookup k
c (forall k v. [(k, v)] -> Map k v
Map [(k, r)]
rs)))) [(k, v)]
ls

        rs' :: [(k, r)]
        rs' :: [(k, r)]
rs' = forall a. (a -> Bool) -> [a] -> [a]
P.filter (\(k
c, r
_) -> Bool -> Bool
not (forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\(k
c', v
_) -> k
c' 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'' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap forall a b. b -> These a b
That) [(k, r)]
rs'

    in forall k v. [(k, v)] -> Map k v
Map ([(k, These v r)]
ls' forall a. [a] -> [a] -> [a]
++ [(k, These v r)]
rs'')

{-# INLINABLE unionWith #-}
-- | Combine two 'Map's with the given combination function.
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 = forall a c b.
(a -> c) -> (b -> c) -> (a -> b -> c) -> These a b -> c
these forall a. a -> a
id forall a. a -> a
id a -> a -> a
merge forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall k v r. Eq k => Map k v -> Map k r -> Map k (These v r)
union Map k a
ls Map k a
rs

{-# INLINABLE 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 = (forall k v. [(k, v)] -> Map k v
Map [(k, a)]
mpl, forall k v. [(k, v)] -> Map k v
Map [(k, b)]
mpr)  where
    ([(k, a)]
mpl, [(k, b)]
mpr) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
P.foldr 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'  = 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)forall a. a -> [a] -> [a]
:[(a, b)]
as, [(a, b)]
bs)
        That b
b    -> ([(a, b)]
as, (a
k, b
b)forall a. a -> [a] -> [a]
:[(a, b)]
bs)
        These b
a b
b -> ((a
k, b
a)forall a. a -> [a] -> [a]
:[(a, b)]
as, (a
k, b
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 = forall k v. [(k, v)] -> Map k v
Map [(k
c, v
i)]

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

{-# INLINABLE null #-}
-- | Is the map empty?
null :: Map k v -> Bool
null :: forall k v. Map k v -> Bool
null = forall (t :: * -> *) a. Foldable t => t a -> Bool
P.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Map k v -> [(k, v)]
unMap

{-# INLINABLE 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) = forall k v. [(k, v)] -> Map k v
Map forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter (v -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd) [(k, v)]
m

{-# INLINABLE elems #-}
-- | Return all elements of the map in the ascending order of their keys.
elems :: Map k v -> [v]
elems :: forall k v. Map k v -> [v]
elems (Map [(k, v)]
xs) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
P.fmap (\(k
_ :: k, v
v) -> v
v) [(k, v)]
xs

{-# INLINABLE 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) = forall k v. [(k, v)] -> Map k v
Map 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

{-# INLINABLE 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) = forall k v. [(k, v)] -> Map k v
Map forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> [a] -> [b]
P.mapMaybe (\(k
k, a
v) -> (k
k, ) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe b
f a
v) [(k, a)]
xs

{-# INLINABLE 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) = forall k v. [(k, v)] -> Map k v
Map forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> [a] -> [b]
P.mapMaybe (\(k
k, a
v) -> (k
k, ) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> Maybe b
f k
k a
v) [(k, a)]
xs

makeLift ''Map