{-# OPTIONS_GHC -fno-warn-redundant-constraints #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}
{- 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
    , 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

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

    -- *** Strict folding
    , foldl'
    , foldr'
    , foldlWithKey'
    , foldrWithKey'

    -- * 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
    )

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.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

--------------------------------------------------------------------------------
-- 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 length of the list.
--
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(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

--------------------------------------------------------------------------------
-- 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.
--
-- 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)\). 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.
--
-- 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)\). 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.
--
-- 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)\). 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.
--
-- 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' #-}

--------------------------------------------------------------------------------
-- 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 #-}