{-# OPTIONS_GHC -fno-warn-redundant-constraints #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}
{-# OPTIONS_HADDOCK not-home #-}
{- HLINT ignore "Avoid lambda" -}
{- HLINT ignore "Avoid lambda using `infix`" -}
{- HLINT ignore "Redundant bracket" -}

-- |
-- Copyright: © 2022–2025 Jonathan Knowles
-- License: Apache-2.0
--
-- Provides /internal/ operations for the 'MonoidMap' type.
--
module Data.MonoidMap.Internal
    (
    -- * Types
      MonoidMap (..)
    , NonNull (..)

    -- * General operations

    -- ** Construction
    , empty
    , fromList
    , fromListWith
    , fromMap
    , fromMapWith
    , fromSet
    , singleton

    -- ** Deconstruction
    , toList
    , toMap

    -- ** Lookup
    , get

    -- ** Modification
    , set
    , adjust
    , nullify

    -- ** Membership
    , null
    , nullKey
    , nonNull
    , nonNullCount
    , nonNullKey
    , nonNullKeys

    -- ** Slicing
    , take
    , drop
    , splitAt

    -- ** Filtering
    , filter
    , filterKeys
    , filterWithKey

    -- ** Partitioning
    , partition
    , partitionKeys
    , partitionWithKey

    -- ** Mapping
    , map
    , mapKeys
    , mapKeysWith
    , mapWithKey

    -- ** Folding
    , foldl
    , foldl'
    , foldr
    , foldr'
    , foldlWithKey
    , foldlWithKey'
    , foldrWithKey
    , foldrWithKey'
    , foldMapWithKey
    , foldMapWithKey'

    -- ** Traversal
    , traverse
    , traverseWithKey
    , mapAccumL
    , mapAccumLWithKey
    , mapAccumR
    , mapAccumRWithKey

    -- * Monoidal operations

    -- ** Association
    , append

    -- ** Subtraction
    , minus
    , minusMaybe
    , monus

    -- ** Inversion
    , invert

    -- ** Exponentiation
    , power

    -- ** Comparison
    , isSubmapOf
    , isSubmapOfBy
    , disjoint
    , disjointBy

    -- ** Intersection
    , intersection
    , intersectionWith
    , intersectionWithA

    -- ** Union
    , union
    , unionWith
    , unionWithA

    -- ** Prefixes
    , isPrefixOf
    , stripPrefix
    , commonPrefix
    , stripCommonPrefix

    -- ** Suffixes
    , isSuffixOf
    , stripSuffix
    , commonSuffix
    , stripCommonSuffix

    -- ** Overlap
    , overlap
    , stripPrefixOverlap
    , stripSuffixOverlap
    , stripOverlap
    )
    where

import Prelude hiding
    ( drop
    , filter
    , foldl
    , foldl'
    , foldr
    , lookup
    , map
    , null
    , splitAt
    , subtract
    , take
    , traverse
    )

import Control.Applicative
    ( Applicative (..) )
import Control.DeepSeq
    ( NFData )
import Data.Bifoldable
    ( Bifoldable )
import Data.Coerce
    ( coerce )
import Data.Function
    ( (&) )
import Data.Functor.Classes
    ( Eq1, Eq2, Show1, Show2 )
import Data.Functor.Identity
    ( Identity (..) )
import Data.Group
    ( Abelian, Group )
import Data.Map.Strict
    ( Map, lookup )
import Data.Maybe
    ( fromMaybe, isJust )
import Data.Monoid.GCD
    ( DistributiveGCDMonoid
    , GCDMonoid
    , LeftDistributiveGCDMonoid
    , LeftGCDMonoid
    , OverlappingGCDMonoid
    , RightDistributiveGCDMonoid
    , RightGCDMonoid
    )
import Data.Monoid.LCM
    ( DistributiveLCMMonoid, LCMMonoid )
import Data.Monoid.Monus
    ( Monus (..) )
import Data.Monoid.Null
    ( MonoidNull, PositiveMonoid )
import Data.Semigroup
    ( stimes )
import Data.Semigroup.Cancellative
    ( Cancellative
    , Commutative
    , LeftCancellative
    , LeftReductive
    , Reductive (..)
    , RightCancellative
    , RightReductive
    )
import Data.Set
    ( Set )
import GHC.Exts
    ( IsList (Item) )
import NoThunks.Class
    ( NoThunks )
import Text.Read
    ( Read (..) )

import qualified Data.Bifunctor as B
import qualified Data.Foldable as F
import qualified Data.List as L
import qualified Data.List.NonEmpty as NE
import qualified Data.Map.Merge.Strict as Map
import qualified Data.Map.Strict as Map
import qualified Data.Set as Set
import qualified GHC.Exts as GHC
import qualified Data.Traversable as Traversable

import qualified Data.Group as C
import qualified Data.Monoid.GCD as C
import qualified Data.Monoid.LCM as C
import qualified Data.Monoid.Null as C
import qualified Data.Semigroup.Cancellative as C

--------------------------------------------------------------------------------
-- Type
--------------------------------------------------------------------------------

newtype MonoidMap k v = MonoidMap (Map k (NonNull v))
    deriving (MonoidMap k v -> MonoidMap k v -> Bool
(MonoidMap k v -> MonoidMap k v -> Bool)
-> (MonoidMap k v -> MonoidMap k v -> Bool) -> Eq (MonoidMap k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => MonoidMap k v -> MonoidMap k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => MonoidMap k v -> MonoidMap k v -> Bool
== :: MonoidMap k v -> MonoidMap k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => MonoidMap k v -> MonoidMap k v -> Bool
/= :: MonoidMap k v -> MonoidMap k v -> Bool
Eq, Int -> MonoidMap k v -> ShowS
[MonoidMap k v] -> ShowS
MonoidMap k v -> String
(Int -> MonoidMap k v -> ShowS)
-> (MonoidMap k v -> String)
-> ([MonoidMap k v] -> ShowS)
-> Show (MonoidMap k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> MonoidMap k v -> ShowS
forall k v. (Show k, Show v) => [MonoidMap k v] -> ShowS
forall k v. (Show k, Show v) => MonoidMap k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> MonoidMap k v -> ShowS
showsPrec :: Int -> MonoidMap k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => MonoidMap k v -> String
show :: MonoidMap k v -> String
$cshowList :: forall k v. (Show k, Show v) => [MonoidMap k v] -> ShowS
showList :: [MonoidMap k v] -> ShowS
Show, MonoidMap k v -> ()
(MonoidMap k v -> ()) -> NFData (MonoidMap k v)
forall a. (a -> ()) -> NFData a
forall k v. (NFData k, NFData v) => MonoidMap k v -> ()
$crnf :: forall k v. (NFData k, NFData v) => MonoidMap k v -> ()
rnf :: MonoidMap k v -> ()
NFData, Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
Proxy (MonoidMap k v) -> String
(Context -> MonoidMap k v -> IO (Maybe ThunkInfo))
-> (Context -> MonoidMap k v -> IO (Maybe ThunkInfo))
-> (Proxy (MonoidMap k v) -> String)
-> NoThunks (MonoidMap k v)
forall a.
(Context -> a -> IO (Maybe ThunkInfo))
-> (Context -> a -> IO (Maybe ThunkInfo))
-> (Proxy a -> String)
-> NoThunks a
forall k v.
(NoThunks k, NoThunks v) =>
Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
forall k v.
(NoThunks k, NoThunks v) =>
Proxy (MonoidMap k v) -> String
$cnoThunks :: forall k v.
(NoThunks k, NoThunks v) =>
Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
noThunks :: Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
$cwNoThunks :: forall k v.
(NoThunks k, NoThunks v) =>
Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
wNoThunks :: Context -> MonoidMap k v -> IO (Maybe ThunkInfo)
$cshowTypeOf :: forall k v.
(NoThunks k, NoThunks v) =>
Proxy (MonoidMap k v) -> String
showTypeOf :: Proxy (MonoidMap k v) -> String
NoThunks)
        via Map k v
    deriving ((forall a. Eq a => Eq (MonoidMap k a)) =>
(forall a b.
 (a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool)
-> Eq1 (MonoidMap k)
forall a. Eq a => Eq (MonoidMap k a)
forall k a. (Eq k, Eq a) => Eq (MonoidMap k a)
forall k a b.
Eq k =>
(a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool
forall a b.
(a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool
forall (f :: * -> *).
(forall a. Eq a => Eq (f a)) =>
(forall a b. (a -> b -> Bool) -> f a -> f b -> Bool) -> Eq1 f
$cliftEq :: forall k a b.
Eq k =>
(a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool
liftEq :: forall a b.
(a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool
Eq1, (forall a. Show a => Show (MonoidMap k a)) =>
(forall a.
 (Int -> a -> ShowS)
 -> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS)
-> (forall a.
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS)
-> Show1 (MonoidMap k)
forall a. Show a => Show (MonoidMap k a)
forall k a. (Show k, Show a) => Show (MonoidMap k a)
forall k a.
Show k =>
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS
forall k a.
Show k =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS
forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS
forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS
forall (f :: * -> *).
(forall a. Show a => Show (f a)) =>
(forall a.
 (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS)
-> (forall a.
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS)
-> Show1 f
$cliftShowsPrec :: forall k a.
Show k =>
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS
liftShowsPrec :: forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS
$cliftShowList :: forall k a.
Show k =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS
liftShowList :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS
Show1, (forall m. Monoid m => MonoidMap k m -> m)
-> (forall m a. Monoid m => (a -> m) -> MonoidMap k a -> m)
-> (forall m a. Monoid m => (a -> m) -> MonoidMap k a -> m)
-> (forall a b. (a -> b -> b) -> b -> MonoidMap k a -> b)
-> (forall a b. (a -> b -> b) -> b -> MonoidMap k a -> b)
-> (forall b a. (b -> a -> b) -> b -> MonoidMap k a -> b)
-> (forall b a. (b -> a -> b) -> b -> MonoidMap k a -> b)
-> (forall a. (a -> a -> a) -> MonoidMap k a -> a)
-> (forall a. (a -> a -> a) -> MonoidMap k a -> a)
-> (forall a. MonoidMap k a -> [a])
-> (forall a. MonoidMap k a -> Bool)
-> (forall a. MonoidMap k a -> Int)
-> (forall a. Eq a => a -> MonoidMap k a -> Bool)
-> (forall a. Ord a => MonoidMap k a -> a)
-> (forall a. Ord a => MonoidMap k a -> a)
-> (forall a. Num a => MonoidMap k a -> a)
-> (forall a. Num a => MonoidMap k a -> a)
-> Foldable (MonoidMap k)
forall a. Eq a => a -> MonoidMap k a -> Bool
forall a. Num a => MonoidMap k a -> a
forall a. Ord a => MonoidMap k a -> a
forall m. Monoid m => MonoidMap k m -> m
forall a. MonoidMap k a -> Bool
forall a. MonoidMap k a -> Int
forall a. MonoidMap k a -> [a]
forall a. (a -> a -> a) -> MonoidMap k a -> a
forall k a. Eq a => a -> MonoidMap k a -> Bool
forall k a. Num a => MonoidMap k a -> a
forall k a. Ord a => MonoidMap k a -> a
forall m a. Monoid m => (a -> m) -> MonoidMap k a -> m
forall k m. Monoid m => MonoidMap k m -> m
forall k a. MonoidMap k a -> Bool
forall k a. MonoidMap k a -> Int
forall k a. MonoidMap k a -> [a]
forall b a. (b -> a -> b) -> b -> MonoidMap k a -> b
forall a b. (a -> b -> b) -> b -> MonoidMap k a -> b
forall k a. (a -> a -> a) -> MonoidMap k a -> a
forall k m a. Monoid m => (a -> m) -> MonoidMap k a -> m
forall k b a. (b -> a -> b) -> b -> MonoidMap k a -> b
forall k a b. (a -> b -> b) -> b -> MonoidMap k a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall k m. Monoid m => MonoidMap k m -> m
fold :: forall m. Monoid m => MonoidMap k m -> m
$cfoldMap :: forall k m a. Monoid m => (a -> m) -> MonoidMap k a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> MonoidMap k a -> m
$cfoldMap' :: forall k m a. Monoid m => (a -> m) -> MonoidMap k a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> MonoidMap k a -> m
$cfoldr :: forall k a b. (a -> b -> b) -> b -> MonoidMap k a -> b
foldr :: forall a b. (a -> b -> b) -> b -> MonoidMap k a -> b
$cfoldr' :: forall k a b. (a -> b -> b) -> b -> MonoidMap k a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> MonoidMap k a -> b
$cfoldl :: forall k b a. (b -> a -> b) -> b -> MonoidMap k a -> b
foldl :: forall b a. (b -> a -> b) -> b -> MonoidMap k a -> b
$cfoldl' :: forall k b a. (b -> a -> b) -> b -> MonoidMap k a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> MonoidMap k a -> b
$cfoldr1 :: forall k a. (a -> a -> a) -> MonoidMap k a -> a
foldr1 :: forall a. (a -> a -> a) -> MonoidMap k a -> a
$cfoldl1 :: forall k a. (a -> a -> a) -> MonoidMap k a -> a
foldl1 :: forall a. (a -> a -> a) -> MonoidMap k a -> a
$ctoList :: forall k a. MonoidMap k a -> [a]
toList :: forall a. MonoidMap k a -> [a]
$cnull :: forall k a. MonoidMap k a -> Bool
null :: forall a. MonoidMap k a -> Bool
$clength :: forall k a. MonoidMap k a -> Int
length :: forall a. MonoidMap k a -> Int
$celem :: forall k a. Eq a => a -> MonoidMap k a -> Bool
elem :: forall a. Eq a => a -> MonoidMap k a -> Bool
$cmaximum :: forall k a. Ord a => MonoidMap k a -> a
maximum :: forall a. Ord a => MonoidMap k a -> a
$cminimum :: forall k a. Ord a => MonoidMap k a -> a
minimum :: forall a. Ord a => MonoidMap k a -> a
$csum :: forall k a. Num a => MonoidMap k a -> a
sum :: forall a. Num a => MonoidMap k a -> a
$cproduct :: forall k a. Num a => MonoidMap k a -> a
product :: forall a. Num a => MonoidMap k a -> a
Foldable)
        via Map k
    deriving ((forall k. Eq k => Eq1 (MonoidMap k)) =>
(forall a b c d.
 (a -> b -> Bool)
 -> (c -> d -> Bool) -> MonoidMap a c -> MonoidMap b d -> Bool)
-> Eq2 MonoidMap
forall k. Eq k => Eq1 (MonoidMap k)
forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> MonoidMap a c -> MonoidMap b d -> Bool
forall (f :: * -> * -> *).
(forall a. Eq a => Eq1 (f a)) =>
(forall a b c d.
 (a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool)
-> Eq2 f
$cliftEq2 :: forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> MonoidMap a c -> MonoidMap b d -> Bool
liftEq2 :: forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> MonoidMap a c -> MonoidMap b d -> Bool
Eq2, (forall k. Show k => Show1 (MonoidMap k)) =>
(forall a b.
 (Int -> a -> ShowS)
 -> ([a] -> ShowS)
 -> (Int -> b -> ShowS)
 -> ([b] -> ShowS)
 -> Int
 -> MonoidMap a b
 -> ShowS)
-> (forall a b.
    (Int -> a -> ShowS)
    -> ([a] -> ShowS)
    -> (Int -> b -> ShowS)
    -> ([b] -> ShowS)
    -> [MonoidMap a b]
    -> ShowS)
-> Show2 MonoidMap
forall k. Show k => Show1 (MonoidMap k)
forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> MonoidMap a b
-> ShowS
forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [MonoidMap a b]
-> ShowS
forall (f :: * -> * -> *).
(forall a. Show a => Show1 (f a)) =>
(forall a b.
 (Int -> a -> ShowS)
 -> ([a] -> ShowS)
 -> (Int -> b -> ShowS)
 -> ([b] -> ShowS)
 -> Int
 -> f a b
 -> ShowS)
-> (forall a b.
    (Int -> a -> ShowS)
    -> ([a] -> ShowS)
    -> (Int -> b -> ShowS)
    -> ([b] -> ShowS)
    -> [f a b]
    -> ShowS)
-> Show2 f
$cliftShowsPrec2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> MonoidMap a b
-> ShowS
liftShowsPrec2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> MonoidMap a b
-> ShowS
$cliftShowList2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [MonoidMap a b]
-> ShowS
liftShowList2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [MonoidMap a b]
-> ShowS
Show2, (forall m. Monoid m => MonoidMap m m -> m)
-> (forall m a b.
    Monoid m =>
    (a -> m) -> (b -> m) -> MonoidMap a b -> m)
-> (forall a c b.
    (a -> c -> c) -> (b -> c -> c) -> c -> MonoidMap a b -> c)
-> (forall c a b.
    (c -> a -> c) -> (c -> b -> c) -> c -> MonoidMap a b -> c)
-> Bifoldable MonoidMap
forall m. Monoid m => MonoidMap m m -> m
forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> MonoidMap a b -> m
forall c a b.
(c -> a -> c) -> (c -> b -> c) -> c -> MonoidMap a b -> c
forall a c b.
(a -> c -> c) -> (b -> c -> c) -> c -> MonoidMap a b -> c
forall (p :: * -> * -> *).
(forall m. Monoid m => p m m -> m)
-> (forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m)
-> (forall a c b.
    (a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c)
-> (forall c a b.
    (c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c)
-> Bifoldable p
$cbifold :: forall m. Monoid m => MonoidMap m m -> m
bifold :: forall m. Monoid m => MonoidMap m m -> m
$cbifoldMap :: forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> MonoidMap a b -> m
bifoldMap :: forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> MonoidMap a b -> m
$cbifoldr :: forall a c b.
(a -> c -> c) -> (b -> c -> c) -> c -> MonoidMap a b -> c
bifoldr :: forall a c b.
(a -> c -> c) -> (b -> c -> c) -> c -> MonoidMap a b -> c
$cbifoldl :: forall c a b.
(c -> a -> c) -> (c -> b -> c) -> c -> MonoidMap a b -> c
bifoldl :: forall c a b.
(c -> a -> c) -> (c -> b -> c) -> c -> MonoidMap a b -> c
Bifoldable)
        via Map

-- Internal alias used when extra brevity is required.
type MM = MonoidMap

--------------------------------------------------------------------------------
-- Non-null values
--------------------------------------------------------------------------------

newtype NonNull v = UnsafeNonNull {forall v. NonNull v -> v
getNonNull :: v}

maybeNonNull :: MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull :: forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull !v
v
    | v -> Bool
forall m. MonoidNull m => m -> Bool
C.null  v
v = Maybe (NonNull v)
forall a. Maybe a
Nothing
    | Bool
otherwise = NonNull v -> Maybe (NonNull v)
forall a. a -> Maybe a
Just (v -> NonNull v
forall v. v -> NonNull v
UnsafeNonNull v
v)
{-# INLINE maybeNonNull #-}

applyNonNull :: (v -> a) -> (NonNull v -> a)
applyNonNull :: forall v a. (v -> a) -> NonNull v -> a
applyNonNull = (v -> a) -> NonNull v -> a
forall a b. Coercible a b => a -> b
coerce
{-# INLINE applyNonNull #-}

applyNonNull2 :: (v1 -> v2 -> a) -> (NonNull v1 -> NonNull v2 -> a)
applyNonNull2 :: forall v1 v2 a. (v1 -> v2 -> a) -> NonNull v1 -> NonNull v2 -> a
applyNonNull2 = (v1 -> v2 -> a) -> NonNull v1 -> NonNull v2 -> a
forall a b. Coercible a b => a -> b
coerce
{-# INLINE applyNonNull2 #-}

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

instance (Ord k, MonoidNull v) =>
    IsList (MonoidMap k v)
  where
    type Item (MonoidMap k v) = (k, v)
    fromList :: [Item (MonoidMap k v)] -> MonoidMap k v
fromList = [(k, v)] -> MonoidMap k v
[Item (MonoidMap k v)] -> MonoidMap k v
forall k v. (Ord k, MonoidNull v) => [(k, v)] -> MonoidMap k v
fromList
    toList :: MonoidMap k v -> [Item (MonoidMap k v)]
toList = MonoidMap k v -> [(k, v)]
MonoidMap k v -> [Item (MonoidMap k v)]
forall k v. MonoidMap k v -> [(k, v)]
toList

instance (Ord k, Read k, MonoidNull v, Read v) =>
    Read (MonoidMap k v)
  where
    readPrec :: ReadPrec (MonoidMap k v)
readPrec = Map k v -> MonoidMap k v
forall v k. MonoidNull v => Map k v -> MonoidMap k v
fromMap (Map k v -> MonoidMap k v)
-> ReadPrec (Map k v) -> ReadPrec (MonoidMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReadPrec (Map k v)
forall a. Read a => ReadPrec a
readPrec

--------------------------------------------------------------------------------
-- Instances: Semigroup and subclasses
--------------------------------------------------------------------------------

instance (Ord k, MonoidNull v) =>
    Semigroup (MonoidMap k v)
  where
    <> :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
(<>) = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
append
    stimes :: forall b. Integral b => b -> MonoidMap k v -> MonoidMap k v
stimes b
0 = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall a b. a -> b -> a
const MonoidMap k v
forall a. Monoid a => a
mempty
    stimes b
1 = MonoidMap k v -> MonoidMap k v
forall a. a -> a
id
    stimes b
n = (v -> v) -> MonoidMap k v -> MonoidMap k v
forall v2 v1 k.
MonoidNull v2 =>
(v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2
map (b -> v -> v
forall b. Integral b => b -> v -> v
forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes b
n)

instance (Ord k, MonoidNull v, Commutative v) =>
    Commutative (MonoidMap k v)

instance (Ord k, MonoidNull v, LeftReductive v) =>
    LeftReductive (MonoidMap k v)
  where
    isPrefixOf :: MonoidMap k v -> MonoidMap k v -> Bool
isPrefixOf = MonoidMap k v -> MonoidMap k v -> Bool
forall k v.
(Ord k, Monoid v, LeftReductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
isPrefixOf
    stripPrefix :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripPrefix = MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall k v.
(Ord k, MonoidNull v, LeftReductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripPrefix

instance (Ord k, MonoidNull v, RightReductive v) =>
    RightReductive (MonoidMap k v)
  where
    isSuffixOf :: MonoidMap k v -> MonoidMap k v -> Bool
isSuffixOf = MonoidMap k v -> MonoidMap k v -> Bool
forall k v.
(Ord k, Monoid v, RightReductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
isSuffixOf
    stripSuffix :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripSuffix = MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall k v.
(Ord k, MonoidNull v, RightReductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripSuffix

instance (Ord k, MonoidNull v, Reductive v) =>
    Reductive (MonoidMap k v)
  where
    </> :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
(</>) = MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall k v.
(Ord k, MonoidNull v, Reductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
minusMaybe

instance (Ord k, MonoidNull v, LeftCancellative v) =>
    LeftCancellative (MonoidMap k v)

instance (Ord k, MonoidNull v, RightCancellative v) =>
    RightCancellative (MonoidMap k v)

instance (Ord k, MonoidNull v, Cancellative v) =>
    Cancellative (MonoidMap k v)

--------------------------------------------------------------------------------
-- Instances: Monoid and subclasses
--------------------------------------------------------------------------------

instance (Ord k, MonoidNull v) =>
    Monoid (MonoidMap k v)
  where
    mempty :: MonoidMap k v
mempty = MonoidMap k v
forall k v. MonoidMap k v
empty

instance (Ord k, MonoidNull v) =>
    MonoidNull (MonoidMap k v)
  where
    null :: MonoidMap k v -> Bool
null = MonoidMap k v -> Bool
forall k a. MonoidMap k a -> Bool
null

instance (Ord k, PositiveMonoid v) =>
    PositiveMonoid (MonoidMap k v)

instance (Ord k, MonoidNull v, LeftGCDMonoid v) =>
    LeftGCDMonoid (MonoidMap k v)
  where
    commonPrefix :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonPrefix = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, LeftGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonPrefix

instance (Ord k, MonoidNull v, LeftDistributiveGCDMonoid v) =>
    LeftDistributiveGCDMonoid (MonoidMap k v)

instance (Ord k, MonoidNull v, RightGCDMonoid v) =>
    RightGCDMonoid (MonoidMap k v)
  where
    commonSuffix :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonSuffix = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, RightGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonSuffix

instance (Ord k, MonoidNull v, RightDistributiveGCDMonoid v) =>
    RightDistributiveGCDMonoid (MonoidMap k v)

instance (Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
    OverlappingGCDMonoid (MonoidMap k v)
  where
    overlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
overlap = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
overlap
    stripPrefixOverlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripPrefixOverlap = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripPrefixOverlap
    stripSuffixOverlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripSuffixOverlap = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripSuffixOverlap
    stripOverlap :: MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripOverlap = MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripOverlap

instance (Ord k, MonoidNull v, GCDMonoid v) =>
    GCDMonoid (MonoidMap k v)
  where
    gcd :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
gcd = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, GCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
intersection

instance (Ord k, MonoidNull v, DistributiveGCDMonoid v) =>
    DistributiveGCDMonoid (MonoidMap k v)

instance (Ord k, MonoidNull v, LCMMonoid v) =>
    LCMMonoid (MonoidMap k v)
  where
    lcm :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
lcm = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, LCMMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
union

instance (Ord k, MonoidNull v, DistributiveLCMMonoid v) =>
    DistributiveLCMMonoid (MonoidMap k v)

instance (Ord k, MonoidNull v, Monus v) =>
    Monus (MonoidMap k v)
  where
    <\> :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
(<\>) = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, Monus v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
monus

--------------------------------------------------------------------------------
-- Instances: Group and subclasses
--------------------------------------------------------------------------------

instance (Ord k, MonoidNull v, Group v) =>
    Group (MonoidMap k v)
  where
    invert :: MonoidMap k v -> MonoidMap k v
invert = MonoidMap k v -> MonoidMap k v
forall v k.
(MonoidNull v, Group v) =>
MonoidMap k v -> MonoidMap k v
invert
    ~~ :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v
(~~) = MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, Group v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
minus
    pow :: forall x. Integral x => MonoidMap k v -> x -> MonoidMap k v
pow = MonoidMap k v -> x -> MonoidMap k v
forall i v k.
(Integral i, MonoidNull v, Group v) =>
MonoidMap k v -> i -> MonoidMap k v
power

instance (Ord k, MonoidNull v, Abelian v) =>
    Abelian (MonoidMap k v)

--------------------------------------------------------------------------------
-- Construction
--------------------------------------------------------------------------------

-- | \(O(1)\). The empty 'MonoidMap'.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k 'empty' '==' 'mempty'
-- @
--
-- Provides the definition of 'mempty' for the 'MonoidMap' instance of
-- 'Monoid'.
--
empty :: MonoidMap k v
empty :: forall k v. MonoidMap k v
empty = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap Map k (NonNull v)
forall k a. Map k a
Map.empty

-- | \(O(n \log n)\). Constructs a 'MonoidMap' from a list of key-value pairs.
--
-- If the list contains more than one value for the same key, values are
-- combined together in the order that they appear with the '(<>)' operator.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('fromList' kvs) '=='
--     'foldMap' 'snd' ('L.filter' (('==' k) . fst) kvs)
-- @
--
-- Satisfies the following round-trip property:
--
-- @
-- 'fromList' ('toList' m) '==' m
-- @
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> 'fromList' [(1,"a"), (2,"x"), (1,"b"), (2,"y"), (1,"c"), (2,"z")]
-- 'fromList' [(1,"abc"), (2,"xyz")]
-- @
--
fromList :: (Ord k, MonoidNull v) => [(k, v)] -> MonoidMap k v
fromList :: forall k v. (Ord k, MonoidNull v) => [(k, v)] -> MonoidMap k v
fromList = (v -> v -> v) -> [(k, v)] -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v) =>
(v -> v -> v) -> [(k, v)] -> MonoidMap k v
fromListWith v -> v -> v
forall a. Semigroup a => a -> a -> a
(<>)

-- | \(O(n \log n)\). Constructs a 'MonoidMap' from a list of key-value pairs,
--   with a combining function for values.
--
-- If the list contains more than one value for the same key, values are
-- combined together in the order that they appear with the given combining
-- function.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('fromListWith' f kvs) '=='
--     'maybe' 'mempty' ('F.foldl1' f)
--         ('NE.nonEmpty' ('snd' '<$>' 'L.filter' (('==' k) . fst) kvs))
-- @
--
fromListWith
    :: (Ord k, MonoidNull v)
    => (v -> v -> v)
    -- ^ Function with which to combine values for duplicate keys.
    -> [(k, v)]
    -> MonoidMap k v
fromListWith :: forall k v.
(Ord k, MonoidNull v) =>
(v -> v -> v) -> [(k, v)] -> MonoidMap k v
fromListWith v -> v -> v
f =
    -- The 'Map.fromListWith' function combines values for duplicate keys in
    -- /reverse order/, so we must flip the provided combining function.
    Map k v -> MonoidMap k v
forall v k. MonoidNull v => Map k v -> MonoidMap k v
fromMap (Map k v -> MonoidMap k v)
-> ([(k, v)] -> Map k v) -> [(k, v)] -> MonoidMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v -> v -> v) -> [(k, v)] -> Map k v
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith ((v -> v -> v) -> v -> v -> v
forall a b c. (a -> b -> c) -> b -> a -> c
flip v -> v -> v
f)

-- | \(O(n)\). Constructs a 'MonoidMap' from an ordinary 'Map'.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('fromMap' m) '==' 'Map'.'Map.findWithDefault' 'mempty' k m
-- @
--
-- This function performs canonicalisation of 'C.null' values, and has a time
-- complexity that is linear in the size of the map.
--
fromMap :: MonoidNull v => Map k v -> MonoidMap k v
fromMap :: forall v k. MonoidNull v => Map k v -> MonoidMap k v
fromMap = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> (Map k v -> Map k (NonNull v)) -> Map k v -> MonoidMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v -> Maybe (NonNull v)) -> Map k v -> Map k (NonNull v)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe v -> Maybe (NonNull v)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull

-- | \(O(n)\). Constructs a 'MonoidMap' from an ordinary 'Map', applying
--   the given function to all values.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('fromMapWith' f m) '==' 'maybe' 'mempty' f ('Map'.'Map.lookup' k m)
-- @
--
-- This function performs canonicalisation of 'C.null' values, and has a time
-- complexity that is linear in the size of the map.
--
-- @since 0.0.4.0
--
fromMapWith :: MonoidNull v2 => (v1 -> v2) -> Map k v1 -> MonoidMap k v2
fromMapWith :: forall v2 v1 k.
MonoidNull v2 =>
(v1 -> v2) -> Map k v1 -> MonoidMap k v2
fromMapWith v1 -> v2
f = Map k (NonNull v2) -> MonoidMap k v2
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v2) -> MonoidMap k v2)
-> (Map k v1 -> Map k (NonNull v2)) -> Map k v1 -> MonoidMap k v2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v1 -> Maybe (NonNull v2)) -> Map k v1 -> Map k (NonNull v2)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2))
-> (v1 -> v2) -> v1 -> Maybe (NonNull v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v1 -> v2
f)

-- | \(O(n)\). Constructs a 'MonoidMap' from a 'Set' and a function from
--   keys to values.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('fromSet' f ks) '=='
--     if 'Set'.'Set.member' k ks
--     then f k
--     else 'mempty'
-- @
--
-- This function performs canonicalisation of 'C.null' values, and has a time
-- complexity that is linear in the 'Set.size' of the set.
--
-- @since 0.0.2.0
--
fromSet :: MonoidNull v => (k -> v) -> Set k -> MonoidMap k v
fromSet :: forall v k. MonoidNull v => (k -> v) -> Set k -> MonoidMap k v
fromSet k -> v
f = Map k v -> MonoidMap k v
forall v k. MonoidNull v => Map k v -> MonoidMap k v
fromMap (Map k v -> MonoidMap k v)
-> (Set k -> Map k v) -> Set k -> MonoidMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> v) -> Set k -> Map k v
forall k a. (k -> a) -> Set k -> Map k a
Map.fromSet k -> v
f

-- | \(O(1)\). Constructs a 'MonoidMap' from a single key-value pair.
--
-- Satisfies the following property:
--
-- @
-- 'get' k ('singleton' k v) '==' v
-- @
--
-- Nullifying the value for key __@k@__ produces an 'empty' map:
--
-- @
-- 'nullify' k ('singleton' k v) '==' 'empty'
-- @
--
singleton :: (Ord k, MonoidNull v) => k -> v -> MonoidMap k v
singleton :: forall k v. (Ord k, MonoidNull v) => k -> v -> MonoidMap k v
singleton k
k v
v = k -> v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v) =>
k -> v -> MonoidMap k v -> MonoidMap k v
set k
k v
v MonoidMap k v
forall a. Monoid a => a
mempty

--------------------------------------------------------------------------------
-- Deconstruction
--------------------------------------------------------------------------------

-- | \(O(n)\). Converts a 'MonoidMap' to a list of key-value pairs, where the
--   keys are in ascending order.
--
-- The result only includes entries with values that are not 'C.null'.
--
-- Satisfies the following round-trip property:
--
-- @
-- 'fromList' ('toList' m) '==' m
-- @
--
-- The resulting list is sorted in ascending key order:
--
-- @
-- 'L.sortOn' 'fst' ('toList' m) '==' 'toList' m
-- @
--
toList :: MonoidMap k v -> [(k, v)]
toList :: forall k v. MonoidMap k v -> [(k, v)]
toList = Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toAscList (Map k v -> [(k, v)])
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

-- | \(O(1)\). Converts a 'MonoidMap' to an ordinary 'Map'.
--
-- The result only includes entries with values that are not 'C.null'.
--
-- Satisfies the following round-trip property:
--
-- @
-- 'fromMap' ('toMap' m) '==' m
-- @
--
toMap :: forall k v. MonoidMap k v -> Map k v
toMap :: forall k v. MonoidMap k v -> Map k v
toMap = MonoidMap k v -> Map k v
forall a b. Coercible a b => a -> b
coerce

--------------------------------------------------------------------------------
-- Lookup
--------------------------------------------------------------------------------

-- | \(O(\log n)\). Gets the value associated with the given key.
--
-- By default, every key in an 'empty' map is associated with a value of
-- 'mempty':
--
-- @
-- ∀ k. 'get' k 'empty' '==' 'mempty'
-- @
--
get :: (Ord k, Monoid v) => k -> MonoidMap k v -> v
get :: forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
get k
k MonoidMap k v
m = v -> Maybe v -> v
forall a. a -> Maybe a -> a
fromMaybe v
forall a. Monoid a => a
mempty (Maybe v -> v) -> Maybe v -> v
forall a b. (a -> b) -> a -> b
$ k -> Map k v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k (Map k v -> Maybe v) -> Map k v -> Maybe v
forall a b. (a -> b) -> a -> b
$ MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap MonoidMap k v
m

--------------------------------------------------------------------------------
-- Modification
--------------------------------------------------------------------------------

-- | \(O(\log n)\). Sets the value associated with the given key.
--
-- Satisfies the following property:
--
-- @
-- 'get' k ('set' k v m) '==' v
-- @
--
set :: (Ord k, MonoidNull v) => k -> v -> MonoidMap k v -> MonoidMap k v
set :: forall k v.
(Ord k, MonoidNull v) =>
k -> v -> MonoidMap k v -> MonoidMap k v
set k
k v
v (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$ case v -> Maybe (NonNull v)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull v
v of
    Just NonNull v
v0 -> k -> NonNull v -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k NonNull v
v0 Map k (NonNull v)
m
    Maybe (NonNull v)
Nothing -> k -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k    Map k (NonNull v)
m

-- | \(O(\log n)\). Adjusts the value associated with the given key.
--
-- Satisfies the following property:
--
-- @
-- 'adjust' f k m '==' 'set' k (f ('get' k m)) m
-- @
--
adjust
    :: (Ord k, MonoidNull v)
    => (v -> v)
    -> k
    -> MonoidMap k v
    -> MonoidMap k v
adjust :: forall k v.
(Ord k, MonoidNull v) =>
(v -> v) -> k -> MonoidMap k v -> MonoidMap k v
adjust v -> v
f k
k (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$
    (Maybe (NonNull v) -> Maybe (NonNull v))
-> k -> Map k (NonNull v) -> Map k (NonNull v)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (v -> Maybe (NonNull v)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v -> Maybe (NonNull v))
-> (Maybe (NonNull v) -> v)
-> Maybe (NonNull v)
-> Maybe (NonNull v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> (NonNull v -> v) -> Maybe (NonNull v) -> v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (v -> v
f v
forall a. Monoid a => a
mempty) ((v -> v) -> NonNull v -> v
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v -> v
f)) k
k Map k (NonNull v)
m

-- | \(O(\log n)\). Sets the value associated with the given key to 'mempty'.
--
-- Satisfies the following property:
--
-- @
-- 'get' k ('nullify' k m) '==' 'mempty'
-- @
--
nullify :: Ord k => k -> MonoidMap k v -> MonoidMap k v
nullify :: forall k v. Ord k => k -> MonoidMap k v -> MonoidMap k v
nullify k
k (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$ k -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k (NonNull v)
m

--------------------------------------------------------------------------------
-- Membership
--------------------------------------------------------------------------------

-- | \(O(1)\). Returns 'True' if (and only if) all values in the map are
--   'C.null'.
--
-- Satisfies the following property:
--
-- @
-- 'null' m '==' (∀ k. 'nullKey' k m)
-- @
--
-- Provides the definition of 'C.null' for the 'MonoidMap' instance of
-- 'MonoidNull'.
--
null :: MonoidMap k v -> Bool
null :: forall k a. MonoidMap k a -> Bool
null = Map k v -> Bool
forall k a. Map k a -> Bool
Map.null (Map k v -> Bool)
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

-- | \(O(\log n)\). Returns 'True' if (and only if) the given key is associated
--   with a value that is 'C.null'.
--
-- Satisfies the following property:
--
-- @
-- 'nullKey' k m '==' 'C.null' ('get' k m)
-- @
--
nullKey :: Ord k => k -> MonoidMap k v -> Bool
nullKey :: forall k v. Ord k => k -> MonoidMap k v -> Bool
nullKey k
k = k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.notMember k
k (Map k v -> Bool)
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

-- | \(O(1)\). Returns 'True' if (and only if) the map contains at least one
--   value that is not 'C.null'.
--
-- Satisfies the following property:
--
-- @
-- 'nonNull' m '==' (∃ k. 'nonNullKey' k m)
-- @
--
nonNull :: MonoidMap k v -> Bool
nonNull :: forall k a. MonoidMap k a -> Bool
nonNull = Bool -> Bool
not (Bool -> Bool) -> (MonoidMap k v -> Bool) -> MonoidMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Bool
forall k a. MonoidMap k a -> Bool
null

-- | \(O(1)\). Returns a count of all values in the map that are not 'C.null'.
--
-- Satisfies the following property:
--
-- @
-- 'nonNullCount' m '==' 'Set.size' ('nonNullKeys' m)
-- @
--
nonNullCount :: MonoidMap k v -> Int
nonNullCount :: forall k a. MonoidMap k a -> Int
nonNullCount = Map k v -> Int
forall k a. Map k a -> Int
Map.size (Map k v -> Int)
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

-- | \(O(\log n)\). Returns 'True' if (and only if) the given key is associated
--   with a value that is not 'C.null'.
--
-- Satisfies the following property:
--
-- @
-- 'nonNullKey' k m '==' 'not' ('C.null' ('get' k m))
-- @
--
nonNullKey :: Ord k => k -> MonoidMap k v -> Bool
nonNullKey :: forall k v. Ord k => k -> MonoidMap k v -> Bool
nonNullKey k
k = k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k (Map k v -> Bool)
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

-- | \(O(n)\). Returns the set of keys associated with values that are not
--   'C.null'.
--
-- Satisfies the following property:
--
-- @
-- k '`Set.member`' ('nonNullKeys' m) '==' 'nonNullKey' k m
-- @
--
nonNullKeys :: MonoidMap k v -> Set k
nonNullKeys :: forall k v. MonoidMap k v -> Set k
nonNullKeys = Map k v -> Set k
forall k a. Map k a -> Set k
Map.keysSet (Map k v -> Set k)
-> (MonoidMap k v -> Map k v) -> MonoidMap k v -> Set k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k v -> Map k v
forall k v. MonoidMap k v -> Map k v
toMap

--------------------------------------------------------------------------------
-- Slicing
--------------------------------------------------------------------------------

-- | \(O(\log n)\). /Takes/ a slice from a map.
--
-- This function takes a given number of non-'C.null' entries from a map,
-- producing a new map from the entries that were /taken/.
--
-- Entries are taken in /key order/, beginning with the /smallest/ keys.
--
-- Satifies the following property:
--
-- @
-- 'take' n '==' 'fromList' . 'Prelude.take' n . 'toList'
-- @
--
take :: Int -> MonoidMap k v -> MonoidMap k v
take :: forall k v. Int -> MonoidMap k v -> MonoidMap k v
take Int
i (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Int -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. Int -> Map k a -> Map k a
Map.take Int
i Map k (NonNull v)
m)

-- | \(O(\log n)\). /Drops/ a slice from a map.
--
-- This function drops a given number of non-'C.null' entries from a map,
-- producing a new map from the entries that /remain/.
--
-- Entries are dropped in /key order/, beginning with the /smallest/ keys.
--
-- Satifies the following property:
--
-- @
-- 'drop' n '==' 'fromList' . 'Prelude.drop' n . 'toList'
-- @
--
drop :: Int -> MonoidMap k v -> MonoidMap k v
drop :: forall k v. Int -> MonoidMap k v -> MonoidMap k v
drop Int
i (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Int -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. Int -> Map k a -> Map k a
Map.drop Int
i Map k (NonNull v)
m)

-- | \(O(\log n)\). /Splits/ a map into /two/ slices.
--
-- This function is equivalent to a combination of 'take' and 'drop':
--
-- @
-- 'splitAt' n m '==' ('take' n m, 'drop' n m)
-- @
--
-- The resulting maps can be combined to reproduce the original map:
--
-- @
-- 'splitAt' n m '&'
--     \\(m1, m2) -> m1 '<>' m2 '==' m
-- @
--
-- The resulting maps have disjoint sets of non-'C.null' entries:
--
-- @
-- 'splitAt' n m '&'
--     \\(m1, m2) -> 'Set.disjoint' ('nonNullKeys' m1) ('nonNullKeys' m2)
-- @
--
splitAt :: Int -> MonoidMap k a -> (MonoidMap k a, MonoidMap k a)
splitAt :: forall k a. Int -> MonoidMap k a -> (MonoidMap k a, MonoidMap k a)
splitAt Int
i MonoidMap k a
m = (Int -> MonoidMap k a -> MonoidMap k a
forall k v. Int -> MonoidMap k v -> MonoidMap k v
take Int
i MonoidMap k a
m, Int -> MonoidMap k a -> MonoidMap k a
forall k v. Int -> MonoidMap k v -> MonoidMap k v
drop Int
i MonoidMap k a
m)

--------------------------------------------------------------------------------
-- Filtering
--------------------------------------------------------------------------------

-- | \(O(n)\). Filters a map according to a predicate on /values/.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('filter' f m) '=='
--     if f ('get' k m)
--     then 'get' k m
--     else 'mempty'
-- @
--
-- The resulting map is identical to that obtained by constructing a map from a
-- filtered list of key-value pairs:
--
-- @
-- 'filter' f m '==' 'fromList' ('L.filter' (f . 'snd') ('toList' m))
-- @
--
filter :: (v -> Bool) -> MonoidMap k v -> MonoidMap k v
filter :: forall v k. (v -> Bool) -> MonoidMap k v -> MonoidMap k v
filter v -> Bool
f (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$ (NonNull v -> Bool) -> Map k (NonNull v) -> Map k (NonNull v)
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter ((v -> Bool) -> NonNull v -> Bool
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v -> Bool
f) Map k (NonNull v)
m

-- | \(O(n)\). Filters a map according to a predicate on /keys/.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('filterKeys' f m) '=='
--     if f k
--     then 'get' k m
--     else 'mempty'
-- @
--
-- The resulting map is identical to that obtained by constructing a map from a
-- filtered list of key-value pairs:
--
-- @
-- 'filter' f m '==' 'fromList' ('L.filter' (f . 'fst') ('toList' m))
-- @
--
filterKeys :: (k -> Bool) -> MonoidMap k v -> MonoidMap k v
filterKeys :: forall k v. (k -> Bool) -> MonoidMap k v -> MonoidMap k v
filterKeys k -> Bool
f (MonoidMap Map k (NonNull v)
m) = Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$ (k -> NonNull v -> Bool) -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey (\k
k NonNull v
_ -> k -> Bool
f k
k) Map k (NonNull v)
m

-- | \(O(n)\). Filters a map according to a predicate on /keys and values/.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('filterWithKey' f m) '=='
--     if f k ('get' k m)
--     then 'get' k m
--     else 'mempty'
-- @
--
-- The resulting map is identical to that obtained by constructing a map from a
-- filtered list of key-value pairs:
--
-- @
-- 'filterWithKey' f m '==' 'fromList' ('L.filter' ('uncurry' f) ('toList' m))
-- @
--
filterWithKey :: (k -> v -> Bool) -> MonoidMap k v -> MonoidMap k v
filterWithKey :: forall k v. (k -> v -> Bool) -> MonoidMap k v -> MonoidMap k v
filterWithKey k -> v -> Bool
f (MonoidMap Map k (NonNull v)
m) =
    Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v) -> MonoidMap k v)
-> Map k (NonNull v) -> MonoidMap k v
forall a b. (a -> b) -> a -> b
$ (k -> NonNull v -> Bool) -> Map k (NonNull v) -> Map k (NonNull v)
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey ((v -> Bool) -> NonNull v -> Bool
forall v a. (v -> a) -> NonNull v -> a
applyNonNull ((v -> Bool) -> NonNull v -> Bool)
-> (k -> v -> Bool) -> k -> NonNull v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v -> Bool
f) Map k (NonNull v)
m

--------------------------------------------------------------------------------
-- Partitioning
--------------------------------------------------------------------------------

-- | \(O(n)\). Partitions a map according to a predicate on /values/.
--
-- Satisfies the following property:
--
-- @
-- 'partition' f m '=='
--     ( 'filter'  \   \   f  m
--     , 'filter' ('not' . f) m
--     )
-- @
--
-- The resulting maps can be combined to reproduce the original map:
--
-- @
-- 'partition' f m '&' \\(m1, m2) ->
--     m1 '<>' m2 '==' m
-- @
--
-- The resulting maps have disjoint sets of non-'C.null' entries:
--
-- @
-- 'partition' f m '&' \\(m1, m2) ->
--     'Set.disjoint'
--         ('nonNullKeys' m1)
--         ('nonNullKeys' m2)
-- @
--
partition :: (v -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partition :: forall v k.
(v -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partition v -> Bool
f (MonoidMap Map k (NonNull v)
m) =
    (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
B.bimap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap ((Map k (NonNull v), Map k (NonNull v))
 -> (MonoidMap k v, MonoidMap k v))
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b. (a -> b) -> a -> b
$ (NonNull v -> Bool)
-> Map k (NonNull v) -> (Map k (NonNull v), Map k (NonNull v))
forall a k. (a -> Bool) -> Map k a -> (Map k a, Map k a)
Map.partition ((v -> Bool) -> NonNull v -> Bool
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v -> Bool
f) Map k (NonNull v)
m

-- | \(O(n)\). Partitions a map according to a predicate on /keys/.
--
-- Satisfies the following property:
--
-- @
-- 'partitionKeys' f m '=='
--     ( 'filterKeys'  \   \   f  m
--     , 'filterKeys' ('not' . f) m
--     )
-- @
--
-- The resulting maps can be combined to reproduce the original map:
--
-- @
-- 'partitionKeys' f m '&' \\(m1, m2) ->
--     m1 '<>' m2 '==' m
-- @
--
-- The resulting maps have disjoint sets of non-'C.null' entries:
--
-- @
-- 'partitionKeys' f m '&' \\(m1, m2) ->
--     'Set.disjoint'
--         ('nonNullKeys' m1)
--         ('nonNullKeys' m2)
-- @
--
partitionKeys
    :: (k -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partitionKeys :: forall k v.
(k -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partitionKeys k -> Bool
f (MonoidMap Map k (NonNull v)
m) =
    (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
B.bimap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap ((Map k (NonNull v), Map k (NonNull v))
 -> (MonoidMap k v, MonoidMap k v))
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b. (a -> b) -> a -> b
$ (k -> NonNull v -> Bool)
-> Map k (NonNull v) -> (Map k (NonNull v), Map k (NonNull v))
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
Map.partitionWithKey (\k
k NonNull v
_ -> k -> Bool
f k
k) Map k (NonNull v)
m

-- | \(O(n)\). Partitions a map according to a predicate on /keys and values/.
--
-- Satisfies the following property:
--
-- @
-- 'partitionWithKey' f m '=='
--     ( 'filterWithKey'   \    \   \    \  \   \ f  m
--     , 'filterWithKey' (('fmap' . 'fmap') 'not' f) m
--     )
-- @
--
-- The resulting maps can be combined to reproduce the original map:
--
-- @
-- 'partitionWithKey' f m '&' \\(m1, m2) ->
--     m1 '<>' m2 '==' m
-- @
--
-- The resulting maps have disjoint sets of non-'C.null' entries:
--
-- @
-- 'partitionWithKey' f m '&' \\(m1, m2) ->
--     'Set.disjoint'
--         ('nonNullKeys' m1)
--         ('nonNullKeys' m2)
-- @
--
partitionWithKey
    :: (k -> v -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partitionWithKey :: forall k v.
(k -> v -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)
partitionWithKey k -> v -> Bool
f (MonoidMap Map k (NonNull v)
m) =
    (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v) -> MonoidMap k v)
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
B.bimap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap Map k (NonNull v) -> MonoidMap k v
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap ((Map k (NonNull v), Map k (NonNull v))
 -> (MonoidMap k v, MonoidMap k v))
-> (Map k (NonNull v), Map k (NonNull v))
-> (MonoidMap k v, MonoidMap k v)
forall a b. (a -> b) -> a -> b
$ (k -> NonNull v -> Bool)
-> Map k (NonNull v) -> (Map k (NonNull v), Map k (NonNull v))
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
Map.partitionWithKey ((v -> Bool) -> NonNull v -> Bool
forall v a. (v -> a) -> NonNull v -> a
applyNonNull ((v -> Bool) -> NonNull v -> Bool)
-> (k -> v -> Bool) -> k -> NonNull v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v -> Bool
f) Map k (NonNull v)
m

--------------------------------------------------------------------------------
-- Mapping
--------------------------------------------------------------------------------

-- | \(O(n)\). Applies a function to all non-'C.null' values of a 'MonoidMap'.
--
-- Satisfies the following properties for all functions __@f@__:
--
-- @
-- ('get' k m '==' 'mempty') ==> ('get' k ('map' f m) '==' 'mempty'     )
-- ('get' k m '/=' 'mempty') ==> ('get' k ('map' f m) '==' f ('get' k m))
-- @
--
-- === Conditional properties
--
-- If applying function __@f@__ to 'mempty' produces 'mempty', then the
-- following additional properties hold:
--
-- @
-- (f 'mempty' '==' 'mempty')
--     ==>
--     (∀ k. 'get' k ('map' f m) '==' f ('get' k m))
-- @
--
-- @
-- (f 'mempty' '==' 'mempty')
--     ==>
--     (∀ g. 'map' (f . g) m '==' 'map' f ('map' g m))
-- @
--
map
    :: MonoidNull v2
    => (v1 -> v2)
    -> MonoidMap k v1
    -> MonoidMap k v2
map :: forall v2 v1 k.
MonoidNull v2 =>
(v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2
map v1 -> v2
f (MonoidMap Map k (NonNull v1)
m) =
    Map k (NonNull v2) -> MonoidMap k v2
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v2) -> MonoidMap k v2)
-> Map k (NonNull v2) -> MonoidMap k v2
forall a b. (a -> b) -> a -> b
$ (NonNull v1 -> Maybe (NonNull v2))
-> Map k (NonNull v1) -> Map k (NonNull v2)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2))
-> (NonNull v1 -> v2) -> NonNull v1 -> Maybe (NonNull v2)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v1 -> v2) -> NonNull v1 -> v2
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v1 -> v2
f) Map k (NonNull v1)
m

-- | \(O(n \log n)\). Applies a function to all the keys of a 'MonoidMap' that
--   are associated with non-'C.null' values.
--
-- If the resultant map would contain more than one value for the same key,
-- values are combined together in ascending key order with the '(<>)'
-- operator.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('mapKeys' f m) '=='
--     'F.foldMap'
--         ('`get`' m)
--         ('Set.filter' (('==') k . f) ('nonNullKeys' m))
-- @
--
mapKeys
    :: (Ord k2, MonoidNull v)
    => (k1 -> k2)
    -> MonoidMap k1 v
    -> MonoidMap k2 v
mapKeys :: forall k2 v k1.
(Ord k2, MonoidNull v) =>
(k1 -> k2) -> MonoidMap k1 v -> MonoidMap k2 v
mapKeys = (v -> v -> v) -> (k1 -> k2) -> MonoidMap k1 v -> MonoidMap k2 v
forall k2 v k1.
(Ord k2, MonoidNull v) =>
(v -> v -> v) -> (k1 -> k2) -> MonoidMap k1 v -> MonoidMap k2 v
mapKeysWith v -> v -> v
forall a. Semigroup a => a -> a -> a
(<>)

-- | \(O(n \log n)\). Applies a function to all the keys of a 'MonoidMap' that
--   are associated with non-'C.null' values, with a combining function for
--   values.
--
-- If the resultant map would contain more than one value for the same key,
-- values are combined together in ascending key order with the given
-- combining function.
--
-- Satisfies the following property:
--
-- @
-- 'mapKeysWith' c f '==' 'fromListWith' c . 'fmap' ('B.first' f) . 'toList'
-- @
--
mapKeysWith
    :: (Ord k2, MonoidNull v)
    => (v -> v -> v)
    -- ^ Function with which to combine values for duplicate keys.
    -> (k1 -> k2)
    -> MonoidMap k1 v
    -> MonoidMap k2 v
mapKeysWith :: forall k2 v k1.
(Ord k2, MonoidNull v) =>
(v -> v -> v) -> (k1 -> k2) -> MonoidMap k1 v -> MonoidMap k2 v
mapKeysWith v -> v -> v
combine k1 -> k2
fk = (v -> v -> v) -> [(k2, v)] -> MonoidMap k2 v
forall k v.
(Ord k, MonoidNull v) =>
(v -> v -> v) -> [(k, v)] -> MonoidMap k v
fromListWith v -> v -> v
combine ([(k2, v)] -> MonoidMap k2 v)
-> (MonoidMap k1 v -> [(k2, v)])
-> MonoidMap k1 v
-> MonoidMap k2 v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1, v) -> (k2, v)) -> [(k1, v)] -> [(k2, v)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k1 -> k2) -> (k1, v) -> (k2, v)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
B.first k1 -> k2
fk) ([(k1, v)] -> [(k2, v)])
-> (MonoidMap k1 v -> [(k1, v)]) -> MonoidMap k1 v -> [(k2, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap k1 v -> [(k1, v)]
forall k v. MonoidMap k v -> [(k, v)]
toList

-- | \(O(n)\). Applies a key-dependent function to all non-'C.null' values of
--   a 'MonoidMap'.
--
-- Satisfies the following properties for all functions __@f@__:
--
-- @
-- ('nonNullKey' k m) ==> ('get' k ('mapWithKey' f m) '==' f k ('get' k m))
-- (   'nullKey' k m) ==> ('get' k ('mapWithKey' f m) '==' 'mempty'       )
-- @
--
-- @since 0.0.3.0
--
mapWithKey
    :: MonoidNull v2
    => (k -> v1 -> v2)
    -> MonoidMap k v1
    -> MonoidMap k v2
mapWithKey :: forall v2 k v1.
MonoidNull v2 =>
(k -> v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2
mapWithKey k -> v1 -> v2
f (MonoidMap Map k (NonNull v1)
m) =
    Map k (NonNull v2) -> MonoidMap k v2
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v2) -> MonoidMap k v2)
-> (Identity (Map k (NonNull v2)) -> Map k (NonNull v2))
-> Identity (Map k (NonNull v2))
-> MonoidMap k v2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Identity (Map k (NonNull v2)) -> Map k (NonNull v2)
forall a. Identity a -> a
runIdentity (Identity (Map k (NonNull v2)) -> MonoidMap k v2)
-> Identity (Map k (NonNull v2)) -> MonoidMap k v2
forall a b. (a -> b) -> a -> b
$
    (k -> NonNull v1 -> Identity (Maybe (NonNull v2)))
-> Map k (NonNull v1) -> Identity (Map k (NonNull v2))
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey
        (\k
k NonNull v1
v -> Maybe (NonNull v2) -> Identity (Maybe (NonNull v2))
forall a. a -> Identity a
Identity (Maybe (NonNull v2) -> Identity (Maybe (NonNull v2)))
-> Maybe (NonNull v2) -> Identity (Maybe (NonNull v2))
forall a b. (a -> b) -> a -> b
$ v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2)) -> v2 -> Maybe (NonNull v2)
forall a b. (a -> b) -> a -> b
$ (v1 -> v2) -> NonNull v1 -> v2
forall v a. (v -> a) -> NonNull v -> a
applyNonNull (k -> v1 -> v2
f k
k) NonNull v1
v) Map k (NonNull v1)
m

--------------------------------------------------------------------------------
-- Lazy folding
--------------------------------------------------------------------------------

-- | \(O(n)\). Folds over the values in the map using the given
--   left-associative binary operator.
--
-- Satisfies the following property:
--
-- @
-- 'foldl' f r m '==' 'Map'.'Map.foldl' f r ('toMap' m)
-- @
--
-- @since 0.0.1.7
--
foldl :: (r -> v -> r) -> r -> MonoidMap k v -> r
foldl :: forall r v k. (r -> v -> r) -> r -> MonoidMap k v -> r
foldl =
    (((r -> v -> r) -> r -> Map k v -> r)
-> (r -> v -> r) -> r -> MonoidMap k v -> r
forall {r} {v} {k}.
((r -> v -> r) -> r -> Map k v -> r)
-> (r -> v -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((r -> v -> r) -> r ->       Map k v -> r)
        -> ((r -> v -> r) -> r -> MonoidMap k v -> r)
    )
    (r -> v -> r) -> r -> Map k v -> r
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl
{-# INLINE foldl #-}

-- | \(O(n)\). Folds over the values in the map using the given
--   right-associative binary operator.
--
-- Satisfies the following property:
--
-- @
-- 'foldr' f r m '==' 'Map'.'Map.foldr' f r ('toMap' m)
-- @
--
-- @since 0.0.1.7
--
foldr :: (v -> r -> r) -> r -> MonoidMap k v -> r
foldr :: forall v r k. (v -> r -> r) -> r -> MonoidMap k v -> r
foldr =
    (((v -> r -> r) -> r -> Map k v -> r)
-> (v -> r -> r) -> r -> MonoidMap k v -> r
forall {v} {r} {k}.
((v -> r -> r) -> r -> Map k v -> r)
-> (v -> r -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((v -> r -> r) -> r ->       Map k v -> r)
        -> ((v -> r -> r) -> r -> MonoidMap k v -> r)
    )
    (v -> r -> r) -> r -> Map k v -> r
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr
{-# INLINE foldr #-}

-- | \(O(n)\). Folds over the keys and values in the map using the given
--   left-associative binary operator.
--
-- Satisfies the following property:
--
-- @
-- 'foldlWithKey' f r m '==' 'Map'.'Map.foldlWithKey' f r ('toMap' m)
-- @
--
-- @since 0.0.1.7
--
foldlWithKey :: (r -> k -> v -> r) -> r -> MonoidMap k v -> r
foldlWithKey :: forall r k v. (r -> k -> v -> r) -> r -> MonoidMap k v -> r
foldlWithKey =
    (((r -> k -> v -> r) -> r -> Map k v -> r)
-> (r -> k -> v -> r) -> r -> MonoidMap k v -> r
forall {r} {k} {v}.
((r -> k -> v -> r) -> r -> Map k v -> r)
-> (r -> k -> v -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((r -> k -> v -> r) -> r ->       Map k v -> r)
        -> ((r -> k -> v -> r) -> r -> MonoidMap k v -> r)
    )
    (r -> k -> v -> r) -> r -> Map k v -> r
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey
{-# INLINE foldlWithKey #-}

-- | \(O(n)\). Folds over the keys and values in the map using the given
--   right-associative binary operator.
--
-- Satisfies the following property:
--
-- @
-- 'foldrWithKey' f r m '==' 'Map'.'Map.foldrWithKey' f r ('toMap' m)
-- @
--
-- @since 0.0.1.7
--
foldrWithKey :: (k -> v -> r -> r) -> r -> MonoidMap k v -> r
foldrWithKey :: forall k v r. (k -> v -> r -> r) -> r -> MonoidMap k v -> r
foldrWithKey =
    (((k -> v -> r -> r) -> r -> Map k v -> r)
-> (k -> v -> r -> r) -> r -> MonoidMap k v -> r
forall {k} {v} {r}.
((k -> v -> r -> r) -> r -> Map k v -> r)
-> (k -> v -> r -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((k -> v -> r -> r) -> r ->       Map k v -> r)
        -> ((k -> v -> r -> r) -> r -> MonoidMap k v -> r)
    )
    (k -> v -> r -> r) -> r -> Map k v -> r
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey
{-# INLINE foldrWithKey #-}

-- | \(O(n)\). Folds over the keys and values in the map using the given
--   monoid.
--
-- Satisfies the following property:
--
-- @
-- 'foldMapWithKey' f m '==' 'Map'.'Map.foldMapWithKey' f ('toMap' m)
-- @
--
-- @since 0.0.1.7
--
foldMapWithKey :: Monoid r => (k -> v -> r) -> MonoidMap k v -> r
foldMapWithKey :: forall r k v. Monoid r => (k -> v -> r) -> MonoidMap k v -> r
foldMapWithKey =
    (((k -> v -> r) -> Map k v -> r)
-> (k -> v -> r) -> MonoidMap k v -> r
forall {k} {v} {r}.
((k -> v -> r) -> Map k v -> r)
-> (k -> v -> r) -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((k -> v -> r) ->       Map k v -> r)
        -> ((k -> v -> r) -> MonoidMap k v -> r)
    )
    (k -> v -> r) -> Map k v -> r
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey
{-# INLINE foldMapWithKey #-}

--------------------------------------------------------------------------------
-- Strict folding
--------------------------------------------------------------------------------

-- | \(O(n)\). A strict version of 'foldl'.
--
-- Each application of the operator is evaluated before using the result in the
-- next application. This function is strict in the starting value.
--
-- @since 0.0.1.7
--
foldl' :: (r -> v -> r) -> r -> MonoidMap k v -> r
foldl' :: forall r v k. (r -> v -> r) -> r -> MonoidMap k v -> r
foldl' =
    (((r -> v -> r) -> r -> Map k v -> r)
-> (r -> v -> r) -> r -> MonoidMap k v -> r
forall {r} {v} {k}.
((r -> v -> r) -> r -> Map k v -> r)
-> (r -> v -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((r -> v -> r) -> r ->       Map k v -> r)
        -> ((r -> v -> r) -> r -> MonoidMap k v -> r)
    )
    (r -> v -> r) -> r -> Map k v -> r
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl'
{-# INLINE foldl' #-}

-- | \(O(n)\). A strict version of 'foldr'.
--
-- Each application of the operator is evaluated before using the result in the
-- next application. This function is strict in the starting value.
--
-- @since 0.0.1.7
--
foldr' :: (v -> r -> r) -> r -> MonoidMap k v -> r
foldr' :: forall v r k. (v -> r -> r) -> r -> MonoidMap k v -> r
foldr' =
    (((v -> r -> r) -> r -> Map k v -> r)
-> (v -> r -> r) -> r -> MonoidMap k v -> r
forall {v} {r} {k}.
((v -> r -> r) -> r -> Map k v -> r)
-> (v -> r -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((v -> r -> r) -> r ->       Map k v -> r)
        -> ((v -> r -> r) -> r -> MonoidMap k v -> r)
    )
    (v -> r -> r) -> r -> Map k v -> r
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr'
{-# INLINE foldr' #-}

-- | \(O(n)\). A strict version of 'foldlWithKey'.
--
-- Each application of the operator is evaluated before using the result in the
-- next application. This function is strict in the starting value.
--
-- @since 0.0.1.7
--
foldlWithKey' :: (r -> k -> v -> r) -> r -> MonoidMap k v -> r
foldlWithKey' :: forall r k v. (r -> k -> v -> r) -> r -> MonoidMap k v -> r
foldlWithKey' =
    (((r -> k -> v -> r) -> r -> Map k v -> r)
-> (r -> k -> v -> r) -> r -> MonoidMap k v -> r
forall {r} {k} {v}.
((r -> k -> v -> r) -> r -> Map k v -> r)
-> (r -> k -> v -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((r -> k -> v -> r) -> r ->       Map k v -> r)
        -> ((r -> k -> v -> r) -> r -> MonoidMap k v -> r)
    )
    (r -> k -> v -> r) -> r -> Map k v -> r
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey'
{-# INLINE foldlWithKey' #-}

-- | \(O(n)\). A strict version of 'foldrWithKey'.
--
-- Each application of the operator is evaluated before using the result in the
-- next application. This function is strict in the starting value.
--
-- @since 0.0.1.7
--
foldrWithKey' :: (k -> v -> r -> r) -> r -> MonoidMap k v -> r
foldrWithKey' :: forall k v r. (k -> v -> r -> r) -> r -> MonoidMap k v -> r
foldrWithKey' =
    (((k -> v -> r -> r) -> r -> Map k v -> r)
-> (k -> v -> r -> r) -> r -> MonoidMap k v -> r
forall {k} {v} {r}.
((k -> v -> r -> r) -> r -> Map k v -> r)
-> (k -> v -> r -> r) -> r -> MonoidMap k v -> r
forall a b. Coercible a b => a -> b
coerce
        :: ((k -> v -> r -> r) -> r ->       Map k v -> r)
        -> ((k -> v -> r -> r) -> r -> MonoidMap k v -> r)
    )
    (k -> v -> r -> r) -> r -> Map k v -> r
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey'
{-# INLINE foldrWithKey' #-}

-- | \(O(n)\). A strict version of 'foldMapWithKey'.
--
-- Each application of `mappend` is evaluated before using the result in the
-- next application.
--
-- @since 0.0.1.8
--
foldMapWithKey' :: Monoid r => (k -> v -> r) -> MonoidMap k v -> r
foldMapWithKey' :: forall r k v. Monoid r => (k -> v -> r) -> MonoidMap k v -> r
foldMapWithKey' k -> v -> r
f = (r -> k -> v -> r) -> r -> MonoidMap k v -> r
forall r k v. (r -> k -> v -> r) -> r -> MonoidMap k v -> r
foldlWithKey' (\r
r k
k v
v -> r
r r -> r -> r
forall a. Semigroup a => a -> a -> a
<> k -> v -> r
f k
k v
v) r
forall a. Monoid a => a
mempty
{-# INLINE foldMapWithKey' #-}

--------------------------------------------------------------------------------
-- Traversal
--------------------------------------------------------------------------------

-- | \(O(n)\). Traverses over the values of a map using the given function.
--
-- Satisfies the following property:
--
-- @
-- 'traverse' f m '=='
-- 'fmap' 'fromMap' ('Traversable'.'Traversable.traverse' f ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
traverse
    :: Applicative t
    => MonoidNull v2
    => (v1 -> t v2)
    -> MonoidMap k v1
    -> t (MonoidMap k v2)
traverse :: forall (t :: * -> *) v2 v1 k.
(Applicative t, MonoidNull v2) =>
(v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverse v1 -> t v2
f = (k -> v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
forall (t :: * -> *) v2 k v1.
(Applicative t, MonoidNull v2) =>
(k -> v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverseWithKey ((v1 -> t v2) -> k -> v1 -> t v2
forall a b. a -> b -> a
const v1 -> t v2
f)
{-# INLINE traverse #-}

-- | \(O(n)\). Traverses over the keys and values of a map using the given
--   function.
--
-- Satisfies the following property:
--
-- @
-- 'traverseWithKey' f m '=='
-- 'fmap' 'fromMap' ('Map'.'Map.traverseWithKey' f ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
traverseWithKey
    :: Applicative t
    => MonoidNull v2
    => (k -> v1 -> t v2)
    -> MonoidMap k v1
    -> t (MonoidMap k v2)
traverseWithKey :: forall (t :: * -> *) v2 k v1.
(Applicative t, MonoidNull v2) =>
(k -> v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverseWithKey k -> v1 -> t v2
f (MonoidMap Map k (NonNull v1)
m) =
    Map k (NonNull v2) -> MonoidMap k v2
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v2) -> MonoidMap k v2)
-> t (Map k (NonNull v2)) -> t (MonoidMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
    (k -> NonNull v1 -> t (Maybe (NonNull v2)))
-> Map k (NonNull v1) -> t (Map k (NonNull v2))
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey
        (\k
k NonNull v1
v -> v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2)) -> t v2 -> t (Maybe (NonNull v2))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (v1 -> t v2) -> NonNull v1 -> t v2
forall v a. (v -> a) -> NonNull v -> a
applyNonNull (k -> v1 -> t v2
f k
k) NonNull v1
v) Map k (NonNull v1)
m
{-# INLINE traverseWithKey #-}

-- | \(O(n)\). Threads an accumulating argument through the map in ascending
--   order of keys.
--
-- Satisfies the following property:
--
-- @
-- 'mapAccumL' f s m '=='
-- 'fmap' 'fromMap' ('Traversable'.'Traversable.mapAccumL' f s ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
mapAccumL
    :: MonoidNull v2
    => (s -> v1 -> (s, v2))
    -> s
    -> MonoidMap k v1
    -> (s, MonoidMap k v2)
mapAccumL :: forall v2 s v1 k.
MonoidNull v2 =>
(s -> v1 -> (s, v2)) -> s -> MonoidMap k v1 -> (s, MonoidMap k v2)
mapAccumL s -> v1 -> (s, v2)
f s
s MonoidMap k v1
m =
    (((v1 -> StateL s v2) -> MM k v1 -> StateL s (MM k v2))
-> (v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall {v1} {s} {v2} {k}.
((v1 -> StateL s v2) -> MM k v1 -> StateL s (MM k v2))
-> (v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall a b. Coercible a b => a -> b
coerce
        :: ((v1 -> StateL s  v2 ) -> MM k v1 -> StateL s (MM k v2))
        -> ((v1 -> s ->  (s, v2)) -> MM k v1 -> s ->  (s, MM k v2))
    )
    (v1 -> StateL s v2) -> MonoidMap k v1 -> StateL s (MM k v2)
forall (t :: * -> *) v2 v1 k.
(Applicative t, MonoidNull v2) =>
(v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverse ((s -> v1 -> (s, v2)) -> v1 -> s -> (s, v2)
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> v1 -> (s, v2)
f) MonoidMap k v1
m s
s
{-# INLINE mapAccumL #-}

-- | \(O(n)\). Threads an accumulating argument through the map in descending
--   order of keys.
--
-- Satisfies the following property:
--
-- @
-- 'mapAccumR' f s m '=='
-- 'fmap' 'fromMap' ('Traversable'.'Traversable.mapAccumR' f s ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
mapAccumR
    :: MonoidNull v2
    => (s -> v1 -> (s, v2))
    -> s
    -> MonoidMap k v1
    -> (s, MonoidMap k v2)
mapAccumR :: forall v2 s v1 k.
MonoidNull v2 =>
(s -> v1 -> (s, v2)) -> s -> MonoidMap k v1 -> (s, MonoidMap k v2)
mapAccumR s -> v1 -> (s, v2)
f s
s MonoidMap k v1
m =
    (((v1 -> StateR s v2) -> MM k v1 -> StateR s (MM k v2))
-> (v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall {v1} {s} {v2} {k}.
((v1 -> StateR s v2) -> MM k v1 -> StateR s (MM k v2))
-> (v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall a b. Coercible a b => a -> b
coerce
        :: ((v1 -> StateR s  v2 ) -> MM k v1 -> StateR s (MM k v2))
        -> ((v1 -> s ->  (s, v2)) -> MM k v1 -> s ->  (s, MM k v2))
    )
    (v1 -> StateR s v2) -> MonoidMap k v1 -> StateR s (MM k v2)
forall (t :: * -> *) v2 v1 k.
(Applicative t, MonoidNull v2) =>
(v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverse ((s -> v1 -> (s, v2)) -> v1 -> s -> (s, v2)
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> v1 -> (s, v2)
f) MonoidMap k v1
m s
s
{-# INLINE mapAccumR #-}

-- | \(O(n)\). Threads an accumulating argument through the map in ascending
--   order of keys.
--
-- Satisfies the following property:
--
-- @
-- 'mapAccumLWithKey' f s m '=='
-- 'fmap' 'fromMap' ('Map'.'Map.mapAccumWithKey' f s ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
mapAccumLWithKey
    :: MonoidNull v2
    => (s -> k -> v1 -> (s, v2))
    -> s
    -> MonoidMap k v1
    -> (s, MonoidMap k v2)
mapAccumLWithKey :: forall v2 s k v1.
MonoidNull v2 =>
(s -> k -> v1 -> (s, v2))
-> s -> MonoidMap k v1 -> (s, MonoidMap k v2)
mapAccumLWithKey s -> k -> v1 -> (s, v2)
f s
s0 MonoidMap k v1
m =
    (((k -> v1 -> StateL s v2) -> MM k v1 -> StateL s (MM k v2))
-> (k -> v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall {k} {v1} {s} {v2}.
((k -> v1 -> StateL s v2) -> MM k v1 -> StateL s (MM k v2))
-> (k -> v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall a b. Coercible a b => a -> b
coerce
        :: ((k -> v1 -> StateL s  v2 ) -> MM k v1 -> StateL s (MM k v2))
        -> ((k -> v1 -> s ->  (s, v2)) -> MM k v1 -> s ->  (s, MM k v2))
    )
    (k -> v1 -> StateL s v2) -> MonoidMap k v1 -> StateL s (MM k v2)
forall (t :: * -> *) v2 k v1.
(Applicative t, MonoidNull v2) =>
(k -> v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverseWithKey (\k
k v1
v1 s
s -> s -> k -> v1 -> (s, v2)
f s
s k
k v1
v1) MonoidMap k v1
m s
s0
{-# INLINE mapAccumLWithKey #-}

-- | \(O(n)\). Threads an accumulating argument through the map in descending
--   order of keys.
--
-- Satisfies the following property:
--
-- @
-- 'mapAccumRWithKey' f s m '=='
-- 'fmap' 'fromMap' ('Map'.'Map.mapAccumRWithKey' f s ('toMap' m))
-- @
--
-- @since 0.0.1.9
--
mapAccumRWithKey
    :: MonoidNull v2
    => (s -> k -> v1 -> (s, v2))
    -> s
    -> MonoidMap k v1
    -> (s, MonoidMap k v2)
mapAccumRWithKey :: forall v2 s k v1.
MonoidNull v2 =>
(s -> k -> v1 -> (s, v2))
-> s -> MonoidMap k v1 -> (s, MonoidMap k v2)
mapAccumRWithKey s -> k -> v1 -> (s, v2)
f s
s0 MonoidMap k v1
m =
    (((k -> v1 -> StateR s v2) -> MM k v1 -> StateR s (MM k v2))
-> (k -> v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall {k} {v1} {s} {v2}.
((k -> v1 -> StateR s v2) -> MM k v1 -> StateR s (MM k v2))
-> (k -> v1 -> s -> (s, v2)) -> MM k v1 -> s -> (s, MM k v2)
forall a b. Coercible a b => a -> b
coerce
        :: ((k -> v1 -> StateR s  v2 ) -> MM k v1 -> StateR s (MM k v2))
        -> ((k -> v1 -> s ->  (s, v2)) -> MM k v1 -> s ->  (s, MM k v2))
    )
    (k -> v1 -> StateR s v2) -> MonoidMap k v1 -> StateR s (MM k v2)
forall (t :: * -> *) v2 k v1.
(Applicative t, MonoidNull v2) =>
(k -> v1 -> t v2) -> MonoidMap k v1 -> t (MonoidMap k v2)
traverseWithKey (\k
k v1
v1 s
s -> s -> k -> v1 -> (s, v2)
f s
s k
k v1
v1) MonoidMap k v1
m s
s0
{-# INLINE mapAccumRWithKey #-}

--------------------------------------------------------------------------------
-- Comparison
--------------------------------------------------------------------------------

-- | Indicates whether or not the first map is a /submap/ of the second.
--
-- Map __@m1@__ is a submap of map __@m2@__ if (and only if) __@m1@__ can be
-- subtracted from __@m2@__ with the 'minusMaybe' operation:
--
-- @
-- m1 '`isSubmapOf`' m2 '==' 'isJust' (m2 '`minusMaybe`' m1)
-- @
--
-- Equivalently, map __@m1@__ is a submap of map __@m2@__ if (and only if) for
-- all possible keys __@k@__, the value for __@k@__ in __@m1@__ can be
-- subtracted from the value for __@k@__ in __@m2@__ with the '(</>)' operator:
--
-- @
-- m1 '`isSubmapOf`' m2 '==' (∀ k. 'isJust' ('get' k m2 '</>' 'get' k m1))
-- @
--
isSubmapOf
    :: (Ord k, Monoid v, Reductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Bool
isSubmapOf :: forall k v.
(Ord k, Monoid v, Reductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
isSubmapOf = (v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool
forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
isSubmapOfBy ((v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool)
-> (v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool
forall a b. (a -> b) -> a -> b
$ \v
v1 v
v2 -> Maybe v -> Bool
forall a. Maybe a -> Bool
isJust (v
v2 v -> v -> Maybe v
forall m. Reductive m => m -> m -> Maybe m
</> v
v1)
{-# INLINE isSubmapOf #-}

-- | Indicates whether or not the first map is a /submap/ of the second, using
--   the given function to compare values for matching keys.
--
-- Satisfies the following property:
--
-- @
-- 'isSubmapOfBy' f m1 m2 '=='
--     'all' (\\k -> f ('get' k m1) ('get' k m2)) ('nonNullKeys' m1)
-- @
--
-- === Conditional totality
--
-- /If/ the given comparison function __@f@__ /always/ evaluates to 'True'
-- when its first argument is 'mempty':
--
-- @
-- ∀ v. f 'mempty' v
-- @
--
-- /Then/ the following property holds:
--
-- @
-- 'isSubmapOfBy' f m1 m2 '==' (∀ k. f ('get' k m1) ('get' k m2))
-- @
--
isSubmapOfBy
    :: (Ord k, Monoid v1, Monoid v2)
    => (v1 -> v2 -> Bool)
    -- ^ Function with which to compare values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> Bool
isSubmapOfBy :: forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
isSubmapOfBy v1 -> v2 -> Bool
leq MonoidMap k v1
m1 MonoidMap k v2
m2 =
    (k -> Bool) -> Set k -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all
        (\k
k -> k -> MonoidMap k v1 -> v1
forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
get k
k MonoidMap k v1
m1 v1 -> v2 -> Bool
`leq` k -> MonoidMap k v2 -> v2
forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
get k
k MonoidMap k v2
m2)
        (MonoidMap k v1 -> Set k
forall k v. MonoidMap k v -> Set k
nonNullKeys MonoidMap k v1
m1)
{-# INLINE isSubmapOfBy #-}

-- | Indicates whether or not a pair of maps are /disjoint/.
--
-- Maps __@m1@__ and __@m2@__ are disjoint if (and only if) their intersection
-- is empty:
--
-- @
-- 'disjoint' m1 m2 '==' ('intersection' m1 m2 '==' 'mempty')
-- @
--
-- Equivalently, maps __@m1@__ and __@m2@__ are disjoint if (and only if) for
-- all possible keys __@k@__, the values for __@k@__ in __@m1@__ and __@m2@__
-- have a 'C.gcd' that is 'C.null':
--
-- @
-- 'disjoint' m1 m2 '==' (∀ k. 'C.null' ('C.gcd' ('get' k m1) ('get' k m2)))
-- @
--
disjoint
    :: (Ord k, GCDMonoid v, MonoidNull v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Bool
disjoint :: forall k v.
(Ord k, GCDMonoid v, MonoidNull v) =>
MonoidMap k v -> MonoidMap k v -> Bool
disjoint = (v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool
forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
disjointBy (\v
v1 v
v2 -> v -> Bool
forall m. MonoidNull m => m -> Bool
C.null (v -> v -> v
forall m. GCDMonoid m => m -> m -> m
C.gcd v
v1 v
v2))
{-# INLINE disjoint #-}

-- | Indicates whether or not a pair of maps are /disjoint/ using the given
--   indicator function to test pairs of values for matching keys.
--
-- Satisfies the following property:
--
-- @
-- 'disjointBy' f m1 m2 '=='
--     'all'
--         (\\k -> f ('get' k m1) ('get' k m2))
--         ('Set.intersection' ('nonNullKeys' m1) ('nonNullKeys' m2))
-- @
--
-- === Conditional totality
--
-- /If/ the given indicator function __@f@__ /always/ evaluates to 'True'
-- when /either/ or /both/ of its arguments are 'mempty':
--
-- @
-- ∀ v. (f v 'mempty') '&&' (f 'mempty' v)
-- @
--
-- /Then/ the following property holds:
--
-- @
-- 'disjointBy' f m1 m2 '==' (∀ k. f ('get' k m1) ('get' k m2))
-- @
--
disjointBy
    :: (Ord k, Monoid v1, Monoid v2)
    => (v1 -> v2 -> Bool)
    -- ^ Function with which to test pairs of values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> Bool
disjointBy :: forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
disjointBy v1 -> v2 -> Bool
f MonoidMap k v1
m1 MonoidMap k v2
m2 =
    (k -> Bool) -> Set k -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all
        (\k
k -> v1 -> v2 -> Bool
f (k -> MonoidMap k v1 -> v1
forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
get k
k MonoidMap k v1
m1) (k -> MonoidMap k v2 -> v2
forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
get k
k MonoidMap k v2
m2))
        (Set k -> Set k -> Set k
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection (MonoidMap k v1 -> Set k
forall k v. MonoidMap k v -> Set k
nonNullKeys MonoidMap k v1
m1) (MonoidMap k v2 -> Set k
forall k v. MonoidMap k v -> Set k
nonNullKeys MonoidMap k v2
m2))
{-# INLINE disjointBy #-}

--------------------------------------------------------------------------------
-- Association
--------------------------------------------------------------------------------

-- | Appends a pair of maps together.
--
-- Uses the 'Semigroup' operator '(<>)' to append each value in the first map
-- to its matching value in the second map.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('append' m1 m2) '==' 'get' k m1 '<>' 'get' k m2
-- @
--
-- This function provides the definition of '(<>)' for the 'MonoidMap' instance
-- of 'Semigroup'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1, "abc"), (2, "ij" ), (3, "p"  )            ]
-- >>> m2 = 'fromList' [            (2, "  k"), (3,  "qr"), (4, "xyz")]
-- >>> m3 = 'fromList' [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]
-- @
-- @
-- >>> 'append' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 4), ("b", 2), ("c", 1)          ]
-- >>> m2 = 'fromList' [          ("b", 1), ("c", 2), ("d", 4)]
-- >>> m3 = 'fromList' [("a", 4), ("b", 3), ("c", 3), ("d", 4)]
-- @
-- @
-- >>> 'append' m1 m2 '==' m3
-- 'True'
-- @
--
append
    :: (Ord k, MonoidNull v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
append :: forall k v.
(Ord k, MonoidNull v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
append = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- v <> mempty ≡ v

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- mempty <> v ≡ v

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall a. Semigroup a => a -> a -> a
(<>)
    }
{-# INLINE append #-}

--------------------------------------------------------------------------------
-- Prefixes and suffixes
--------------------------------------------------------------------------------

-- | Indicates whether or not the first map is a /prefix/ of the second.
--
-- 'MonoidMap' __@m1@__ is a /prefix/ of 'MonoidMap' __@m2@__ if (and only if)
-- for all possible keys __@k@__, the value for __@k@__ in __@m1@__ is a
-- /prefix/ of the value for __@k@__ in __@m2@__:
--
-- @
-- m1 '`isPrefixOf`' m2 '==' (∀ k. 'get' k m1 '`C.isPrefixOf`' 'get' k m2)
-- @
--
-- This function provides the definition of 'C.isPrefixOf' for the 'MonoidMap'
-- instance of 'LeftReductive'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1, "a"  ), (2, "p"  ), (3, "x"  )]
-- >>> m2 = 'fromList' [(1, "abc"), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isPrefixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [            (2, "p"  )            ]
-- >>> m2 = 'fromList' [(1, "abc"), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isPrefixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [(1, "abc"), (2, "p"  ), (3, "x"  )]
-- >>> m2 = 'fromList' [(1, "a"  ), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isPrefixOf`' m2
-- 'False'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 1), ("b", 1), ("c", 1)]
-- >>> m2 = 'fromList' [("a", 2), ("b", 4), ("c", 8)]
-- >>> m1 '`isPrefixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [          ("b", 1)          ]
-- >>> m2 = 'fromList' [("a", 2), ("b", 4), ("c", 8)]
-- >>> m1 '`isPrefixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 1), ("c", 1)]
-- >>> m2 = 'fromList' [("a", 1), ("b", 4), ("c", 8)]
-- >>> m1 '`isPrefixOf`' m2
-- 'False'
-- @
--
isPrefixOf
    :: (Ord k, Monoid v, LeftReductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Bool
isPrefixOf :: forall k v.
(Ord k, Monoid v, LeftReductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
isPrefixOf = (v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool
forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
isSubmapOfBy v -> v -> Bool
forall m. LeftReductive m => m -> m -> Bool
C.isPrefixOf
    -- Note that in practice, it's sufficient to check the following property:
    --
    -- @
    -- m1 '`isPrefixOf`' m2 '=='
    --     'all'
    --         (\\k -> 'get' k m1 '`C.isPrefixOf`' 'get' k m2)
    --         ('nonNullKeys' m1)
    -- @
    --
    -- ==== Justification
    --
    -- According to the laws for 'LeftReductive':
    --
    -- @
    -- ∀ a b. b '`C.isPrefixOf`' (b '<>' a)
    -- @
    --
    -- Substituting 'mempty' for @b@:
    --
    -- @
    -- ∀ a. 'mempty' '`C.isPrefixOf`' ('mempty' '<>' a)
    -- @
    --
    -- According to the left identity law for 'Monoid':
    --
    -- @
    -- ∀ a. 'mempty' '<>' a '==' a
    -- @
    --
    -- We can therefore assert that:
    --
    -- @
    -- ∀ a. 'mempty' '`C.isPrefixOf`' a
    -- @
    --
    -- Since 'mempty' is /always/ a valid prefix, we only need to consider
    -- values in 'm1' that are /not/ 'mempty'.
    --
    -- The 'nonNullKeys' function, when applied to 'm1', gives us /precisely/
    -- the set of keys that are not associated with 'mempty' in 'm1':
    --
    -- @
    -- (k '`Data.Set.member`' 'nonNullKeys' m1) '==' ('get' k m1 '/=' 'mempty')
    -- @
    --
{-# INLINE isPrefixOf #-}

-- | Indicates whether or not the first map is a /suffix/ of the second.
--
-- 'MonoidMap' __@m1@__ is a /suffix/ of 'MonoidMap' __@m2@__ if (and only if)
-- for all possible keys __@k@__, the value for __@k@__ in __@m1@__ is a
-- /suffix/ of the value for __@k@__ in __@m2@__:
--
-- @
-- m1 '`isSuffixOf`' m2 '==' (∀ k. 'get' k m1 '`C.isSuffixOf`' 'get' k m2)
-- @
--
-- This function provides the definition of 'C.isSuffixOf' for the 'MonoidMap'
-- instance of 'RightReductive'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1,   "c"), (2,   "r"), (3,   "z")]
-- >>> m2 = 'fromList' [(1, "abc"), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isSuffixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [            (2,   "r")            ]
-- >>> m2 = 'fromList' [(1, "abc"), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isSuffixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [(1, "abc"), (2,   "r"), (3,   "z")]
-- >>> m2 = 'fromList' [(1,   "c"), (2, "pqr"), (3, "xyz")]
-- >>> m1 '`isSuffixOf`' m2
-- 'False'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 1), ("b", 1), ("c", 1)]
-- >>> m2 = 'fromList' [("a", 2), ("b", 4), ("c", 8)]
-- >>> m1 '`isSuffixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [          ("b", 1)          ]
-- >>> m2 = 'fromList' [("a", 2), ("b", 4), ("c", 8)]
-- >>> m1 '`isSuffixOf`' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 1), ("c", 1)]
-- >>> m2 = 'fromList' [("a", 1), ("b", 4), ("c", 8)]
-- >>> m1 '`isSuffixOf`' m2
-- 'False'
-- @
--
isSuffixOf
    :: (Ord k, Monoid v, RightReductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Bool
isSuffixOf :: forall k v.
(Ord k, Monoid v, RightReductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
isSuffixOf = (v -> v -> Bool) -> MonoidMap k v -> MonoidMap k v -> Bool
forall k v1 v2.
(Ord k, Monoid v1, Monoid v2) =>
(v1 -> v2 -> Bool) -> MonoidMap k v1 -> MonoidMap k v2 -> Bool
isSubmapOfBy v -> v -> Bool
forall m. RightReductive m => m -> m -> Bool
C.isSuffixOf
    -- Note that in practice, it's sufficient to check the following property:
    --
    -- @
    -- m1 '`isSuffixOf`' m2 '=='
    --     'all'
    --         (\\k -> 'get' k m1 '`C.isSuffixOf`' 'get' k m2)
    --         ('nonNullKeys' m1)
    -- @
    --
    -- ==== Justification
    --
    -- According to the laws for 'RightReductive':
    --
    -- @
    -- ∀ a b. b '`C.isSuffixOf`' (a '<>' b)
    -- @
    --
    -- Substituting 'mempty' for @b@:
    --
    -- @
    -- ∀ a. 'mempty' '`C.isSuffixOf`' (a '<>' 'mempty')
    -- @
    --
    -- According to the right identity law for 'Monoid':
    --
    -- @
    -- ∀ a. a '<>' 'mempty' '==' a
    -- @
    --
    -- We can therefore assert that:
    --
    -- @
    -- ∀ a. 'mempty' '`C.isSuffixOf`' a
    -- @
    --
    -- Since 'mempty' is /always/ a valid suffix, we only need to consider
    -- values in 'm1' that are /not/ 'mempty'.
    --
    -- The 'nonNullKeys' function, when applied to 'm1', gives us /precisely/
    -- the set of keys that are not associated with 'mempty' in 'm1':
    --
    -- @
    -- (k '`Data.Set.member`' 'nonNullKeys' m1) '==' ('get' k m1 '/=' 'mempty')
    -- @
    --
{-# INLINE isSuffixOf #-}

-- | Strips a /prefix/ from a 'MonoidMap'.
--
-- If map __@m1@__ is a /prefix/ of map __@m2@__, then 'stripPrefix' __@m1@__
-- __@m2@__ will produce a /reduced/ map where prefix __@m1@__ is /stripped/
-- from __@m2@__.
--
-- === Properties
--
-- The 'stripPrefix' function, when applied to maps __@m1@__ and __@m2@__,
-- produces a result if (and only if) __@m1@__ is a prefix of __@m2@__:
--
-- @
-- 'isJust' ('stripPrefix' m1 m2) '==' m1 '`isPrefixOf`' m2
-- @
--
-- The value for any key __@k@__ in the result is /identical/ to the result of
-- stripping the value for __@k@__ in map __@m1@__ from the value for __@k@__
-- in map __@m2@__:
--
-- @
-- 'all'
--    (\\r -> 'Just' ('get' k r) '==' 'C.stripPrefix' ('get' k m1) ('get' k m2))
--    ('stripPrefix' m1 m2)
-- @
--
-- If we append prefix __@m1@__ to the /left-hand/ side of the result, we can
-- always recover the original map __@m2@__:
--
-- @
-- 'all'
--    (\\r -> m1 '<>' r '==' m2)
--    ('stripPrefix' m1 m2)
-- @
--
-- This function provides the definition of 'C.stripPrefix' for the 'MonoidMap'
-- instance of 'LeftReductive'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> __m1__ = 'fromList' [(1, ""   ), (2, "i"  ), (3, "pq" ), (4, "xyz")]
-- >>> __m2__ = 'fromList' [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]
-- >>> __m3__ = 'fromList' [(1, "abc"), (2,  "jk"), (3,   "r"), (4,    "")]
-- @
-- @
-- >>> 'stripPrefix' __m1__ __m2__ '==' 'Just' __m3__
-- 'True'
-- @
-- @
-- >>> 'stripPrefix' __m2__ __m1__ '==' 'Nothing'
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> __m1__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> __m2__ = 'fromList' [("a", 3), ("b", 3), ("c", 3), ("d", 3)]
-- >>> __m3__ = 'fromList' [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
-- @
-- @
-- >>> 'stripPrefix' __m1__ __m2__ '==' 'Just' __m3__
-- 'True'
-- @
-- @
-- >>> 'stripPrefix' __m2__ __m1__ '==' 'Nothing'
-- 'True'
-- @
--
stripPrefix
    :: (Ord k, MonoidNull v, LeftReductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Maybe (MonoidMap k v)
stripPrefix :: forall k v.
(Ord k, MonoidNull v, LeftReductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripPrefix = MergeStrategy Maybe k v v v
-> MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA MergeStrategy
    { withNonNullL :: WhenOneSideNull Maybe k v v
withNonNullL =
        (v -> Maybe v) -> WhenOneSideNull Maybe k v v
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA (\v
v -> v -> v -> Maybe v
forall m. LeftReductive m => m -> m -> Maybe m
C.stripPrefix v
v v
forall a. Monoid a => a
mempty)

    , withNonNullR :: WhenOneSideNull Maybe k v v
withNonNullR =
        WhenOneSideNull Maybe k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- stripPrefix mempty a ≡ a

    , withNonNullP :: WhenBothNonNull Maybe k v v v
withNonNullP =
        (v -> v -> Maybe v) -> WhenBothNonNull Maybe k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v -> v -> Maybe v
forall m. LeftReductive m => m -> m -> Maybe m
C.stripPrefix
    }
{-# INLINE stripPrefix #-}

-- | Strips a /suffix/ from a 'MonoidMap'.
--
-- If map __@m1@__ is a /suffix/ of map __@m2@__, then 'stripSuffix' __@m1@__
-- __@m2@__ will produce a /reduced/ map where suffix __@m1@__ is /stripped/
-- from __@m2@__.
--
-- === Properties
--
-- The 'stripSuffix' function, when applied to maps __@m1@__ and __@m2@__,
-- produces a result if (and only if) __@m1@__ is a suffix of __@m2@__:
--
-- @
-- 'isJust' ('stripSuffix' m1 m2) '==' m1 '`isSuffixOf`' m2
-- @
--
-- The value for any key __@k@__ in the result is /identical/ to the result of
-- stripping the value for __@k@__ in map __@m1@__ from the value for __@k@__
-- in map __@m2@__:
--
-- @
-- 'all'
--    (\\r -> 'Just' ('get' k r) '==' 'C.stripSuffix' ('get' k m1) ('get' k m2))
--    ('stripSuffix' m1 m2)
-- @
--
-- If we append suffix __@m1@__ to the /right-hand/ side of the result, we can
-- always recover the original map __@m2@__:
--
-- @
-- 'all'
--    (\\r -> r '<>' m1 '==' m2)
--    ('stripSuffix' m1 m2)
-- @
--
-- This function provides the definition of 'C.stripSuffix' for the 'MonoidMap'
-- instance of 'RightReductive'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> __m1__ = 'fromList' [(1,    ""), (2,   "k"), (3,  "qr"), (4, "xyz")]
-- >>> __m2__ = 'fromList' [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]
-- >>> __m3__ = 'fromList' [(1, "abc"), (2, "ij" ), (3, "p"  ), (4, ""   )]
-- @
-- @
-- >>> 'stripSuffix' __m1__ __m2__ '==' 'Just' __m3__
-- 'True'
-- @
-- @
-- >>> 'stripSuffix' __m2__ __m1__ '==' 'Nothing'
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> __m1__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> __m2__ = 'fromList' [("a", 3), ("b", 3), ("c", 3), ("d", 3)]
-- >>> __m3__ = 'fromList' [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
-- @
-- @
-- >>> 'stripSuffix' __m1__ __m2__ '==' 'Just' __m3__
-- 'True'
-- @
-- @
-- >>> 'stripSuffix' __m2__ __m1__ '==' 'Nothing'
-- 'True'
-- @
--
stripSuffix
    :: (Ord k, MonoidNull v, RightReductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Maybe (MonoidMap k v)
stripSuffix :: forall k v.
(Ord k, MonoidNull v, RightReductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
stripSuffix = MergeStrategy Maybe k v v v
-> MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA MergeStrategy
    { withNonNullL :: WhenOneSideNull Maybe k v v
withNonNullL =
        (v -> Maybe v) -> WhenOneSideNull Maybe k v v
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA (\v
v -> v -> v -> Maybe v
forall m. RightReductive m => m -> m -> Maybe m
C.stripSuffix v
v v
forall a. Monoid a => a
mempty)

    , withNonNullR :: WhenOneSideNull Maybe k v v
withNonNullR =
        WhenOneSideNull Maybe k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- stripSuffix mempty a ≡ a

    , withNonNullP :: WhenBothNonNull Maybe k v v v
withNonNullP =
        (v -> v -> Maybe v) -> WhenBothNonNull Maybe k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v -> v -> Maybe v
forall m. RightReductive m => m -> m -> Maybe m
C.stripSuffix
    }
{-# INLINE stripSuffix #-}

-- | Finds the /greatest common prefix/ of two maps.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('commonPrefix' m1 m2)
--     '==' 'C.commonPrefix' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.commonPrefix' for the
-- 'MonoidMap' instance of 'LeftGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> __m1__ = 'fromList' [(1, "+++"), (2, "b++"), (3, "cc+"), (4, "ddd")]
-- >>> __m2__ = 'fromList' [(1, "---"), (2, "b--"), (3, "cc-"), (4, "ddd")]
-- >>> __m3__ = 'fromList' [(1, ""   ), (2, "b"  ), (3, "cc" ), (4, "ddd")]
-- @
-- @
-- >>> 'commonPrefix' __m1__ __m2__ '==' __m3__
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> __m1__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> __m2__ = 'fromList' [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
-- >>> __m3__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 2)]
-- @
-- @
-- >>> 'commonPrefix' __m1__ __m2__ '==' __m3__
-- 'True'
-- @
--
commonPrefix
    :: (Ord k, MonoidNull v, LeftGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
commonPrefix :: forall k v.
(Ord k, MonoidNull v, LeftGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonPrefix = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- commonPrefix a mempty ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- commonPrefix mempty a ≡ mempty

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. LeftGCDMonoid m => m -> m -> m
C.commonPrefix
    }
{-# INLINE commonPrefix #-}

-- | Finds the /greatest common suffix/ of two maps.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('commonSuffix' m1 m2)
--     '==' 'C.commonSuffix' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.commonSuffix' for the
-- 'MonoidMap' instance of 'RightGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> __m1__ = 'fromList' [(1, "+++"), (2, "++b"), (3, "+cc"), (4, "ddd")]
-- >>> __m2__ = 'fromList' [(1, "---"), (2, "--b"), (3, "-cc"), (4, "ddd")]
-- >>> __m3__ = 'fromList' [(1,    ""), (2,   "b"), (3,  "cc"), (4, "ddd")]
-- @
-- @
-- >>> 'commonSuffix' __m1__ __m2__ '==' __m3__
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> __m1__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> __m2__ = 'fromList' [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
-- >>> __m3__ = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 2)]
-- @
-- @
-- >>> 'commonSuffix' __m1__ __m2__ '==' __m3__
-- 'True'
-- @
--
commonSuffix
    :: (Ord k, MonoidNull v, RightGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
commonSuffix :: forall k v.
(Ord k, MonoidNull v, RightGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
commonSuffix = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- commonSuffix a mempty ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- commonSuffix mempty a ≡ mempty

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. RightGCDMonoid m => m -> m -> m
C.commonSuffix
    }
{-# INLINE commonSuffix #-}

-- | Strips the /greatest common prefix/ from a pair of maps.
--
-- Given two maps __@m1@__ and __@m2@__, 'stripCommonPrefix' produces a
-- tuple __@(p, r1, r2)@__, where:
--
--  - __@p@__ is the /greatest common prefix/ of __@m1@__ and __@m2@__
--  - __@r1@__ is the /remainder/ of stripping prefix __@p@__ from __@m1@__
--  - __@r2@__ is the /remainder/ of stripping prefix __@p@__ from __@m2@__
--
-- The resulting prefix __@p@__ can be appended to the /left-hand/ side of
-- either remainder __@r1@__ or __@r2@__ to /reproduce/ either of the original
-- maps __@m1@__ or __@m2@__ respectively:
--
-- @
-- 'stripCommonPrefix' m1 m2
--    '&' \\(p, r1, _) -> p '<>' r1 '==' m1
-- 'stripCommonPrefix' m1 m2
--    '&' \\(p, _, r2) -> p '<>' r2 '==' m2
-- @
--
-- Prefix __@p@__ is /identical/ to the result of applying 'commonPrefix' to
-- __@m1@__ and __@m2@__:
--
-- @
-- 'stripCommonPrefix' m1 m2
--    '&' \\(p, _, _) -> p '==' 'commonPrefix' m1 m2
-- @
--
-- Remainders __@r1@__ and __@r2@__ are /identical/ to the results of applying
-- 'stripPrefix' to __@p@__ and __@m1@__ or to __@p@__ and __@m2@__
-- respectively:
--
-- @
-- 'stripCommonPrefix' m1 m2
--    '&' \\(p, r1, _) -> 'Just' r1 '==' 'stripPrefix' p m1
-- 'stripCommonPrefix' m1 m2
--    '&' \\(p, _, r2) -> 'Just' r2 '==' 'stripPrefix' p m2
-- @
--
-- This function provides the definition of 'C.stripCommonPrefix' for the
-- 'MonoidMap' instance of 'LeftGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1, "+++"), (2, "a++"), (3, "aa+"), (4, "aaa")]
-- >>> m2 = 'fromList' [(1, "---"), (2, "a--"), (3, "aa-"), (4, "aaa")]
-- @
-- @
-- >>> p  = 'fromList' [(1, ""   ), (2, "a"  ), (3, "aa" ), (4, "aaa")]
-- >>> r1 = 'fromList' [(1, "+++"), (2,  "++"), (3,   "+"), (4,    "")]
-- >>> r2 = 'fromList' [(1, "---"), (2,  "--"), (3,   "-"), (4,    "")]
-- @
-- @
-- >>> 'stripCommonPrefix' m1 m2 '==' (p, r1, r2)
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
-- @
-- @
-- >>> p  = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]
-- >>> r1 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]
-- >>> r2 = 'fromList' [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]
-- @
-- @
-- >>> 'stripCommonPrefix' m1 m2 '==' (p, r1, r2)
-- 'True'
-- @
--
stripCommonPrefix
    :: (Ord k, MonoidNull v, LeftGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripCommonPrefix :: forall k v.
(Ord k, MonoidNull v, LeftGCDMonoid v) =>
MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripCommonPrefix = MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
forall m. LeftGCDMonoid m => m -> m -> (m, m, m)
C.stripCommonPrefix

-- | Strips the /greatest common suffix/ from a pair of maps.
--
-- Given two maps __@m1@__ and __@m2@__, 'stripCommonSuffix' produces a
-- tuple __@(r1, r2, s)@__, where:
--
--  - __@s@__ is the /greatest common suffix/ of __@m1@__ and __@m2@__
--  - __@r1@__ is the /remainder/ of stripping suffix __@s@__ from __@m1@__
--  - __@r2@__ is the /remainder/ of stripping suffix __@s@__ from __@m2@__
--
-- The resulting suffix __@s@__ can be appended to the /right-hand/ side of
-- either remainder __@r1@__ or __@r2@__ to /reproduce/ either of the original
-- maps __@m1@__ or __@m2@__ respectively:
--
-- @
-- 'stripCommonSuffix' m1 m2
--    '&' \\(r1, _, s) -> r1 '<>' s '==' m1
-- 'stripCommonSuffix' m1 m2
--    '&' \\(_, r2, s) -> r2 '<>' s '==' m2
-- @
--
-- Suffix __@s@__ is /identical/ to the result of applying 'commonSuffix' to
-- __@m1@__ and __@m2@__:
--
-- @
-- 'stripCommonSuffix' m1 m2
--    '&' \\(_, _, s) -> s '==' 'commonSuffix' m1 m2
-- @
--
-- Remainders __@r1@__ and __@r2@__ are /identical/ to the results of applying
-- 'stripSuffix' to __@s@__ and __@m1@__ or to __@s@__ and __@m2@__
-- respectively:
--
-- @
-- 'stripCommonSuffix' m1 m2
--    '&' \\(r1, _, s) -> 'Just' r1 '==' 'stripSuffix' s m1
-- 'stripCommonSuffix' m1 m2
--    '&' \\(_, r2, s) -> 'Just' r2 '==' 'stripSuffix' s m2
-- @
--
-- This function provides the definition of 'C.stripCommonSuffix' for the
-- 'MonoidMap' instance of 'RightGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1, "+++"), (2, "++a"), (3, "+aa"), (4, "aaa")]
-- >>> m2 = 'fromList' [(1, "---"), (2, "--a"), (3, "-aa"), (4, "aaa")]
-- @
-- @
-- >>> r1 = 'fromList' [(1, "+++"), (2, "++" ), (3, "+"  ), (4, ""   )]
-- >>> r2 = 'fromList' [(1, "---"), (2, "--" ), (3, "-"  ), (4, ""   )]
-- >>> s  = 'fromList' [(1,    ""), (2,   "a"), (3,  "aa"), (4, "aaa")]
-- @
-- @
-- >>> 'stripCommonSuffix' m1 m2 '==' (r1, r2, s)
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
-- @
-- @
-- >>> r1 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]
-- >>> r2 = 'fromList' [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]
-- >>> s  = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]
-- @
-- @
-- >>> 'stripCommonSuffix' m1 m2 '==' (r1, r2, s)
-- 'True'
-- @
--
stripCommonSuffix
    :: (Ord k, MonoidNull v, RightGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripCommonSuffix :: forall k v.
(Ord k, MonoidNull v, RightGCDMonoid v) =>
MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripCommonSuffix = MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
C.stripCommonSuffix

--------------------------------------------------------------------------------
-- Overlap
--------------------------------------------------------------------------------

-- | Finds the /greatest overlap/ of two maps.
--
-- The /greatest overlap/ __@o@__ of maps __@m1@__ and __@m2@__ is the /unique/
-- greatest map that is both a /suffix/ of __@m1@__ and a /prefix/ of __@m2@__:
--
-- @
-- m1 '==' r1 '<>' o \  \
-- m2 '=='    \  \ o '<>' r2
-- @
--
-- Where:
--
--  - __@r1@__ is the /remainder/ obtained by stripping /suffix overlap/
--    __@o@__ from __@m1@__.
--
--      (see 'stripSuffixOverlap')
--
--  - __@r2@__ is the /remainder/ obtained by stripping /prefix overlap/
--    __@o@__ from __@m2@__.
--
--      (see 'stripPrefixOverlap')
--
-- This function satisfies the following property:
--
-- @
-- 'get' k ('overlap' m1 m2) '==' 'C.overlap' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.overlap' for the 'MonoidMap'
-- instance of 'OverlappingGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1,"abc"   ), (2,"abcd"  ), (3,"abcde "), (4,"abcdef")]
-- >>> m2 = 'fromList' [(1,   "def"), (2,  "cdef"), (3," bcdef"), (4,"abcdef")]
-- >>> m3 = 'fromList' [(1,   ""   ), (2,  "cd"  ), (3," bcde" ), (4,"abcdef")]
-- @
-- @
-- >>> 'overlap' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]
-- @
-- @
-- >>> 'overlap' m1 m2 '==' m3
-- 'True'
-- @
--
overlap
    :: (Ord k, MonoidNull v, OverlappingGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
overlap :: forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
overlap = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- overlap a mempty ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- overlap mempty a ≡ mempty

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. OverlappingGCDMonoid m => m -> m -> m
C.overlap
    }
{-# INLINE overlap #-}

-- | /Strips/ from the second map its /greatest prefix overlap/ with suffixes
--   of the first map.
--
-- Evaluating 'stripPrefixOverlap' __@m1@__ __@m2@__ produces the /remainder/
-- __@r2@__:
--
-- @
-- m1 '==' r1 '<>' o \  \
-- m2 '=='    \  \ o '<>' r2
-- @
--
-- Where __@o@__ is the /greatest overlap/ of maps __@m1@__ and __@m2@__: the
-- /unique/ greatest map that is both a /suffix/ of __@m1@__ and a /prefix/ of
-- __@m2@__.
--
-- This function satisfies the following property:
--
-- @
-- 'get' k ('stripPrefixOverlap' m1 m2)
--     '==' 'C.stripPrefixOverlap' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.stripPrefixOverlap' for the
-- 'MonoidMap' instance of 'OverlappingGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1,"abc"   ), (2,"abcd"  ), (3,"abcde" ), (4,"abcdef")]
-- >>> m2 = 'fromList' [(1,   "def"), (2,  "cdef"), (3, "bcdef"), (4,"abcdef")]
-- >>> m3 = 'fromList' [(1,   "def"), (2,    "ef"), (3,     "f"), (4,      "")]
-- @
-- @
-- >>> 'stripPrefixOverlap' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
-- >>> m3 = 'fromList' [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]
-- @
-- @
-- >>> 'stripPrefixOverlap' m1 m2 '==' m3
-- 'True'
-- @
--
stripPrefixOverlap
    :: (Ord k, MonoidNull v, OverlappingGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
stripPrefixOverlap :: forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripPrefixOverlap = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- overlap a b      <> stripPrefixOverlap a b      ≡ b
        -- overlap a mempty <> stripPrefixOverlap a mempty ≡ mempty
        --           mempty <> stripPrefixOverlap a mempty ≡ mempty
        --                     stripPrefixOverlap a mempty ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- overlap a      b <> stripPrefixOverlap a      b ≡ b
        -- overlap mempty b <> stripPrefixOverlap mempty b ≡ b
        --         mempty   <> stripPrefixOverlap mempty b ≡ b
        --                     stripPrefixOverlap mempty b ≡ b

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. OverlappingGCDMonoid m => m -> m -> m
C.stripPrefixOverlap
    }
{-# INLINE stripPrefixOverlap #-}

-- | /Strips/ from the second map its /greatest suffix overlap/ with prefixes
--   of the first map.
--
-- Evaluating 'stripSuffixOverlap' __@m2@__ __@m1@__ produces the /remainder/
-- __@r1@__:
--
-- @
-- m1 '==' r1 '<>' o \  \
-- m2 '=='    \  \ o '<>' r2
-- @
--
-- Where __@o@__ is the /greatest overlap/ of maps __@m1@__ and __@m2@__: the
-- /unique/ greatest map that is both a /suffix/ of __@m1@__ and a /prefix/ of
-- __@m2@__.
--
-- This function satisfies the following property:
--
-- @
-- 'get' k ('stripSuffixOverlap' m2 m1)
--     '==' 'C.stripSuffixOverlap' ('get' k m2) ('get' k m1)
-- @
--
-- This function provides the definition of 'C.stripSuffixOverlap' for the
-- 'MonoidMap' instance of 'OverlappingGCDMonoid'.
--
-- === __Examples__
--
-- With 'String' values:
--
-- @
-- >>> m1 = 'fromList' [(1,"abc"   ), (2,"abcd"  ), (3,"abcde" ), (4,"abcdef")]
-- >>> m2 = 'fromList' [(1,   "def"), (2,  "cdef"), (3, "bcdef"), (4,"abcdef")]
-- >>> m3 = 'fromList' [(1,"abc"   ), (2,"ab"    ), (3,"a"     ), (4,""      )]
-- @
-- @
-- >>> 'stripSuffixOverlap' m2 m1 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]
-- @
-- @
-- >>> 'stripSuffixOverlap' m2 m1 '==' m3
-- 'True'
-- @
--
stripSuffixOverlap
    :: (Ord k, MonoidNull v, OverlappingGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
stripSuffixOverlap :: forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripSuffixOverlap = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- stripSuffixOverlap b a      <> overlap a      b ≡ a
        -- stripSuffixOverlap b mempty <> overlap mempty b ≡ mempty
        -- stripSuffixOverlap b mempty <>         mempty   ≡ mempty
        -- stripSuffixOverlap b mempty                     ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- stripSuffixOverlap b      a <> overlap a b      ≡ a
        -- stripSuffixOverlap mempty a <> overlap a mempty ≡ a
        -- stripSuffixOverlap mempty a <>           mempty ≡ a
        -- stripSuffixOverlap mempty a                     ≡ a

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. OverlappingGCDMonoid m => m -> m -> m
C.stripSuffixOverlap
    }
{-# INLINE stripSuffixOverlap #-}

-- | Finds the /greatest overlap/ of two maps and /strips/ it from both maps.
--
-- Evaluating 'stripOverlap' __@m1@__ __@m2@__ produces the tuple
-- __@(r1, o, r2)@__, where:
--
-- @
-- m1 '==' r1 '<>' o \  \
-- m2 '=='    \  \ o '<>' r2
-- @
--
-- Where:
--
--  - __@o@__ is the /greatest overlap/ of maps __@m1@__ and __@m2@__: the
--    /unique/ greatest map that is both a /suffix/ of __@m1@__ and a /prefix/
--    of __@m2@__.
--
--      (see 'overlap')
--
--  - __@r1@__ is the /remainder/ obtained by stripping /suffix overlap/
--    __@o@__ from __@m1@__.
--
--      (see 'stripSuffixOverlap')
--
--  - __@r2@__ is the /remainder/ obtained by stripping /prefix overlap/
--    __@o@__ from __@m2@__.
--
--      (see 'stripPrefixOverlap')
--
-- This function satisfies the following property:
--
-- @
-- 'stripOverlap' m1 m2 '=='
--    ( 'stripSuffixOverlap' m2 m1
--    , 'overlap' m1 m2
--    , 'stripPrefixOverlap' m1 m2
--    )
-- @
--
-- This function provides the definition of 'C.stripOverlap' for the
-- 'MonoidMap' instance of 'OverlappingGCDMonoid'.
--
stripOverlap
    :: (Ord k, MonoidNull v, OverlappingGCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripOverlap :: forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v
-> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)
stripOverlap MonoidMap k v
m1 MonoidMap k v
m2 =
    ( MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripSuffixOverlap MonoidMap k v
m2 MonoidMap k v
m1
    , MonoidMap k v
m1 MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
`overlap` MonoidMap k v
m2
    , MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v.
(Ord k, MonoidNull v, OverlappingGCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
stripPrefixOverlap MonoidMap k v
m1 MonoidMap k v
m2
    )

--------------------------------------------------------------------------------
-- Intersection
--------------------------------------------------------------------------------

-- | Finds the /intersection/ of two maps.
--
-- The intersection of maps __@m1@__ and __@m2@__ is the greatest single map
-- __@m@__ that is a /submap/ of both __@m1@__ /and/ __@m2@__:
--
-- @
-- 'intersection' m1 m2 '`isSubmapOf`' m1
-- 'intersection' m1 m2 '`isSubmapOf`' m2
-- @
--
-- The intersection is /unique/:
--
-- @
-- 'and'
--     [ 'intersection' m1 m2 '`isSubmapOf`' m
--     , \            \       \            \ m '`isSubmapOf`' m1
--     , \            \       \            \ m '`isSubmapOf`' m2
--     ]
-- ==>
--     (m '==' 'intersection' m1 m2)
-- @
--
-- The following property holds for all possible keys __@k@__:
--
-- @
-- 'get' k ('intersection' m1 m2) '==' 'C.gcd' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.gcd' for the 'MonoidMap'
-- instance of 'GCDMonoid'.
--
-- === __Examples__
--
-- With 'Data.Monoid.Product' 'Numeric.Natural.Natural' values, this function
-- computes the /greatest common divisor/ of each pair of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b",  6), ("c", 15), ("d", 35)]
-- >>> m2 = 'fromList' [("a", 6), ("b", 15), ("c", 35), ("d", 77)]
-- >>> m3 = 'fromList' [("a", 2), ("b",  3), ("c",  5), ("d",  7)]
-- @
-- @
-- >>> 'intersection' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values, this function
-- computes the /minimum/ of each pair of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 1), ("c", 1), ("d", 0)]
-- @
-- @
-- >>> 'intersection' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Set' 'Numeric.Natural.Natural' values, this function computes the
-- /set/ /intersection/ of each pair of matching values:
--
-- @
-- f xs = 'fromList' ('Set.fromList' '<$>' xs)
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2  ]), ("c", [0,1,2    ])]
-- >>> m2 = f [("a", [0,1,2]), ("b", [  1,2,3]), ("c", [    2,3,4])]
-- >>> m3 = f [("a", [0,1,2]), ("b", [  1,2  ]), ("c", [    2    ])]
-- @
-- @
-- >>> 'intersection' m1 m2 '==' m3
-- 'True'
-- @
--
intersection
    :: (Ord k, MonoidNull v, GCDMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
intersection :: forall k v.
(Ord k, MonoidNull v, GCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
intersection = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- gcd a mempty ≡ mempty

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- gcd mempty b ≡ mempty

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. GCDMonoid m => m -> m -> m
C.gcd
    }
{-# INLINE intersection #-}

--------------------------------------------------------------------------------
-- Union
--------------------------------------------------------------------------------

-- | Finds the /union/ of two maps.
--
-- The union of maps __@m1@__ and __@m2@__ is the smallest single map __@m@__
-- that includes both __@m1@__ /and/ __@m2@__ as /submaps/:
--
-- @
-- m1 '`isSubmapOf`' 'union' m1 m2
-- m2 '`isSubmapOf`' 'union' m1 m2
-- @
--
-- The union is /unique/:
--
-- @
-- 'and'
--     [ m1 '`isSubmapOf`' m
--     , m2 '`isSubmapOf`' m
--     ,    \            \ m '`isSubmapOf`' 'union' m1 m2
--     ]
-- ==>
--     (m '==' 'union' m1 m2)
-- @
--
-- The following property holds for all possible keys __@k@__:
--
-- @
-- 'get' k ('union' m1 m2) '==' 'C.lcm' ('get' k m1) ('get' k m2)
-- @
--
-- This function provides the definition of 'C.lcm' for the 'MonoidMap'
-- instance of 'LCMMonoid'.
--
-- === __Examples__
--
-- With 'Data.Monoid.Product' 'Numeric.Natural.Natural' values, this function
-- computes the /least common multiple/ of each pair of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b",  6), ("c",  15), ("d",  35)]
-- >>> m2 = 'fromList' [("a", 6), ("b", 15), ("c",  35), ("d",  77)]
-- >>> m3 = 'fromList' [("a", 6), ("b", 30), ("c", 105), ("d", 385)]
-- @
-- @
-- >>> 'union' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values, this function
-- computes the /maximum/ of each pair of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
-- >>> m3 = 'fromList' [("a", 3), ("b", 2), ("c", 2), ("d", 3)]
-- @
-- @
-- >>> 'union' m1 m2 '==' m3
-- 'True'
-- @
--
-- With 'Set' 'Numeric.Natural.Natural' values, this function computes the
-- /set/ /union/ of each pair of matching values:
--
-- @
-- f xs = 'fromList' ('Set.fromList' '<$>' xs)
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2  ]), ("c", [0,1,2    ])]
-- >>> m2 = f [("a", [0,1,2]), ("b", [  1,2,3]), ("c", [    2,3,4])]
-- >>> m3 = f [("a", [0,1,2]), ("b", [0,1,2,3]), ("c", [0,1,2,3,4])]
-- @
-- @
-- >>> 'union' m1 m2 '==' m3
-- 'True'
-- @
--
union
    :: (Ord k, MonoidNull v, LCMMonoid v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
union :: forall k v.
(Ord k, MonoidNull v, LCMMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
union = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- lcm a mempty ≡ a

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- lcm mempty a ≡ a

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. LCMMonoid m => m -> m -> m
C.lcm
    }
{-# INLINE union #-}

--------------------------------------------------------------------------------
-- Subtraction
--------------------------------------------------------------------------------

-- | Performs /group subtraction/ of the second map from the first.
--
-- Uses the 'Group' subtraction operator '(C.~~)' to subtract each value in the
-- second map from its matching value in the first map.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k (m1 '`minus`' m2) '==' 'get' k m1 'C.~~' 'get' k m2
-- @
--
-- This function provides the definition of '(C.~~)' for the 'MonoidMap'
-- instance of 'Group'.
--
-- === __Examples__
--
-- With 'Data.Monoid.Sum' 'Integer' values, this function performs normal
-- integer subtraction of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", (-1)), ("b",   0 ), ("c", 1)]
-- >>> m2 = 'fromList' [("a",   1 ), ("b",   1 ), ("c", 1)]
-- >>> m3 = 'fromList' [("a", (-2)), ("b", (-1)), ("c", 0)]
-- @
-- @
-- >>> m1 '`minus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", (-1)), ("b",   0 ), ("c",   1 )]
-- >>> m2 = 'fromList' [("a", (-1)), ("b", (-1)), ("c", (-1))]
-- >>> m3 = 'fromList' [("a",   0 ), ("b",   1 ), ("c",   2 )]
-- @
-- @
-- >>> m1 '`minus`' m2 '==' m3
-- 'True'
-- @
--
minus
    :: (Ord k, MonoidNull v, Group v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
minus :: forall k v.
(Ord k, MonoidNull v, Group v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
minus = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- a ~~ mempty ≡ a

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        (v -> v) -> WhenOneSideNull Identity k v v
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> v2) -> WhenOneSideNull f k v1 v2
withNonNull v -> v
forall m. Group m => m -> m
C.invert
        -- Justification:
        --
        -- a      ~~ b ≡ a      <> invert b
        -- mempty ~~ b ≡ mempty <> invert b
        -- mempty ~~ b ≡           invert b

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. Group m => m -> m -> m
(C.~~)
    }
{-# INLINE minus #-}

-- | Performs /reductive subtraction/ of the second map from the first.
--
-- Uses the 'Reductive' subtraction operator '(</>)' to subtract each value in
-- the second map from its matching value in the first map.
--
-- This function produces a result if (and only if) for all possible keys
-- __@k@__, it is possible to subtract the value for __@k@__ in the second map
-- from the value for __@k@__ in the first map:
--
-- @
-- 'isJust' (m1 '`minusMaybe`' m2)
--     '==' (∀ k. 'isJust' ('get' k m1 '</>' 'get' k m2))
-- @
--
-- Otherwise, this function returns 'Nothing'.
--
-- This function satisfies the following property:
--
-- @
-- 'all'
--    (\\r -> 'Just' ('get' k r) '==' 'get' k m1 '</>' 'get' k m2)
--    (m1 '`minusMaybe`' m2)
-- @
--
-- This function provides the definition of '(</>)' for the 'MonoidMap'
-- instance of 'Reductive'.
--
-- === __Examples__
--
-- With 'Set' 'Numeric.Natural.Natural' values, this function performs /set/
-- /subtraction/ of matching values, succeeding if (and only if) each value
-- from the second map is a subset of its matching value from the first map:
--
-- @
-- f xs = 'fromList' ('Set.fromList' '<$>' xs)
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2])]
-- >>> m2 = f [("a", [     ]), ("b", [0,1,2])]
-- >>> m3 = f [("a", [0,1,2]), ("b", [     ])]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Just' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2]), ("c", [0,1,2])]
-- >>> m2 = f [("a", [0    ]), ("b", [  1  ]), ("c", [    2])]
-- >>> m3 = f [("a", [  1,2]), ("b", [0,  2]), ("c", [0,1  ])]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Just' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2    ]), ("b", [0,1,2    ]), ("c", [0,1,2    ])]
-- >>> m2 = f [("a", [    2,3,4]), ("b", [  1,2,3,4]), ("c", [0,1,2,3,4])]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Nothing'
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values, this function
-- performs /ordinary/ /subtraction/ of matching values, succeeding if (and only
-- if) each value from the second map is less than or equal to its matching
-- value from the first map:
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- >>> m2 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
-- >>> m3 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Just' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- >>> m2 = 'fromList' [("a", 1), ("b", 2), ("c", 3), ("d", 5)]
-- >>> m3 = 'fromList' [("a", 1), ("b", 1), ("c", 2), ("d", 3)]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Just' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- >>> m2 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Just' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
-- >>> m2 = 'fromList' [("a", 3), ("b", 3), ("c", 5), ("d", 8)]
-- @
-- @
-- >>> m1 '`minusMaybe`' m2 '==' 'Nothing'
-- 'True'
-- @
--
minusMaybe
    :: (Ord k, MonoidNull v, Reductive v)
    => MonoidMap k v
    -> MonoidMap k v
    -> Maybe (MonoidMap k v)
minusMaybe :: forall k v.
(Ord k, MonoidNull v, Reductive v) =>
MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
minusMaybe = MergeStrategy Maybe k v v v
-> MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)
forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA MergeStrategy
    { withNonNullL :: WhenOneSideNull Maybe k v v
withNonNullL =
        WhenOneSideNull Maybe k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- According to laws for Reductive:
        -- maybe a (b      <>) (a </> b     ) ≡       a
        -- maybe a (mempty <>) (a </> mempty) ≡       a
        -- maybe a (id       ) (a </> mempty) ≡       a
        --                     (a </> mempty) ∈ {Just a, Nothing}
        --
        -- According to laws for LeftReductive and RightReductive:
        -- isJust (a </> b     ) ≡ b      `isPrefixOf` a ≡ b      `isSuffixOf` a
        -- isJust (a </> mempty) ≡ mempty `isPrefixOf` a ≡ mempty `isSuffixOf` a
        --
        -- According to laws for LeftReductive and RightReductive:
        -- b      `isPrefixOf` (b      <> a)
        -- mempty `isPrefixOf` (mempty <> a)
        -- mempty `isPrefixOf`            a
        --
        -- Therefore:
        -- a </> mempty ≡ Just a

    , withNonNullR :: WhenOneSideNull Maybe k v v
withNonNullR =
        (v -> Maybe v) -> WhenOneSideNull Maybe k v v
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA (\v
v -> v
forall a. Monoid a => a
mempty v -> v -> Maybe v
forall m. Reductive m => m -> m -> Maybe m
</> v
v)

    , withNonNullP :: WhenBothNonNull Maybe k v v v
withNonNullP =
        (v -> v -> Maybe v) -> WhenBothNonNull Maybe k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v -> v -> Maybe v
forall m. Reductive m => m -> m -> Maybe m
(</>)
    }
{-# INLINE minusMaybe #-}

-- | Performs /monus subtraction/ of the second map from the first.
--
-- Uses the 'Monus' subtraction operator '(<\>)' to subtract each value in
-- the second map from its matching value in the first map.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k (m1 '`monus`' m2) '==' 'get' k m1 '<\>' 'get' k m2
-- @
--
-- This function provides the definition of '(<\>)' for the 'MonoidMap'
-- instance of 'Monus'.
--
-- === __Examples__
--
-- With 'Set' 'Numeric.Natural.Natural' values, this function performs /set/
-- /subtraction/ of matching values:
--
-- @
-- f xs = 'fromList' ('Set.fromList' '<$>' xs)
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2])]
-- >>> m2 = f [("a", [     ]), ("b", [0,1,2])]
-- >>> m3 = f [("a", [0,1,2]), ("b", [     ])]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2]), ("b", [0,1,2]), ("c", [0,1,2])]
-- >>> m2 = f [("a", [0    ]), ("b", [  1  ]), ("c", [    2])]
-- >>> m3 = f [("a", [  1,2]), ("b", [0,  2]), ("c", [0,1  ])]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = f [("a", [0,1,2    ]), ("b", [0,1,2    ]), ("c", [0,1,2    ])]
-- >>> m2 = f [("a", [    2,3,4]), ("b", [  1,2,3,4]), ("c", [0,1,2,3,4])]
-- >>> m3 = f [("a", [0,1      ]), ("b", [0        ]), ("c", [         ])]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values, this function
-- performs /truncated/ /subtraction/ of matching values:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 1), ("b", 1), ("c", 1), ("d", 1)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 0), ("c", 1), ("d", 2)]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 1)]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 4), ("b", 4), ("c", 4), ("d", 4)]
-- >>> m3 = 'fromList' [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
-- @
-- @
-- >>> m1 '`monus`' m2 '==' m3
-- 'True'
-- @
--
monus
    :: (Ord k, MonoidNull v, Monus v)
    => MonoidMap k v
    -> MonoidMap k v
    -> MonoidMap k v
monus :: forall k v.
(Ord k, MonoidNull v, Monus v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
monus = MergeStrategy Identity k v v v
-> MonoidMap k v -> MonoidMap k v -> MonoidMap k v
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v v
withNonNullL =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull
        -- Justification:
        --
        -- a      <> (b <\> a     ) ≡ b <> (a      <\> b)
        -- mempty <> (b <\> mempty) ≡ b <> (mempty <\> a)
        --            b <\> mempty  ≡ b <> (mempty <\> a)
        --            b <\> mempty  ≡ b <>  mempty
        --            b <\> mempty  ≡ b

    , withNonNullR :: WhenOneSideNull Identity k v v
withNonNullR =
        WhenOneSideNull Identity k v v
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
        -- Justification:
        --
        -- mempty <\> a ≡ mempty

    , withNonNullP :: WhenBothNonNull Identity k v v v
withNonNullP =
        (v -> v -> v) -> WhenBothNonNull Identity k v v v
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v -> v -> v
forall m. Monus m => m -> m -> m
(<\>)
    }
{-# INLINE monus #-}

--------------------------------------------------------------------------------
-- Inversion
--------------------------------------------------------------------------------

-- | Inverts every value in a map.
--
-- Applies the 'Group' method 'C.invert' to every value in a map.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('invert' m) '==' 'C.invert' ('get' k m)
-- @
--
-- This function provides the definition of 'C.invert' for the 'MonoidMap'
-- instance of 'Group'.
--
-- === __Examples__
--
-- With 'Data.Monoid.Sum' 'Integer' values, this function performs negation
-- of values:
--
-- @
-- >>> m1 = 'fromList' [("a", (-1)), ("b", 0), ("c",   1) ]
-- >>> m2 = 'fromList' [("a",   1 ), ("b", 0), ("c", (-1))]
-- @
-- @
-- >>> 'negate' m1 '==' m2
-- 'True'
-- @
--
invert
    :: (MonoidNull v, Group v)
    => MonoidMap k v
    -> MonoidMap k v
invert :: forall v k.
(MonoidNull v, Group v) =>
MonoidMap k v -> MonoidMap k v
invert = (v -> v) -> MonoidMap k v -> MonoidMap k v
forall v2 v1 k.
MonoidNull v2 =>
(v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2
map v -> v
forall m. Group m => m -> m
C.invert
{-# INLINE invert #-}

--------------------------------------------------------------------------------
-- Exponentiation
--------------------------------------------------------------------------------

-- | Performs exponentiation of every value in a map.
--
-- Uses the 'Group' exponentiation method 'C.pow' to raise every value in a map
-- to the power of the given exponent.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k (m '`power`' i) '==' 'get' k m '`C.pow`' i
-- @
--
-- This function provides the definition of 'C.pow' for the 'MonoidMap'
-- instance of 'Group'.
--
-- === __Examples__
--
-- With 'Data.Monoid.Sum' 'Numeric.Natural.Natural' values, this function
-- performs /ordinary multiplication/ of all values by the given exponent:
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
-- >>> m2 = 'fromList' [("a", 0), ("b", 2), ("c", 4), ("d", 6)]
-- @
-- @
-- >>> m1 '`power`' 2 '==' m2
-- 'True'
-- @
--
-- @
-- >>> m1 = 'fromList' [("a", 0), ("b",   1 ), ("c",   2 ), ("d",   3 )]
-- >>> m2 = 'fromList' [("a", 0), ("b", (-1)), ("c", (-2)), ("d", (-3))]
-- @
-- @
-- >>> m1 '`power`' (-1) '==' m2
-- 'True'
-- @
--
power
    :: (Integral i, MonoidNull v, Group v)
    => MonoidMap k v
    -> i
    -> MonoidMap k v
power :: forall i v k.
(Integral i, MonoidNull v, Group v) =>
MonoidMap k v -> i -> MonoidMap k v
power MonoidMap k v
m i
i = (v -> v) -> MonoidMap k v -> MonoidMap k v
forall v2 v1 k.
MonoidNull v2 =>
(v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2
map (v -> i -> v
forall x. Integral x => v -> x -> v
forall m x. (Group m, Integral x) => m -> x -> m
`C.pow` i
i) MonoidMap k v
m
{-# INLINE power #-}

--------------------------------------------------------------------------------
-- Intersection
--------------------------------------------------------------------------------

-- | Computes the /intersection/ of a pair of maps using the given function
--   to combine values for matching keys.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('intersectionWith' f m1 m2) '=='
--     if k '`Set.member`'
--         'Set.intersection'
--             ('nonNullKeys' m1)
--             ('nonNullKeys' m2)
--     then f ('get' k m1) ('get' k m2)
--     else 'mempty'
-- @
--
-- === Conditional totality
--
-- /If/ the given combining function __@f@__ /always/ produces 'mempty' when
-- /either/ or /both/ of its arguments are 'mempty':
--
-- @
-- (f v      'mempty' '==' 'mempty') '&&'
-- (f 'mempty' v      '==' 'mempty')
-- @
--
-- /Then/ the following property holds for all possible keys __@k@__:
--
-- @
-- 'get' k ('intersectionWith' f m1 m2) '==' f ('get' k m1) ('get' k m2)
-- @
--
-- === __Examples__
--
-- With the 'Prelude.min' function applied to 'Data.Monoid.Sum'
-- 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1)          ]
-- >>> m2 = 'fromList' [          ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m3 = 'fromList' [          ("b", 1), ("c", 2), ("d", 1)          ]
-- @
-- @
-- >>> 'intersectionWith' 'Prelude.min' m1 m2 '==' m3
-- 'True'
-- @
--
intersectionWith
    :: (Ord k, MonoidNull v3)
    => (v1 -> v2 -> v3)
    -- ^ Function with which to combine values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> MonoidMap k v3
intersectionWith :: forall k v3 v1 v2.
(Ord k, MonoidNull v3) =>
(v1 -> v2 -> v3)
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
intersectionWith v1 -> v2 -> v3
f = MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v1 v3
withNonNullL =
        WhenOneSideNull Identity k v1 v3
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
    , withNonNullR :: WhenOneSideNull Identity k v2 v3
withNonNullR =
        WhenOneSideNull Identity k v2 v3
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
    , withNonNullP :: WhenBothNonNull Identity k v1 v2 v3
withNonNullP =
        (v1 -> v2 -> v3) -> WhenBothNonNull Identity k v1 v2 v3
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v1 -> v2 -> v3
f
    }
{-# INLINE intersectionWith #-}

-- | An /applicative/ version of 'intersectionWith'.
--
-- Satisfies the following property:
--
-- @
-- 'runIdentity' ('intersectionWithA' (('fmap' . 'fmap') 'Identity' f) m1 m2)
--          '==' ('intersectionWith'    \    \   \    \  \        \ f  m1 m2)
-- @
--
intersectionWithA
    :: (Applicative f, Ord k, MonoidNull v3)
    => (v1 -> v2 -> f v3)
    -- ^ Function with which to combine values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> f (MonoidMap k v3)
intersectionWithA :: forall (f :: * -> *) k v3 v1 v2.
(Applicative f, Ord k, MonoidNull v3) =>
(v1 -> v2 -> f v3)
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
intersectionWithA v1 -> v2 -> f v3
f = MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA MergeStrategy
    { withNonNullL :: WhenOneSideNull f k v1 v3
withNonNullL =
        WhenOneSideNull f k v1 v3
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
    , withNonNullR :: WhenOneSideNull f k v2 v3
withNonNullR =
        WhenOneSideNull f k v2 v3
forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull
    , withNonNullP :: WhenBothNonNull f k v1 v2 v3
withNonNullP =
        (v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v1 -> v2 -> f v3
f
    }
{-# INLINE intersectionWithA #-}

--------------------------------------------------------------------------------
-- Union
--------------------------------------------------------------------------------

-- | Computes the /union/ of a pair of maps using the given function to combine
--   values for matching keys.
--
-- Satisfies the following property for all possible keys __@k@__:
--
-- @
-- 'get' k ('unionWith' f m1 m2) '=='
--     if k '`Set.member`'
--         'Set.union'
--             ('nonNullKeys' m1)
--             ('nonNullKeys' m2)
--     then f ('get' k m1) ('get' k m2)
--     else 'mempty'
-- @
--
-- === Conditional totality
--
-- /If/ the given combining function __@f@__ /always/ produces 'mempty' when
-- /both/ of its arguments are 'mempty':
--
-- @
-- f 'mempty' 'mempty' '==' 'mempty'
-- @
--
-- /Then/ the following property holds for all possible keys __@k@__:
--
-- @
-- 'get' k ('unionWith' f m1 m2) '==' f ('get' k m1) ('get' k m2)
-- @
--
-- === __Examples__
--
-- With the 'Prelude.max' function applied to 'Data.Monoid.Sum'
-- 'Numeric.Natural.Natural' values:
--
-- @
-- >>> m1 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 1)          ]
-- >>> m2 = 'fromList' [          ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
-- >>> m3 = 'fromList' [("a", 4), ("b", 3), ("c", 2), ("d", 3), ("e", 4)]
-- @
-- @
-- >>> 'unionWith' 'Prelude.max' m1 m2 '==' m3
-- 'True'
-- @
--
unionWith
    :: (Ord k, Monoid v1, Monoid v2, MonoidNull v3)
    => (v1 -> v2 -> v3)
    -- ^ Function with which to combine values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> MonoidMap k v3
unionWith :: forall k v1 v2 v3.
(Ord k, Monoid v1, Monoid v2, MonoidNull v3) =>
(v1 -> v2 -> v3)
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
unionWith v1 -> v2 -> v3
f = MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge MergeStrategy
    { withNonNullL :: WhenOneSideNull Identity k v1 v3
withNonNullL =
        (v1 -> v3) -> WhenOneSideNull Identity k v1 v3
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> v2) -> WhenOneSideNull f k v1 v2
withNonNull (\v1
v -> v1 -> v2 -> v3
f v1
v v2
forall a. Monoid a => a
mempty)
    , withNonNullR :: WhenOneSideNull Identity k v2 v3
withNonNullR =
        (v2 -> v3) -> WhenOneSideNull Identity k v2 v3
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> v2) -> WhenOneSideNull f k v1 v2
withNonNull (\v2
v -> v1 -> v2 -> v3
f v1
forall a. Monoid a => a
mempty v2
v)
    , withNonNullP :: WhenBothNonNull Identity k v1 v2 v3
withNonNullP =
        (v1 -> v2 -> v3) -> WhenBothNonNull Identity k v1 v2 v3
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v1 -> v2 -> v3
f
    }
{-# INLINE unionWith #-}

-- | An /applicative/ version of 'unionWith'.
--
-- Satisfies the following property:
--
-- @
-- 'runIdentity' ('unionWithA' (('fmap' . 'fmap') 'Identity' f) m1 m2)
--          '==' ('unionWith'    \    \   \    \  \        \ f  m1 m2)
-- @
--
unionWithA
    :: (Applicative f, Ord k, Monoid v1, Monoid v2, MonoidNull v3)
    => (v1 -> v2 -> f v3)
    -- ^ Function with which to combine values for matching keys.
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> f (MonoidMap k v3)
unionWithA :: forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k, Monoid v1, Monoid v2, MonoidNull v3) =>
(v1 -> v2 -> f v3)
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
unionWithA v1 -> v2 -> f v3
f = MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA MergeStrategy
    { withNonNullL :: WhenOneSideNull f k v1 v3
withNonNullL =
        (v1 -> f v3) -> WhenOneSideNull f k v1 v3
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA (\v1
v -> v1 -> v2 -> f v3
f v1
v v2
forall a. Monoid a => a
mempty)
    , withNonNullR :: WhenOneSideNull f k v2 v3
withNonNullR =
        (v2 -> f v3) -> WhenOneSideNull f k v2 v3
forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA (\v2
v -> v1 -> v2 -> f v3
f v1
forall a. Monoid a => a
mempty v2
v)
    , withNonNullP :: WhenBothNonNull f k v1 v2 v3
withNonNullP =
        (v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v1 -> v2 -> f v3
f
    }
{-# INLINE unionWithA #-}

--------------------------------------------------------------------------------
-- Merging
--------------------------------------------------------------------------------

type WhenOneSideNull f k          vx                        vr
   = Map.WhenMissing f k (NonNull vx)              (NonNull vr)
type WhenBothNonNull f k          v1           v2           vr
   = Map.WhenMatched f k (NonNull v1) (NonNull v2) (NonNull vr)

data MergeStrategy f k v1 v2 v3 = MergeStrategy
    { forall (f :: * -> *) k v1 v2 v3.
MergeStrategy f k v1 v2 v3 -> WhenOneSideNull f k v1 v3
withNonNullL :: !(WhenOneSideNull f k v1    v3)
    , forall (f :: * -> *) k v1 v2 v3.
MergeStrategy f k v1 v2 v3 -> WhenOneSideNull f k v2 v3
withNonNullR :: !(WhenOneSideNull f k    v2 v3)
    , forall (f :: * -> *) k v1 v2 v3.
MergeStrategy f k v1 v2 v3 -> WhenBothNonNull f k v1 v2 v3
withNonNullP :: !(WhenBothNonNull f k v1 v2 v3)
    }

merge
    :: Ord k
    => MergeStrategy Identity k v1 v2 v3
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> MonoidMap k v3
merge :: forall k v1 v2 v3.
Ord k =>
MergeStrategy Identity k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> MonoidMap k v3
merge (MergeStrategy WhenOneSideNull Identity k v1 v3
nnl WhenOneSideNull Identity k v2 v3
nnr WhenBothNonNull Identity k v1 v2 v3
nnp) (MonoidMap Map k (NonNull v1)
m1) (MonoidMap Map k (NonNull v2)
m2) =
    Map k (NonNull v3) -> MonoidMap k v3
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v3) -> MonoidMap k v3)
-> Map k (NonNull v3) -> MonoidMap k v3
forall a b. (a -> b) -> a -> b
$ WhenOneSideNull Identity k v1 v3
-> WhenOneSideNull Identity k v2 v3
-> WhenBothNonNull Identity k v1 v2 v3
-> Map k (NonNull v1)
-> Map k (NonNull v2)
-> Map k (NonNull v3)
forall k a c b.
Ord k =>
SimpleWhenMissing k a c
-> SimpleWhenMissing k b c
-> SimpleWhenMatched k a b c
-> Map k a
-> Map k b
-> Map k c
Map.merge WhenOneSideNull Identity k v1 v3
nnl WhenOneSideNull Identity k v2 v3
nnr WhenBothNonNull Identity k v1 v2 v3
nnp Map k (NonNull v1)
m1 Map k (NonNull v2)
m2
{-# INLINE merge #-}

mergeA
    :: (Applicative f, Ord k)
    => MergeStrategy f k v1 v2 v3
    -> MonoidMap k v1
    -> MonoidMap k v2
    -> f (MonoidMap k v3)
mergeA :: forall (f :: * -> *) k v1 v2 v3.
(Applicative f, Ord k) =>
MergeStrategy f k v1 v2 v3
-> MonoidMap k v1 -> MonoidMap k v2 -> f (MonoidMap k v3)
mergeA (MergeStrategy WhenOneSideNull f k v1 v3
nnl WhenOneSideNull f k v2 v3
nnr WhenBothNonNull f k v1 v2 v3
nnp) (MonoidMap Map k (NonNull v1)
m1) (MonoidMap Map k (NonNull v2)
m2) =
    Map k (NonNull v3) -> MonoidMap k v3
forall k v. Map k (NonNull v) -> MonoidMap k v
MonoidMap (Map k (NonNull v3) -> MonoidMap k v3)
-> f (Map k (NonNull v3)) -> f (MonoidMap k v3)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> WhenOneSideNull f k v1 v3
-> WhenOneSideNull f k v2 v3
-> WhenBothNonNull f k v1 v2 v3
-> Map k (NonNull v1)
-> Map k (NonNull v2)
-> f (Map k (NonNull v3))
forall (f :: * -> *) k a c b.
(Applicative f, Ord k) =>
WhenMissing f k a c
-> WhenMissing f k b c
-> WhenMatched f k a b c
-> Map k a
-> Map k b
-> f (Map k c)
Map.mergeA WhenOneSideNull f k v1 v3
nnl WhenOneSideNull f k v2 v3
nnr WhenBothNonNull f k v1 v2 v3
nnp Map k (NonNull v1)
m1 Map k (NonNull v2)
m2
{-# INLINE mergeA #-}

keepNull
    :: Applicative f
    => WhenOneSideNull f k v1 v2
keepNull :: forall (f :: * -> *) k v1 v2.
Applicative f =>
WhenOneSideNull f k v1 v2
keepNull = WhenMissing f k (NonNull v1) (NonNull v2)
forall (f :: * -> *) k x y. Applicative f => WhenMissing f k x y
Map.dropMissing
{-# INLINE keepNull #-}

keepNonNull
    :: Applicative f
    => WhenOneSideNull f k v v
keepNonNull :: forall (f :: * -> *) k v. Applicative f => WhenOneSideNull f k v v
keepNonNull = WhenMissing f k (NonNull v) (NonNull v)
forall (f :: * -> *) k x. Applicative f => WhenMissing f k x x
Map.preserveMissing
{-# INLINE keepNonNull #-}

withNonNull
    :: (Applicative f, MonoidNull v2)
    => (v1 -> v2)
    -> WhenOneSideNull f k v1 v2
withNonNull :: forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> v2) -> WhenOneSideNull f k v1 v2
withNonNull v1 -> v2
f
    = (k -> NonNull v1 -> Maybe (NonNull v2))
-> WhenMissing f k (NonNull v1) (NonNull v2)
forall (f :: * -> *) k x y.
Applicative f =>
(k -> x -> Maybe y) -> WhenMissing f k x y
Map.mapMaybeMissing
    ((k -> NonNull v1 -> Maybe (NonNull v2))
 -> WhenMissing f k (NonNull v1) (NonNull v2))
-> (k -> NonNull v1 -> Maybe (NonNull v2))
-> WhenMissing f k (NonNull v1) (NonNull v2)
forall a b. (a -> b) -> a -> b
$ \k
_k NonNull v1
v -> v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2)) -> v2 -> Maybe (NonNull v2)
forall a b. (a -> b) -> a -> b
$ (v1 -> v2) -> NonNull v1 -> v2
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v1 -> v2
f NonNull v1
v
{-# INLINE withNonNull #-}

withNonNullA
    :: (Applicative f, MonoidNull v2)
    => (v1 -> f v2)
    -> WhenOneSideNull f k v1 v2
withNonNullA :: forall (f :: * -> *) v2 v1 k.
(Applicative f, MonoidNull v2) =>
(v1 -> f v2) -> WhenOneSideNull f k v1 v2
withNonNullA v1 -> f v2
f
    = (k -> NonNull v1 -> f (Maybe (NonNull v2)))
-> WhenMissing f k (NonNull v1) (NonNull v2)
forall (f :: * -> *) k x y.
Applicative f =>
(k -> x -> f (Maybe y)) -> WhenMissing f k x y
Map.traverseMaybeMissing
    ((k -> NonNull v1 -> f (Maybe (NonNull v2)))
 -> WhenMissing f k (NonNull v1) (NonNull v2))
-> (k -> NonNull v1 -> f (Maybe (NonNull v2)))
-> WhenMissing f k (NonNull v1) (NonNull v2)
forall a b. (a -> b) -> a -> b
$ \k
_k NonNull v1
v -> v2 -> Maybe (NonNull v2)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v2 -> Maybe (NonNull v2)) -> f v2 -> f (Maybe (NonNull v2))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (v1 -> f v2) -> NonNull v1 -> f v2
forall v a. (v -> a) -> NonNull v -> a
applyNonNull v1 -> f v2
f NonNull v1
v
{-# INLINE withNonNullA #-}

withBoth
    :: (Applicative f, MonoidNull v3)
    => (v1 -> v2 -> v3)
    -> WhenBothNonNull f k v1 v2 v3
withBoth :: forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> v3) -> WhenBothNonNull f k v1 v2 v3
withBoth v1 -> v2 -> v3
f
    = (k -> NonNull v1 -> NonNull v2 -> Maybe (NonNull v3))
-> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3)
forall (f :: * -> *) k x y z.
Applicative f =>
(k -> x -> y -> Maybe z) -> WhenMatched f k x y z
Map.zipWithMaybeMatched
    ((k -> NonNull v1 -> NonNull v2 -> Maybe (NonNull v3))
 -> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3))
-> (k -> NonNull v1 -> NonNull v2 -> Maybe (NonNull v3))
-> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3)
forall a b. (a -> b) -> a -> b
$ \k
_k NonNull v1
v1 NonNull v2
v2 -> v3 -> Maybe (NonNull v3)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v3 -> Maybe (NonNull v3)) -> v3 -> Maybe (NonNull v3)
forall a b. (a -> b) -> a -> b
$ (v1 -> v2 -> v3) -> NonNull v1 -> NonNull v2 -> v3
forall v1 v2 a. (v1 -> v2 -> a) -> NonNull v1 -> NonNull v2 -> a
applyNonNull2 v1 -> v2 -> v3
f NonNull v1
v1 NonNull v2
v2
{-# INLINE withBoth #-}

withBothA
    :: (Applicative f, MonoidNull v3)
    => (v1 -> v2 -> f v3)
    -> WhenBothNonNull f k v1 v2 v3
withBothA :: forall (f :: * -> *) v3 v1 v2 k.
(Applicative f, MonoidNull v3) =>
(v1 -> v2 -> f v3) -> WhenBothNonNull f k v1 v2 v3
withBothA v1 -> v2 -> f v3
f
    = (k -> NonNull v1 -> NonNull v2 -> f (Maybe (NonNull v3)))
-> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3)
forall (f :: * -> *) k x y z.
Applicative f =>
(k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z
Map.zipWithMaybeAMatched
    ((k -> NonNull v1 -> NonNull v2 -> f (Maybe (NonNull v3)))
 -> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3))
-> (k -> NonNull v1 -> NonNull v2 -> f (Maybe (NonNull v3)))
-> WhenMatched f k (NonNull v1) (NonNull v2) (NonNull v3)
forall a b. (a -> b) -> a -> b
$ \k
_k NonNull v1
v1 NonNull v2
v2 -> v3 -> Maybe (NonNull v3)
forall v. MonoidNull v => v -> Maybe (NonNull v)
maybeNonNull (v3 -> Maybe (NonNull v3)) -> f v3 -> f (Maybe (NonNull v3))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (v1 -> v2 -> f v3) -> NonNull v1 -> NonNull v2 -> f v3
forall v1 v2 a. (v1 -> v2 -> a) -> NonNull v1 -> NonNull v2 -> a
applyNonNull2 v1 -> v2 -> f v3
f NonNull v1
v1 NonNull v2
v2
{-# INLINE withBothA #-}

--------------------------------------------------------------------------------
-- State
--------------------------------------------------------------------------------

newtype StateL s a = StateL (s -> (s, a))
newtype StateR s a = StateR (s -> (s, a))

instance Functor (StateL s) where
    fmap :: forall a b. (a -> b) -> StateL s a -> StateL s b
fmap a -> b
f (StateL s -> (s, a)
kx) =
        (s -> (s, b)) -> StateL s b
forall s a. (s -> (s, a)) -> StateL s a
StateL ((s -> (s, b)) -> StateL s b) -> (s -> (s, b)) -> StateL s b
forall a b. (a -> b) -> a -> b
$ \s
s -> let (s
s', a
x) = s -> (s, a)
kx s
s in (s
s', a -> b
f a
x)

instance Functor (StateR s) where
    fmap :: forall a b. (a -> b) -> StateR s a -> StateR s b
fmap a -> b
f (StateR s -> (s, a)
kx) =
        (s -> (s, b)) -> StateR s b
forall s a. (s -> (s, a)) -> StateR s a
StateR ((s -> (s, b)) -> StateR s b) -> (s -> (s, b)) -> StateR s b
forall a b. (a -> b) -> a -> b
$ \s
s -> let (s
s', a
x) = s -> (s, a)
kx s
s in (s
s', a -> b
f a
x)

instance Applicative (StateL s) where
    pure :: forall a. a -> StateL s a
pure a
a = (s -> (s, a)) -> StateL s a
forall s a. (s -> (s, a)) -> StateL s a
StateL ((s -> (s, a)) -> StateL s a) -> (s -> (s, a)) -> StateL s a
forall a b. (a -> b) -> a -> b
$
        \s
s -> (s
s, a
a)
    StateL s -> (s, a -> b)
kf <*> :: forall a b. StateL s (a -> b) -> StateL s a -> StateL s b
<*> StateL s -> (s, a)
kx = (s -> (s, b)) -> StateL s b
forall s a. (s -> (s, a)) -> StateL s a
StateL ((s -> (s, b)) -> StateL s b) -> (s -> (s, b)) -> StateL s b
forall a b. (a -> b) -> a -> b
$
        \s
s ->
            let (s
s' , a -> b
f  ) = s -> (s, a -> b)
kf s
s
                (s
s'',   a
x) = s -> (s, a)
kx s
s'
            in  (s
s'', a -> b
f a
x)
    liftA2 :: forall a b c.
(a -> b -> c) -> StateL s a -> StateL s b -> StateL s c
liftA2 a -> b -> c
f (StateL s -> (s, a)
kx) (StateL s -> (s, b)
ky) = (s -> (s, c)) -> StateL s c
forall s a. (s -> (s, a)) -> StateL s a
StateL ((s -> (s, c)) -> StateL s c) -> (s -> (s, c)) -> StateL s c
forall a b. (a -> b) -> a -> b
$
        \s
s ->
            let (s
s' ,   a
x  ) = s -> (s, a)
kx s
s
                (s
s'',     b
y) = s -> (s, b)
ky s
s'
            in  (s
s'', a -> b -> c
f a
x b
y)

instance Applicative (StateR s) where
    pure :: forall a. a -> StateR s a
pure a
a = (s -> (s, a)) -> StateR s a
forall s a. (s -> (s, a)) -> StateR s a
StateR ((s -> (s, a)) -> StateR s a) -> (s -> (s, a)) -> StateR s a
forall a b. (a -> b) -> a -> b
$
        \s
s -> (s
s, a
a)
    StateR s -> (s, a -> b)
kf <*> :: forall a b. StateR s (a -> b) -> StateR s a -> StateR s b
<*> StateR s -> (s, a)
kx = (s -> (s, b)) -> StateR s b
forall s a. (s -> (s, a)) -> StateR s a
StateR ((s -> (s, b)) -> StateR s b) -> (s -> (s, b)) -> StateR s b
forall a b. (a -> b) -> a -> b
$
        \s
s ->
            let (s
s',    a
x) = s -> (s, a)
kx s
s
                (s
s'', a -> b
f  ) = s -> (s, a -> b)
kf s
s'
            in  (s
s'', a -> b
f a
x)
    liftA2 :: forall a b c.
(a -> b -> c) -> StateR s a -> StateR s b -> StateR s c
liftA2 a -> b -> c
f (StateR s -> (s, a)
kx) (StateR s -> (s, b)
ky) = (s -> (s, c)) -> StateR s c
forall s a. (s -> (s, a)) -> StateR s a
StateR ((s -> (s, c)) -> StateR s c) -> (s -> (s, c)) -> StateR s c
forall a b. (a -> b) -> a -> b
$
        \s
s ->
            let (s
s' ,     b
y) = s -> (s, b)
ky s
s
                (s
s'',   a
x  ) = s -> (s, a)
kx s
s'
            in  (s
s'', a -> b -> c
f a
x b
y)