{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE GADTs #-}

module Data.Dependent.Map.Monoidal where

import Data.Aeson
import Data.Coerce
import Data.Constraint.Extras
import Data.Constraint.Forall
import Data.Dependent.Map (DMap)
import qualified Data.Dependent.Map as DMap
import Data.Dependent.Sum
import Data.Dependent.Sum.Orphans ()
import Data.GADT.Compare
import Data.GADT.Show
import Data.Maybe
import Data.Semigroup
import Data.Some hiding (This)
import Data.Type.Equality
import Text.Read
import Prelude hiding (lookup, map)

newtype MonoidalDMap (f :: k -> *) (g :: k -> *) = MonoidalDMap { forall k (f :: k -> *) (g :: k -> *). MonoidalDMap f g -> DMap f g
unMonoidalDMap :: DMap f g }

-- Temporary shim to avoid making changes to dependent-sum and dependent-map.
-- TODO: Finalise constraints-extras and optionally get it upstreamed into constraints.
-- Then actually get these instances into the real DSum and DMap,
-- killing off EqTag, OrdTag, ShowTag and ReadTag.
newtype FakeDSum f g = FakeDSum { forall {k} (f :: k -> *) (g :: k -> *). FakeDSum f g -> DSum f g
unFakeDSum :: DSum f g }

instance (GEq f, Has' Eq f g) => Eq (FakeDSum f g) where
  FakeDSum ((f a
k :: k a) :=> g a
v) == :: FakeDSum f g -> FakeDSum f g -> Bool
== FakeDSum (f a
k' :=> g a
v') = case forall k (f :: k -> *) (a :: k) (b :: k).
GEq f =>
f a -> f b -> Maybe (a :~: b)
geq f a
k f a
k' of
    Maybe (a :~: a)
Nothing -> Bool
False
    Just a :~: a
Refl -> forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
       (f :: k' -> *) (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Eq @g f a
k (g a
v forall a. Eq a => a -> a -> Bool
== g a
v')

instance (GCompare f, Has' Eq f g, Has' Ord f g) => Ord (FakeDSum f g) where
  compare :: FakeDSum f g -> FakeDSum f g -> Ordering
compare (FakeDSum (f a
k :=> g a
v)) (FakeDSum (f a
k' :=> g a
v')) = case forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare f a
k f a
k' of
    GOrdering a a
GLT -> Ordering
LT
    GOrdering a a
GGT -> Ordering
GT
    GOrdering a a
GEQ -> forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
       (f :: k' -> *) (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Ord @g f a
k (forall a. Ord a => a -> a -> Ordering
compare g a
v g a
v')

-- NB: We're not going to show/parse the "FakeDSum" constructor, because this whole datatype is a temporary shim.
instance (ForallF Show f, Has' Show f g) => Show (FakeDSum f g) where
  showsPrec :: Int -> FakeDSum f g -> ShowS
showsPrec Int
p (FakeDSum ((f a
k :: f a) :=> g a
v)) = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
>= Int
10)
    ( forall {k2} {k1} (c :: k2 -> Constraint) (t :: k1 -> k2) (a :: k1)
       r.
ForallF c t =>
(c (t a) => r) -> r
whichever @Show @f @a (forall a. Show a => Int -> a -> ShowS
showsPrec Int
0 f a
k)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" :=> "
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
       (f :: k' -> *) (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Show @g f a
k (forall a. Show a => Int -> a -> ShowS
showsPrec Int
1 g a
v)
    )

instance (GRead f, Has' Read f g) => Read (FakeDSum f g) where
  readsPrec :: Int -> ReadS (FakeDSum f g)
readsPrec Int
p = forall a. Bool -> ReadS a -> ReadS a
readParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
1) forall a b. (a -> b) -> a -> b
$ \String
s ->
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
      [ forall {k} (tag :: k -> *) b.
Some tag -> (forall (a :: k). tag a -> b) -> b
getGReadResult Some f
withTag forall a b. (a -> b) -> a -> b
$ \f a
tag ->
          [ (forall {k} (f :: k -> *) (g :: k -> *). DSum f g -> FakeDSum f g
FakeDSum (f a
tag forall {k} (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> g a
val), String
rest'')
          | (g a
val, String
rest'') <- forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
       (f :: k' -> *) (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Read @g f a
tag forall a b. (a -> b) -> a -> b
$ forall a. Read a => Int -> ReadS a
readsPrec Int
1 String
rest'
          ]
      | (Some f
withTag, String
rest) <- forall k (t :: k -> *). GRead t => Int -> GReadS t
greadsPrec Int
p String
s
      , (String
":=>", String
rest') <- ReadS String
lex String
rest
      ]

instance forall f g. (Has' Eq f g, GCompare f) => Eq (MonoidalDMap f g) where
  MonoidalDMap DMap f g
m == :: MonoidalDMap f g -> MonoidalDMap f g -> Bool
== MonoidalDMap DMap f g
m' =
    (coerce :: forall a b. Coercible a b => a -> b
coerce (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m) :: [FakeDSum f g]) forall a. Eq a => a -> a -> Bool
== (coerce :: forall a b. Coercible a b => a -> b
coerce (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m'))

instance forall f g. (Has' Eq f g, Has' Ord f g, GCompare f) => Ord (MonoidalDMap f g) where
  compare :: MonoidalDMap f g -> MonoidalDMap f g -> Ordering
compare (MonoidalDMap DMap f g
m) (MonoidalDMap DMap f g
m') =
    forall a. Ord a => a -> a -> Ordering
compare (coerce :: forall a b. Coercible a b => a -> b
coerce (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m) :: [FakeDSum f g]) (coerce :: forall a b. Coercible a b => a -> b
coerce (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m'))

instance (Show (FakeDSum k f)) => Show (MonoidalDMap k f) where
    showsPrec :: Int -> MonoidalDMap k f -> ShowS
showsPrec Int
p MonoidalDMap k f
m = Bool -> ShowS -> ShowS
showParen (Int
pforall a. Ord a => a -> a -> Bool
>Int
10)
        ( String -> ShowS
showString String
"fromList "
        forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (coerce :: forall a b. Coercible a b => a -> b
coerce (forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [DSum k f]
toList MonoidalDMap k f
m) :: [FakeDSum k f])
        )

instance (GCompare k, Read (FakeDSum k f)) => Read (MonoidalDMap k f) where
  readPrec :: ReadPrec (MonoidalDMap k f)
readPrec = forall a. ReadPrec a -> ReadPrec a
parens forall a b. (a -> b) -> a -> b
$ forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
    Ident String
"fromList" <- ReadPrec Lexeme
lexP
    [FakeDSum k f]
xs <- forall a. Read a => ReadPrec a
readPrec
    forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
[DSum k2 f] -> DMap k2 f
DMap.fromList forall a b. (a -> b) -> a -> b
$ coerce :: forall a b. Coercible a b => a -> b
coerce ([FakeDSum k f]
xs :: [FakeDSum k f])
  readListPrec :: ReadPrec [MonoidalDMap k f]
readListPrec = forall a. Read a => ReadPrec [a]
readListPrecDefault

deriving instance (ToJSON (DMap f g)) => ToJSON (MonoidalDMap f g)

instance (Has' Semigroup f g, GCompare f) => Semigroup (MonoidalDMap f g) where
  (MonoidalDMap DMap f g
m) <> :: MonoidalDMap f g -> MonoidalDMap f g -> MonoidalDMap f g
<> (MonoidalDMap DMap f g
n) =
    forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> f v -> f v)
-> DMap k2 f -> DMap k2 f -> DMap k2 f
DMap.unionWithKey (\f v
f (g v
u :: g a) g v
v -> forall {k} {k'} (c :: k -> Constraint) (g :: k' -> k)
       (f :: k' -> *) (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Semigroup @g f v
f (g v
u forall a. Semigroup a => a -> a -> a
<> g v
v)) DMap f g
m DMap f g
n)

instance (Has' Semigroup f g, GCompare f) => Monoid (MonoidalDMap f g) where
  mempty :: MonoidalDMap f g
mempty = forall {k} (k :: k -> *) (f :: k -> *). MonoidalDMap k f
empty
  mappend :: MonoidalDMap f g -> MonoidalDMap f g -> MonoidalDMap f g
mappend MonoidalDMap f g
m MonoidalDMap f g
n = MonoidalDMap f g
m forall a. Semigroup a => a -> a -> a
<> MonoidalDMap f g
n

deriving instance (FromJSON (DMap f g)) => FromJSON (MonoidalDMap f g)

{--------------------------------------------------------------------
  Construction
--------------------------------------------------------------------}

-- | /O(1)/. The empty map.
--
-- > empty      == fromList []
-- > size empty == 0
empty :: MonoidalDMap k f
empty :: forall {k} (k :: k -> *) (f :: k -> *). MonoidalDMap k f
empty = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
DMap.empty

-- | /O(1)/. A map with a single element.
--
-- > singleton 1 'a'        == fromList [(1, 'a')]
-- > size (singleton 1 'a') == 1
singleton :: k v -> f v -> MonoidalDMap k f
singleton :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
k v -> f v -> MonoidalDMap k f
singleton k v
k f v
x = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
DMap.singleton k v
k f v
x)

{--------------------------------------------------------------------
  Query
--------------------------------------------------------------------}

-- | /O(1)/. Is the map empty?
null :: MonoidalDMap k f -> Bool
null :: forall {k} (k :: k -> *) (f :: k -> *). MonoidalDMap k f -> Bool
null (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Bool
DMap.null DMap k f
m

-- | /O(1)/. The number of elements in the map.
size :: MonoidalDMap k f -> Int
size :: forall {k} (k :: k -> *) (f :: k -> *). MonoidalDMap k f -> Int
size (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
DMap.size DMap k f
m

-- | /O(log n)/. Lookup the value at a key in the map.
--
-- The function will return the corresponding value as @('Just' value)@,
-- or 'Nothing' if the key isn't in the map.
lookup :: forall k f v. GCompare k => k v -> MonoidalDMap k f -> Maybe (f v)
lookup :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> Maybe (f v)
lookup k v
k (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe (f v)
DMap.lookup k v
k DMap k f
m


-- | /O(log n)/. Delete and find the minimal element.
--
-- > deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
-- > deleteFindMin                                            Error: can not return the minimal element of an empty map

deleteFindMin :: MonoidalDMap k f -> (DSum k f, MonoidalDMap k f)
deleteFindMin :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> (DSum k f, MonoidalDMap k f)
deleteFindMin (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> (DSum k2 f, DMap k2 f)
DMap.deleteFindMin DMap k f
m of
    (DSum k f
x, DMap k f
m') -> (DSum k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
m')

-- | /O(log n)/. Retrieves the minimal (key :=> value) entry of the map, and
-- the map stripped of that element, or 'Nothing' if passed an empty map.
minViewWithKey :: forall k f . MonoidalDMap k f -> Maybe (DSum k f, MonoidalDMap k f)
minViewWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> Maybe (DSum k f, MonoidalDMap k f)
minViewWithKey (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)
DMap.minViewWithKey DMap k f
m of
    Maybe (DSum k f, DMap k f)
Nothing -> forall a. Maybe a
Nothing
    Just (DSum k f
x, DMap k f
m') -> forall a. a -> Maybe a
Just (DSum k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
m')

-- | /O(log n)/. Retrieves the maximal (key :=> value) entry of the map, and
-- the map stripped of that element, or 'Nothing' if passed an empty map.
maxViewWithKey :: forall k f . MonoidalDMap k f -> Maybe (DSum k f, MonoidalDMap k f)
maxViewWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> Maybe (DSum k f, MonoidalDMap k f)
maxViewWithKey (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)
DMap.maxViewWithKey DMap k f
m of
    Maybe (DSum k f, DMap k f)
Nothing -> forall a. Maybe a
Nothing
    Just (DSum k f
x, DMap k f
m') -> forall a. a -> Maybe a
Just (DSum k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
m')

-- | /O(log n)/. Delete and find the maximal element.
--
-- > deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
-- > deleteFindMax empty                                      Error: can not return the maximal element of an empty map

deleteFindMax :: MonoidalDMap k f -> (DSum k f, MonoidalDMap k f)
deleteFindMax :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> (DSum k f, MonoidalDMap k f)
deleteFindMax (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> (DSum k2 f, DMap k2 f)
DMap.deleteFindMax DMap k f
m of
    (DSum k f
x, DMap k f
m') -> (DSum k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
m')

{--------------------------------------------------------------------
  Query
--------------------------------------------------------------------}

-- | /O(log n)/. Is the key a member of the map? See also 'notMember'.
member :: GCompare k => k a -> MonoidalDMap k f -> Bool
member :: forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
GCompare k =>
k a -> MonoidalDMap k f -> Bool
member k a
k = forall a. Maybe a -> Bool
isJust forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> Maybe (f v)
lookup k a
k

-- | /O(log n)/. Is the key not a member of the map? See also 'member'.
notMember :: GCompare k => k v -> MonoidalDMap k f -> Bool
notMember :: forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
GCompare k =>
k a -> MonoidalDMap k f -> Bool
notMember k v
k MonoidalDMap k f
m = Bool -> Bool
not (forall {k} (k :: k -> *) (a :: k) (f :: k -> *).
GCompare k =>
k a -> MonoidalDMap k f -> Bool
member k v
k MonoidalDMap k f
m)

-- | /O(log n)/. Find the value at a key.
-- Calls 'error' when the element can not be found.
-- Consider using 'lookup' when elements may not be present.
find :: GCompare k => k v -> MonoidalDMap k f -> f v
find :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
k v -> MonoidalDMap k f -> f v
find k v
k MonoidalDMap k f
m = case forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> Maybe (f v)
lookup k v
k MonoidalDMap k f
m of
    Maybe (f v)
Nothing -> forall a. HasCallStack => String -> a
error String
"MonoidalDMap.find: element not in the map"
    Just f v
v  -> f v
v

-- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns
-- the value at key @k@ or returns default value @def@
-- when the key is not in the map.
findWithDefault :: GCompare k => f v -> k v -> MonoidalDMap k f -> f v
findWithDefault :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
f v -> k v -> MonoidalDMap k f -> f v
findWithDefault f v
def k v
k MonoidalDMap k f
m = case forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> Maybe (f v)
lookup k v
k MonoidalDMap k f
m of
    Maybe (f v)
Nothing -> f v
def
    Just f v
v  -> f v
v

{--------------------------------------------------------------------
  Insertion
--------------------------------------------------------------------}

-- | /O(log n)/. Insert a new key and value in the map.
-- If the key is already present in the map, the associated value is
-- replaced with the supplied value. 'insert' is equivalent to
-- @'insertWith' 'const'@.
insert :: forall k f v. GCompare k => k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insert :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insert k v
k f v
v (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f
DMap.insert k v
k f v
v DMap k f
m)

-- | /O(log n)/. Insert with a function, combining new value and old value.
-- @'insertWith' f key value mp@
-- will insert the entry @key :=> value@ into @mp@ if key does
-- not exist in the map. If the key does exist, the function will
-- insert the entry @key :=> f new_value old_value@.
insertWith :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWith :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(f v -> f v -> f v)
-> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWith f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
DMap.insertWith f v -> f v -> f v
f k v
k f v
v DMap k f
m)

-- | Same as 'insertWith', but the combining function is applied strictly.
-- This is often the most desirable behavior.
insertWith' :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWith' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(f v -> f v -> f v)
-> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWith' f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
DMap.insertWith' f v -> f v -> f v
f k v
k f v
v DMap k f
m)

-- | /O(log n)/. Insert with a function, combining key, new value and old value.
-- @'insertWithKey' f key value mp@
-- will insert the entry @key :=> value@ into @mp@ if key does
-- not exist in the map. If the key does exist, the function will
-- insert the entry @key :=> f key new_value old_value@.
-- Note that the key passed to f is the same key passed to 'insertWithKey'.
insertWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v)
-> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWithKey k v -> f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> f v -> f v)
-> k2 v -> f v -> DMap k2 f -> DMap k2 f
DMap.insertWithKey k v -> f v -> f v -> f v
f k v
k f v
v DMap k f
m)

-- | Same as 'insertWithKey', but the combining function is applied strictly.
insertWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWithKey' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v)
-> k v -> f v -> MonoidalDMap k f -> MonoidalDMap k f
insertWithKey' k v -> f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> f v -> f v)
-> k2 v -> f v -> DMap k2 f -> DMap k2 f
DMap.insertWithKey' k v -> f v -> f v -> f v
f k v
k f v
v DMap k f
m)


-- | /O(log n)/. Combines insert operation with old value retrieval.
-- The expression (@'insertLookupWithKey' f k x map@)
-- is a pair where the first element is equal to (@'lookup' k map@)
-- and the second element equal to (@'insertWithKey' f k x map@).
insertLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f
                    -> (Maybe (f v), MonoidalDMap k f)
insertLookupWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v)
-> k v
-> f v
-> MonoidalDMap k f
-> (Maybe (f v), MonoidalDMap k f)
insertLookupWithKey k v -> f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> f v -> f v)
-> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
DMap.insertLookupWithKey k v -> f v -> f v -> f v
f k v
k f v
v DMap k f
m of
    (Maybe (f v)
x, DMap k f
y) -> (Maybe (f v)
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)

-- | /O(log n)/. A strict version of 'insertLookupWithKey'.
insertLookupWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> MonoidalDMap k f
                     -> (Maybe (f v), MonoidalDMap k f)
insertLookupWithKey' :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v)
-> k v
-> f v
-> MonoidalDMap k f
-> (Maybe (f v), MonoidalDMap k f)
insertLookupWithKey' k v -> f v -> f v -> f v
f k v
k f v
v (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> f v -> f v)
-> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
DMap.insertLookupWithKey' k v -> f v -> f v -> f v
f k v
k f v
v DMap k f
m of
    (Maybe (f v)
x, DMap k f
y) -> (Maybe (f v)
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)

{--------------------------------------------------------------------
  Deletion
  [delete] is the inlined version of [deleteWith (\k x -> Nothing)]
--------------------------------------------------------------------}

-- | /O(log n)/. Delete a key and its value from the map. When the key is not
-- a member of the map, the original map is returned.
delete :: forall k f v. GCompare k => k v -> MonoidalDMap k f -> MonoidalDMap k f
delete :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> MonoidalDMap k f
delete k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> DMap k2 f
DMap.delete k v
k DMap k f
m)

-- | /O(log n)/. Update a value at a specific key with the result of the provided function.
-- When the key is not
-- a member of the map, the original map is returned.
adjust :: GCompare k => (f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjust :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjust f v -> f v
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.adjust f v -> f v
f k v
k DMap k f
m)

-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjustWithKey :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjustWithKey k v -> f v -> f v
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
(k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.adjustWithKey k v -> f v -> f v
f k v
k DMap k f
m)

-- | /O(log n)/. A strict version of 'adjustWithKey'.
adjustWithKey' :: GCompare k => (k v -> f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjustWithKey' :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
adjustWithKey' k v -> f v -> f v
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
(k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.adjustWithKey' k v -> f v -> f v
f k v
k DMap k f
m)

-- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@
-- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
-- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
update :: GCompare k => (f v -> Maybe (f v)) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
update :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(f v -> Maybe (f v)) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
update f v -> Maybe (f v)
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.update f v -> Maybe (f v)
f k v
k DMap k f
m)

-- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the
-- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing',
-- the element is deleted. If it is (@'Just' y@), the key @k@ is bound
-- to the new value @y@.
updateWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
updateWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> Maybe (f v))
-> k v -> MonoidalDMap k f -> MonoidalDMap k f
updateWithKey k v -> f v -> Maybe (f v)
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.updateWithKey k v -> f v -> Maybe (f v)
f k v
k DMap k f
m)

-- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
-- The function returns changed value, if it is updated.
-- Returns the original key value if the map entry is deleted.
updateLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> MonoidalDMap k f -> (Maybe (f v), MonoidalDMap k f)
updateLookupWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> Maybe (f v))
-> k v -> MonoidalDMap k f -> (Maybe (f v), MonoidalDMap k f)
updateLookupWithKey k v -> f v -> Maybe (f v)
f k v
k (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(k2 v -> f v -> Maybe (f v))
-> k2 v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
DMap.updateLookupWithKey k v -> f v -> Maybe (f v)
f k v
k DMap k f
m of
    (Maybe (f v)
x, DMap k f
y) -> (Maybe (f v)
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)

-- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.
-- 'alter' can be used to insert, delete, or update a value in a 'Map'.
-- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
alter :: forall k f v. GCompare k => (Maybe (f v) -> Maybe (f v)) -> k v -> MonoidalDMap k f -> MonoidalDMap k f
alter :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(Maybe (f v) -> Maybe (f v))
-> k v -> MonoidalDMap k f -> MonoidalDMap k f
alter Maybe (f v) -> Maybe (f v)
f k v
k (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
(Maybe (f v) -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
DMap.alter Maybe (f v) -> Maybe (f v)
f k v
k DMap k f
m)

{--------------------------------------------------------------------
  Indexing
--------------------------------------------------------------------}

-- | /O(log n)/. Return the /index/ of a key. The index is a number from
-- /0/ up to, but not including, the 'size' of the map. Calls 'error' when
-- the key is not a 'member' of the map.
findIndex :: GCompare k => k v -> MonoidalDMap k f -> Int
findIndex :: forall {k} (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
k v -> MonoidalDMap k f -> Int
findIndex k v
k (MonoidalDMap DMap k f
m)
  = case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe Int
DMap.lookupIndex k v
k DMap k f
m of
      Maybe Int
Nothing  -> forall a. HasCallStack => String -> a
error String
"MonoidalDMap.findIndex: element is not in the map"
      Just Int
idx -> Int
idx

-- | /O(log n)/. Lookup the /index/ of a key. The index is a number from
-- /0/ up to, but not including, the 'size' of the map.
lookupIndex :: forall k f v. GCompare k => k v -> MonoidalDMap k f -> Maybe Int
lookupIndex :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> Maybe Int
lookupIndex k v
k (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe Int
DMap.lookupIndex k v
k DMap k f
m

-- | /O(log n)/. Retrieve an element by /index/. Calls 'error' when an
-- invalid index is used.
elemAt :: Int -> MonoidalDMap k f -> DSum k f
elemAt :: forall {k} (k :: k -> *) (f :: k -> *).
Int -> MonoidalDMap k f -> DSum k f
elemAt Int
i (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
Int -> DMap k2 f -> DSum k2 f
DMap.elemAt Int
i DMap k f
m

-- | /O(log n)/. Update the element at /index/. Does nothing when an
-- invalid index is used.
updateAt :: (forall v. k v -> f v -> Maybe (f v)) -> Int -> MonoidalDMap k f -> MonoidalDMap k f
updateAt :: forall {k} (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> Maybe (f v))
-> Int -> MonoidalDMap k f -> MonoidalDMap k f
updateAt forall (v :: k). k v -> f v -> Maybe (f v)
f Int
i (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> Maybe (f v))
-> Int -> DMap k2 f -> DMap k2 f
DMap.updateAt forall (v :: k). k v -> f v -> Maybe (f v)
f Int
i DMap k f
m)

-- | /O(log n)/. Delete the element at /index/.
-- Defined as (@'deleteAt' i map = 'updateAt' (\k x -> 'Nothing') i map@).
deleteAt :: Int -> MonoidalDMap k f -> MonoidalDMap k f
deleteAt :: forall {k} (k :: k -> *) (f :: k -> *).
Int -> MonoidalDMap k f -> MonoidalDMap k f
deleteAt Int
i (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
Int -> DMap k2 f -> DMap k2 f
DMap.deleteAt Int
i DMap k f
m)

{--------------------------------------------------------------------
  Minimal, Maximal
--------------------------------------------------------------------}

-- | /O(log n)/. The minimal key of the map. Calls 'error' is the map is empty.
findMin :: MonoidalDMap k f -> DSum k f
findMin :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> DSum k f
findMin (MonoidalDMap DMap k f
m) = case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> Maybe (DSum k2 f)
DMap.lookupMin DMap k f
m of
  Just DSum k f
x -> DSum k f
x
  Maybe (DSum k f)
Nothing -> forall a. HasCallStack => String -> a
error String
"MonoidalDMap.findMin: empty map has no minimal element"

lookupMin :: MonoidalDMap k f -> Maybe (DSum k f)
lookupMin :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> Maybe (DSum k f)
lookupMin (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> Maybe (DSum k2 f)
DMap.lookupMin DMap k f
m

-- | /O(log n)/. The maximal key of the map. Calls 'error' is the map is empty.
findMax :: MonoidalDMap k f -> DSum k f
findMax :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> DSum k f
findMax MonoidalDMap k f
m = case forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> Maybe (DSum k f)
lookupMax MonoidalDMap k f
m of
  Just DSum k f
x -> DSum k f
x
  Maybe (DSum k f)
Nothing -> forall a. HasCallStack => String -> a
error String
"Map.findMax: empty map has no maximal element"

lookupMax :: MonoidalDMap k f -> Maybe (DSum k f)
lookupMax :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> Maybe (DSum k f)
lookupMax (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> Maybe (DSum k2 f)
DMap.lookupMax DMap k f
m

-- | /O(log n)/. Delete the minimal key. Returns an empty map if the map is empty.
deleteMin :: MonoidalDMap k f -> MonoidalDMap k f
deleteMin :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> MonoidalDMap k f
deleteMin (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> DMap k2 f
DMap.deleteMin DMap k f
m)

-- | /O(log n)/. Delete the maximal key. Returns an empty map if the map is empty.
deleteMax :: MonoidalDMap k f -> MonoidalDMap k f
deleteMax :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> MonoidalDMap k f
deleteMax (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> DMap k2 f
DMap.deleteMax DMap k f
m)

-- | /O(log n)/. Update the value at the minimal key.
updateMinWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> MonoidalDMap k f -> MonoidalDMap k f
updateMinWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> Maybe (f v))
-> MonoidalDMap k f -> MonoidalDMap k f
updateMinWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> Maybe (f v))
-> DMap k2 f -> DMap k2 f
DMap.updateMinWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f DMap k f
m)

-- | /O(log n)/. Update the value at the maximal key.
updateMaxWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> MonoidalDMap k f -> MonoidalDMap k f
updateMaxWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> Maybe (f v))
-> MonoidalDMap k f -> MonoidalDMap k f
updateMaxWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> Maybe (f v))
-> DMap k2 f -> DMap k2 f
DMap.updateMaxWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f DMap k f
m)

{--------------------------------------------------------------------
  Union.
--------------------------------------------------------------------}

-- | The union of a list of maps, with a combining operation:
--   (@'unionsWithKey' f == 'Prelude.foldl' ('unionWithKey' f) 'empty'@).
unionsWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [MonoidalDMap k f] -> MonoidalDMap k f
unionsWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> [MonoidalDMap k f] -> MonoidalDMap k f
unionsWithKey forall (v :: k). k v -> f v -> f v -> f v
f [MonoidalDMap k f]
ms = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> f v -> f v)
-> [DMap k2 f] -> DMap k2 f
DMap.unionsWithKey forall (v :: k). k v -> f v -> f v -> f v
f (coerce :: forall a b. Coercible a b => a -> b
coerce [MonoidalDMap k f]
ms))

{--------------------------------------------------------------------
  Union with a combining function
--------------------------------------------------------------------}

-- | /O(n+m)/.
-- Union with a combining function.
unionWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> MonoidalDMap k f -> MonoidalDMap k f -> MonoidalDMap k f
unionWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> MonoidalDMap k f -> MonoidalDMap k f -> MonoidalDMap k f
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k f
n) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> f v -> f v)
-> DMap k2 f -> DMap k2 f -> DMap k2 f
DMap.unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f DMap k f
m DMap k f
n)

{--------------------------------------------------------------------
  Difference
--------------------------------------------------------------------}

-- | /O(m * log (n\/m + 1)), m <= n/. Difference of two maps.
-- Return elements of the first map not existing in the second map.
difference :: GCompare k => MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k f
difference :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k f
difference (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k g
n) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
GCompare k2 =>
DMap k2 f -> DMap k2 g -> DMap k2 f
DMap.difference DMap k f
m DMap k g
n)

-- | /O(n+m)/. Difference with a combining function. When two equal keys are
-- encountered, the combining function is applied to the key and both values.
-- If it returns 'Nothing', the element is discarded (proper set difference). If
-- it returns (@'Just' y@), the element is updated with a new value @y@.
differenceWithKey :: GCompare k => (forall v. k v -> f v -> g v -> Maybe (f v)) -> MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k f
differenceWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k f
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k g
n) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> g v -> Maybe (f v))
-> DMap k2 f -> DMap k2 g -> DMap k2 f
DMap.differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f DMap k f
m DMap k g
n)

{--------------------------------------------------------------------
  Intersection
--------------------------------------------------------------------}

-- | /O(m * log (n\/m + 1), m <= n/. Intersection with a combining function.
intersectionWithKey :: GCompare k => (forall v. k v -> f v -> g v -> h v) -> MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k h
intersectionWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> h v)
-> MonoidalDMap k f -> MonoidalDMap k g -> MonoidalDMap k h
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
f (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k g
n) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *)
       (h :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> g v -> h v)
-> DMap k2 f -> DMap k2 g -> DMap k2 h
DMap.intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
f DMap k f
m DMap k g
n)

{--------------------------------------------------------------------
  Submap
--------------------------------------------------------------------}
-- | /O(n+m)/.
-- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' 'eqTagged')@).
--
isSubmapOf :: (GCompare k, Has' Eq k f) => MonoidalDMap k f -> MonoidalDMap k f -> Bool
isSubmapOf :: forall {k} (k :: k -> *) (f :: k -> *).
(GCompare k, Has' Eq k f) =>
MonoidalDMap k f -> MonoidalDMap k f -> Bool
isSubmapOf (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k f
n) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(GCompare k2, Has' Eq k2 f) =>
DMap k2 f -> DMap k2 f -> Bool
DMap.isSubmapOf DMap k f
m DMap k f
n

{- | /O(n+m)/.
 The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if
 all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when
 applied to their respective keys and values.
-}
isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> MonoidalDMap k f -> MonoidalDMap k g -> Bool
isSubmapOfBy :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> MonoidalDMap k f -> MonoidalDMap k g -> Bool
isSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k g
n) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool)
-> DMap k2 f -> DMap k2 g -> Bool
DMap.isSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
m DMap k g
n

-- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
-- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' 'eqTagged'@).
isProperSubmapOf :: (GCompare k, Has' Eq k f) => MonoidalDMap k f -> MonoidalDMap k f -> Bool
isProperSubmapOf :: forall {k} (k :: k -> *) (f :: k -> *).
(GCompare k, Has' Eq k f) =>
MonoidalDMap k f -> MonoidalDMap k f -> Bool
isProperSubmapOf (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k f
n) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(GCompare k2, Has' Eq k2 f) =>
DMap k2 f -> DMap k2 f -> Bool
DMap.isProperSubmapOf DMap k f
m DMap k f
n

{- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
 The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when
 @m1@ and @m2@ are not equal,
 all keys in @m1@ are in @m2@, and when @f@ returns 'True' when
 applied to their respective keys and values.
-}
isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> MonoidalDMap k f -> MonoidalDMap k g -> Bool
isProperSubmapOfBy :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> MonoidalDMap k f -> MonoidalDMap k g -> Bool
isProperSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f (MonoidalDMap DMap k f
m) (MonoidalDMap DMap k g
n) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool)
-> DMap k2 f -> DMap k2 g -> Bool
DMap.isProperSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
m DMap k g
n

{--------------------------------------------------------------------
  Filter and partition
--------------------------------------------------------------------}

-- | /O(n)/. Filter all keys\/values that satisfy the predicate.
filterWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> MonoidalDMap k f -> MonoidalDMap k f
filterWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Bool)
-> MonoidalDMap k f -> MonoidalDMap k f
filterWithKey forall (v :: k). k v -> f v -> Bool
p (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> DMap k2 f
DMap.filterWithKey forall (v :: k). k v -> f v -> Bool
p DMap k f
m)

-- | /O(n)/. Partition the map according to a predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 'split'.
partitionWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> MonoidalDMap k f -> (MonoidalDMap k f, MonoidalDMap k f)
partitionWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Bool)
-> MonoidalDMap k f -> (MonoidalDMap k f, MonoidalDMap k f)
partitionWithKey forall (v :: k). k v -> f v -> Bool
p (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> Bool)
-> DMap k2 f -> (DMap k2 f, DMap k2 f)
DMap.partitionWithKey forall (v :: k). k v -> f v -> Bool
p DMap k f
m of
    (DMap k f
x, DMap k f
y) -> (forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)

-- | /O(n)/. Map keys\/values and collect the 'Just' results.
mapMaybeWithKey :: GCompare k => (forall v. k v -> f v -> Maybe (g v)) -> MonoidalDMap k f -> MonoidalDMap k g
mapMaybeWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Maybe (g v))
-> MonoidalDMap k f -> MonoidalDMap k g
mapMaybeWithKey forall (v :: k). k v -> f v -> Maybe (g v)
f (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> Maybe (g v))
-> DMap k2 f -> DMap k2 g
DMap.mapMaybeWithKey forall (v :: k). k v -> f v -> Maybe (g v)
f DMap k f
m)

-- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
mapEitherWithKey :: GCompare k =>
  (forall v. k v -> f v -> Either (g v) (h v)) -> MonoidalDMap k f -> (MonoidalDMap k g, MonoidalDMap k h)
mapEitherWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Either (g v) (h v))
-> MonoidalDMap k f -> (MonoidalDMap k g, MonoidalDMap k h)
mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
f (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *)
       (h :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> Either (g v) (h v))
-> DMap k2 f -> (DMap k2 g, DMap k2 h)
DMap.mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
f DMap k f
m of
    (DMap k g
x, DMap k h
y) -> (forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k g
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k h
y)

{--------------------------------------------------------------------
  Mapping
--------------------------------------------------------------------}

-- | /O(n)/. Map a function over all values in the map.
map :: (forall v. f v -> g v) -> MonoidalDMap k f -> MonoidalDMap k g
map :: forall {k} (f :: k -> *) (g :: k -> *) (k :: k -> *).
(forall (v :: k). f v -> g v)
-> MonoidalDMap k f -> MonoidalDMap k g
map forall (v :: k). f v -> g v
f (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (f :: k1 -> *) (g :: k1 -> *) (k2 :: k1 -> *).
(forall (v :: k1). f v -> g v) -> DMap k2 f -> DMap k2 g
DMap.map forall (v :: k). f v -> g v
f DMap k f
m)

-- | /O(n)/. Map a function over all values in the map.
mapWithKey :: (forall v. k v -> f v -> g v) -> MonoidalDMap k f -> MonoidalDMap k g
mapWithKey :: forall {k} (k :: k -> *) (f :: k -> *) (g :: k -> *).
(forall (v :: k). k v -> f v -> g v)
-> MonoidalDMap k f -> MonoidalDMap k g
mapWithKey forall (v :: k). k v -> f v -> g v
f (MonoidalDMap DMap k f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> g v) -> DMap k2 f -> DMap k2 g
DMap.mapWithKey forall (v :: k). k v -> f v -> g v
f DMap k f
m)

-- | /O(n)/.
-- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
-- That is, behaves exactly like a regular 'traverse' except that the traversing
-- function also has access to the key associated with a value.
traverseWithKey :: Applicative t => (forall v. k v -> f v -> t (g v)) -> MonoidalDMap k f -> t (MonoidalDMap k g)
traverseWithKey :: forall {k} (t :: * -> *) (k :: k -> *) (f :: k -> *) (g :: k -> *).
Applicative t =>
(forall (v :: k). k v -> f v -> t (g v))
-> MonoidalDMap k f -> t (MonoidalDMap k g)
traverseWithKey forall (v :: k). k v -> f v -> t (g v)
f (MonoidalDMap DMap k f
m) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (t :: * -> *) (k2 :: k1 -> *) (f :: k1 -> *)
       (g :: k1 -> *).
Applicative t =>
(forall (v :: k1). k2 v -> f v -> t (g v))
-> DMap k2 f -> t (DMap k2 g)
DMap.traverseWithKey forall (v :: k). k v -> f v -> t (g v)
f DMap k f
m)

-- | /O(n)/. The function 'mapAccumLWithKey' threads an accumulating
-- argument throught the map in ascending order of keys.
mapAccumLWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> MonoidalDMap k f -> (a, MonoidalDMap k g)
mapAccumLWithKey :: forall {k} a (k :: k -> *) (f :: k -> *) (g :: k -> *).
(forall (v :: k). a -> k v -> f v -> (a, g v))
-> a -> MonoidalDMap k f -> (a, MonoidalDMap k g)
mapAccumLWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f a
x (MonoidalDMap DMap k f
m) =
  case forall {k1} a (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
(forall (v :: k1). a -> k2 v -> f v -> (a, g v))
-> a -> DMap k2 f -> (a, DMap k2 g)
DMap.mapAccumLWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f a
x DMap k f
m of
    (a
y, DMap k g
m') -> (a
y, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k g
m')

-- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating
-- argument through the map in descending order of keys.
mapAccumRWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> MonoidalDMap k f -> (a, MonoidalDMap k g)
mapAccumRWithKey :: forall {k} a (k :: k -> *) (f :: k -> *) (g :: k -> *).
(forall (v :: k). a -> k v -> f v -> (a, g v))
-> a -> MonoidalDMap k f -> (a, MonoidalDMap k g)
mapAccumRWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f a
x (MonoidalDMap DMap k f
m) =
  case forall {k1} a (k2 :: k1 -> *) (f :: k1 -> *) (g :: k1 -> *).
(forall (v :: k1). a -> k2 v -> f v -> (a, g v))
-> a -> DMap k2 f -> (a, DMap k2 g)
DMap.mapAccumRWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f a
x DMap k f
m of
    (a
y, DMap k g
m') -> (a
y, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k g
m')

-- | /O(n*log n)/.
-- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
--
-- The size of the result may be smaller if @f@ maps two or more distinct
-- keys to the same new key.  In this case the associated values will be
-- combined using @c@.
mapKeysWith :: GCompare k2 => (forall v. k2 v -> f v -> f v -> f v) -> (forall v. k1 v -> k2 v) -> MonoidalDMap k1 f -> MonoidalDMap k2 f
mapKeysWith :: forall {k} (k2 :: k -> *) (f :: k -> *) (k1 :: k -> *).
GCompare k2 =>
(forall (v :: k). k2 v -> f v -> f v -> f v)
-> (forall (v :: k). k1 v -> k2 v)
-> MonoidalDMap k1 f
-> MonoidalDMap k2 f
mapKeysWith forall (v :: k). k2 v -> f v -> f v -> f v
c forall (v :: k). k1 v -> k2 v
f (MonoidalDMap DMap k1 f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k} (k2 :: k -> *) (f :: k -> *) (k1 :: k -> *).
GCompare k2 =>
(forall (v :: k). k2 v -> f v -> f v -> f v)
-> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
DMap.mapKeysWith forall (v :: k). k2 v -> f v -> f v -> f v
c forall (v :: k). k1 v -> k2 v
f DMap k1 f
m)

-- | /O(n)/.
-- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@
-- is strictly monotonic.
-- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
-- /The precondition is not checked./
-- Semi-formally, we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapKeysMonotonic f s == mapKeys f s
-- >     where ls = keys s
--
-- This means that @f@ maps distinct original keys to distinct resulting keys.
-- This function has better performance than 'mapKeys'.
mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> MonoidalDMap k1 f -> MonoidalDMap k2 f
mapKeysMonotonic :: forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
(forall (v :: k). k1 v -> k2 v)
-> MonoidalDMap k1 f -> MonoidalDMap k2 f
mapKeysMonotonic forall (v :: k). k1 v -> k2 v
f (MonoidalDMap DMap k1 f
m) = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
(forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
DMap.mapKeysMonotonic forall (v :: k). k1 v -> k2 v
f DMap k1 f
m)

{--------------------------------------------------------------------
  Folds
--------------------------------------------------------------------}

-- | /O(n)/. Post-order fold.  The function will be applied from the lowest
-- value to the highest.
foldrWithKey :: (forall v. k v -> f v -> b -> b) -> b -> MonoidalDMap k f -> b
foldrWithKey :: forall {k} (k :: k -> *) (f :: k -> *) b.
(forall (v :: k). k v -> f v -> b -> b)
-> b -> MonoidalDMap k f -> b
foldrWithKey forall (v :: k). k v -> f v -> b -> b
f b
x (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) b.
(forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b
DMap.foldrWithKey forall (v :: k). k v -> f v -> b -> b
f b
x DMap k f
m

-- | /O(n)/. Pre-order fold.  The function will be applied from the highest
-- value to the lowest.
foldlWithKey :: (forall v. b -> k v -> f v -> b) -> b -> MonoidalDMap k f -> b
foldlWithKey :: forall {k} b (k :: k -> *) (f :: k -> *).
(forall (v :: k). b -> k v -> f v -> b)
-> b -> MonoidalDMap k f -> b
foldlWithKey forall (v :: k). b -> k v -> f v -> b
f b
x (MonoidalDMap DMap k f
m) = forall {k1} b (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). b -> k2 v -> f v -> b) -> b -> DMap k2 f -> b
DMap.foldlWithKey forall (v :: k). b -> k v -> f v -> b
f b
x DMap k f
m

{--------------------------------------------------------------------
  List variations
--------------------------------------------------------------------}

-- | /O(n)/. Return all keys of the map in ascending order.
--
-- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- > keys empty == []

keys  :: MonoidalDMap k f -> [Some k]
keys :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [Some k]
keys (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> [Some k2]
DMap.keys DMap k f
m

-- | /O(n)/. Return all key\/value pairs in the map in ascending key order.
assocs :: MonoidalDMap k f -> [DSum k f]
assocs :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [DSum k f]
assocs (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.assocs DMap k f
m

{--------------------------------------------------------------------
  Lists
  use [foldlStrict] to reduce demand on the control-stack
--------------------------------------------------------------------}

-- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'.
fromListWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> MonoidalDMap k f
fromListWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> MonoidalDMap k f
fromListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> f v -> f v)
-> [DSum k2 f] -> DMap k2 f
DMap.fromListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs)

-- | /O(n)/. Convert to a list of key\/value pairs.
toList :: MonoidalDMap k f -> [DSum k f]
toList :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [DSum k f]
toList (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap k f
m

-- | /O(n)/. Convert to an ascending list.
toAscList :: MonoidalDMap k f -> [DSum k f]
toAscList :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [DSum k f]
toAscList (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toAscList DMap k f
m

-- | /O(n)/. Convert to a descending list.
toDescList :: MonoidalDMap k f -> [DSum k f]
toDescList :: forall {k} (k :: k -> *) (f :: k -> *).
MonoidalDMap k f -> [DSum k f]
toDescList (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toDescList DMap k f
m

{--------------------------------------------------------------------
  Building trees from ascending/descending lists can be done in linear time.

  Note that if [xs] is ascending that:
    fromAscList xs       == fromList xs
    fromAscListWith f xs == fromListWith f xs
--------------------------------------------------------------------}

-- | /O(n)/. Build a map from an ascending list in linear time with a
-- combining function for equal keys.
-- /The precondition (input list is ascending) is not checked./
fromAscListWithKey :: GEq k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> MonoidalDMap k f
fromAscListWithKey :: forall {k} (k :: k -> *) (f :: k -> *).
GEq k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> MonoidalDMap k f
fromAscListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs = forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GEq k2 =>
(forall (v :: k1). k2 v -> f v -> f v -> f v)
-> [DSum k2 f] -> DMap k2 f
DMap.fromAscListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs)

{--------------------------------------------------------------------
  Split
--------------------------------------------------------------------}

-- | /O(log n)/. The expression (@'split' k map@) is a pair @(map1,map2)@ where
-- the keys in @map1@ are smaller than @k@ and the keys in @map2@ larger than @k@.
-- Any key equal to @k@ is found in neither @map1@ nor @map2@.
split :: forall k f v. GCompare k => k v -> MonoidalDMap k f -> (MonoidalDMap k f, MonoidalDMap k f)
split :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> MonoidalDMap k f -> (MonoidalDMap k f, MonoidalDMap k f)
split k v
k (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> (DMap k2 f, DMap k2 f)
DMap.split k v
k DMap k f
m of
    (DMap k f
x, DMap k f
y) -> (forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)
{-# INLINABLE split #-}

-- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
-- like 'split' but also returns @'lookup' k map@.
splitLookup :: forall k f v. GCompare k => k v -> MonoidalDMap k f -> (MonoidalDMap k f, Maybe (f v), MonoidalDMap k f)
splitLookup :: forall {k} (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v
-> MonoidalDMap k f
-> (MonoidalDMap k f, Maybe (f v), MonoidalDMap k f)
splitLookup k v
k (MonoidalDMap DMap k f
m) =
  case forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> (DMap k2 f, Maybe (f v), DMap k2 f)
DMap.splitLookup k v
k DMap k f
m of
    (DMap k f
x, Maybe (f v)
v, DMap k f
y) -> (forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, Maybe (f v)
v, forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
y)

-- | /O(n)/. Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format. See 'showTreeWith'.
showTree :: (GShow k, Has' Show k f) => MonoidalDMap k f -> String
showTree :: forall {k} (k :: k -> *) (f :: k -> *).
(GShow k, Has' Show k f) =>
MonoidalDMap k f -> String
showTree (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(GShow k2, Has' Show k2 f) =>
DMap k2 f -> String
DMap.showTree DMap k f
m

{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
 the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
 @wide@ is 'True', an extra wide version is shown.
-}
showTreeWith :: (forall v. k v -> f v -> String) -> Bool -> Bool -> MonoidalDMap k f -> String
showTreeWith :: forall {k} (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> String)
-> Bool -> Bool -> MonoidalDMap k f -> String
showTreeWith forall (v :: k). k v -> f v -> String
showElem Bool
hang Bool
wide (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> String)
-> Bool -> Bool -> DMap k2 f -> String
DMap.showTreeWith forall (v :: k). k v -> f v -> String
showElem Bool
hang Bool
wide DMap k f
m

{--------------------------------------------------------------------
  Assertions
--------------------------------------------------------------------}

-- | /O(n)/. Test if the internal map structure is valid.
valid :: GCompare k => MonoidalDMap k f -> Bool
valid :: forall {k} (k :: k -> *) (f :: k -> *).
GCompare k =>
MonoidalDMap k f -> Bool
valid (MonoidalDMap DMap k f
m) = forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
DMap k2 f -> Bool
DMap.valid DMap k f
m