{-# 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.Kind (Type)
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 -> Type) (g :: k -> Type) = 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 f a -> f a -> Maybe (a :~: a)
forall (a :: k) (b :: k). f a -> f b -> Maybe (a :~: b)
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
forall (c :: * -> Constraint) (g :: 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 g a -> g a -> Bool
forall a. Eq a => a -> a -> Bool
== g a
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 f a -> f a -> GOrdering a a
forall (a :: k) (b :: k). f a -> f b -> GOrdering a b
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
forall (c :: * -> Constraint) (g :: k -> *) (f :: k -> *) (a :: k)
       r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Ord @g f a
k (g a -> g a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare g a
v g a
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 Int -> Int -> Bool
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
forall (c :: * -> Constraint) (t :: k -> *) (a :: k) r.
ForallF c t =>
(c (t a) => r) -> r
whichever @Show @f @a (Int -> f a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
0 f a
k)
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" :=> "
    ShowS -> ShowS -> ShowS
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
forall (c :: * -> Constraint) (g :: k -> *) (f :: k -> *) (a :: k)
       r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Show @g f a
k (Int -> g a -> ShowS
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 = Bool -> ReadS (FakeDSum f g) -> ReadS (FakeDSum f g)
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1) (ReadS (FakeDSum f g) -> ReadS (FakeDSum f g))
-> ReadS (FakeDSum f g) -> ReadS (FakeDSum f g)
forall a b. (a -> b) -> a -> b
$ \String
s ->
    [[(FakeDSum f g, String)]] -> [(FakeDSum f g, String)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
      [ Some f
-> (forall (a :: k). f a -> [(FakeDSum f g, String)])
-> [(FakeDSum f g, String)]
forall {k} (tag :: k -> *) b.
Some tag -> (forall (a :: k). tag a -> b) -> b
getGReadResult Some f
withTag ((forall (a :: k). f a -> [(FakeDSum f g, String)])
 -> [(FakeDSum f g, String)])
-> (forall (a :: k). f a -> [(FakeDSum f g, String)])
-> [(FakeDSum f g, String)]
forall a b. (a -> b) -> a -> b
$ \f a
tag ->
          [ (DSum f g -> FakeDSum f g
forall {k} (f :: k -> *) (g :: k -> *). DSum f g -> FakeDSum f g
FakeDSum (f a
tag f a -> g a -> DSum f g
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
forall (c :: * -> Constraint) (g :: k -> *) (f :: k -> *) (a :: k)
       r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Read @g f a
tag ((Read (g a) => [(g a, String)]) -> [(g a, String)])
-> (Read (g a) => [(g a, String)]) -> [(g a, String)]
forall a b. (a -> b) -> a -> b
$ Int -> ReadS (g a)
forall a. Read a => Int -> ReadS a
readsPrec Int
1 String
rest'
          ]
      | (Some f
withTag, String
rest) <- Int -> GReadS f
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' =
    ([DSum f g] -> [FakeDSum f g]
forall a b. Coercible a b => a -> b
coerce (DMap f g -> [DSum f g]
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m) :: [FakeDSum f g]) [FakeDSum f g] -> [FakeDSum f g] -> Bool
forall a. Eq a => a -> a -> Bool
== ([DSum f g] -> [FakeDSum f g]
forall a b. Coercible a b => a -> b
coerce (DMap f g -> [DSum f g]
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') =
    [FakeDSum f g] -> [FakeDSum f g] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([DSum f g] -> [FakeDSum f g]
forall a b. Coercible a b => a -> b
coerce (DMap f g -> [DSum f g]
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> [DSum k2 f]
DMap.toList DMap f g
m) :: [FakeDSum f g]) ([DSum f g] -> [FakeDSum f g]
forall a b. Coercible a b => a -> b
coerce (DMap f g -> [DSum f g]
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
pInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10)
        ( String -> ShowS
showString String
"fromList "
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [FakeDSum k f] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 ([DSum k f] -> [FakeDSum k f]
forall a b. Coercible a b => a -> b
coerce (MonoidalDMap k f -> [DSum k f]
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 = ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f))
-> ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f))
-> ReadPrec (MonoidalDMap k f) -> ReadPrec (MonoidalDMap k f)
forall a b. (a -> b) -> a -> b
$ do
    Ident "fromList" <- ReadPrec Lexeme
lexP
    xs <- readPrec
    return . MonoidalDMap . DMap.fromList $ coerce (xs :: [FakeDSum k f])
  readListPrec :: ReadPrec [MonoidalDMap k f]
readListPrec = ReadPrec [MonoidalDMap k f]
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) =
    DMap f g -> MonoidalDMap f g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). f v -> g v -> g v -> g v)
-> DMap f g -> DMap f g -> DMap f g
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
forall (c :: * -> Constraint) (g :: 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 g v -> g v -> g v
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 = MonoidalDMap f g
forall {k} (k :: k -> *) (f :: k -> *). MonoidalDMap k f
empty

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 = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
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 = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (k v -> f v -> DMap k f
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) = DMap k f -> Bool
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) = DMap k f -> Int
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) = k v -> DMap k f -> Maybe (f v)
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 DMap k f -> (DSum k f, DMap k f)
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, DMap k f -> MonoidalDMap k f
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 DMap k f -> Maybe (DSum k f, DMap k f)
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 -> Maybe (DSum k f, MonoidalDMap k f)
forall a. Maybe a
Nothing
    Just (DSum k f
x, DMap k f
m') -> (DSum k f, MonoidalDMap k f) -> Maybe (DSum k f, MonoidalDMap k f)
forall a. a -> Maybe a
Just (DSum k f
x, DMap k f -> MonoidalDMap k f
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 DMap k f -> Maybe (DSum k f, DMap k f)
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 -> Maybe (DSum k f, MonoidalDMap k f)
forall a. Maybe a
Nothing
    Just (DSum k f
x, DMap k f
m') -> (DSum k f, MonoidalDMap k f) -> Maybe (DSum k f, MonoidalDMap k f)
forall a. a -> Maybe a
Just (DSum k f
x, DMap k f -> MonoidalDMap k f
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 DMap k f -> (DSum k f, DMap k f)
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, DMap k f -> MonoidalDMap k f
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 = Maybe (f a) -> Bool
forall a. Maybe a -> Bool
isJust (Maybe (f a) -> Bool)
-> (MonoidalDMap k f -> Maybe (f a)) -> MonoidalDMap k f -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k a -> MonoidalDMap k f -> Maybe (f a)
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 (k v -> MonoidalDMap k f -> Bool
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 k v -> MonoidalDMap k f -> Maybe (f v)
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 -> String -> f v
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 k v -> MonoidalDMap k f -> Maybe (f v)
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (k v -> f v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
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 (k v -> f v -> f v -> f v)
-> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
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, DMap k f -> MonoidalDMap k f
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 (k v -> f v -> f v -> f v)
-> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
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, DMap k f -> MonoidalDMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (k v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((f v -> f v) -> k v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
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 (k v -> f v -> Maybe (f v))
-> k v -> DMap k f -> (Maybe (f v), DMap k f)
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, DMap k f -> MonoidalDMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
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 k v -> DMap k f -> Maybe Int
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  -> String -> Int
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) = k v -> DMap k f -> Maybe Int
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) = Int -> DMap k f -> DSum k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> Maybe (f v))
-> Int -> DMap k f -> DMap k f
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 k v -> f v -> Maybe (f v)
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (Int -> DMap k f -> DMap k f
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 DMap k f -> Maybe (DSum k f)
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 -> String -> DSum k f
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) = DMap k f -> Maybe (DSum k f)
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 MonoidalDMap k f -> Maybe (DSum k f)
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 -> String -> DSum k f
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) = DMap k f -> Maybe (DSum k f)
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (DMap k f -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> Maybe (f v))
-> DMap k f -> DMap k f
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> Maybe (f v))
-> DMap k2 f -> DMap k2 f
DMap.updateMinWithKey k v -> f v -> Maybe (f v)
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> Maybe (f v))
-> DMap k f -> DMap k f
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> Maybe (f v))
-> DMap k2 f -> DMap k2 f
DMap.updateMaxWithKey k v -> f v -> Maybe (f v)
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 = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> f v -> f v)
-> [DMap k f] -> DMap k f
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 k v -> f v -> f v -> f v
forall (v :: k). k v -> f v -> f v -> f v
f ([MonoidalDMap k f] -> [DMap k f]
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
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 k v -> f v -> f v -> f v
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap (DMap k f -> DMap k g -> DMap k f
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
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 k v -> f v -> g v -> Maybe (f v)
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) = DMap k h -> MonoidalDMap k h
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
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 k v -> f v -> g v -> h v
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) = DMap k f -> DMap k f -> Bool
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 (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
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 k v -> k v -> f v -> g v -> Bool
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) = DMap k f -> DMap k f -> Bool
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 (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
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 k v -> k v -> f v -> g v -> Bool
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) = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> Bool) -> DMap k f -> DMap k f
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
(forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> DMap k2 f
DMap.filterWithKey k v -> f v -> Bool
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 (v :: k). k v -> f v -> Bool)
-> DMap k f -> (DMap k f, DMap k f)
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 k v -> f v -> Bool
forall (v :: k). k v -> f v -> Bool
p DMap k f
m of
    (DMap k f
x, DMap k f
y) -> (DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, DMap k f -> MonoidalDMap k f
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) = DMap k g -> MonoidalDMap k g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> Maybe (g v))
-> DMap k f -> DMap k g
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 k v -> f v -> Maybe (g v)
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 (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
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 k v -> f v -> Either (g v) (h v)
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) -> (DMap k g -> MonoidalDMap k g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k g
x, DMap k h -> MonoidalDMap k h
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) = DMap k g -> MonoidalDMap k g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
forall {k1} (f :: k1 -> *) (g :: k1 -> *) (k2 :: k1 -> *).
(forall (v :: k1). f v -> g v) -> DMap k2 f -> DMap k2 g
DMap.map f v -> g v
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) = DMap k g -> MonoidalDMap k g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
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 k v -> f v -> g v
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) = (DMap k g -> MonoidalDMap k g)
-> t (DMap k g) -> t (MonoidalDMap k g)
forall a b. (a -> b) -> t a -> t b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap DMap k g -> MonoidalDMap k g
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> t (g v))
-> DMap k f -> t (DMap k g)
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 k v -> f v -> t (g v)
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 (v :: k). a -> k v -> f v -> (a, g v))
-> a -> DMap k f -> (a, DMap k g)
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 a -> k v -> f v -> (a, g v)
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, DMap k g -> MonoidalDMap k g
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 (v :: k). a -> k v -> f v -> (a, g v))
-> a -> DMap k f -> (a, DMap k g)
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 a -> k v -> f v -> (a, g v)
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, DMap k g -> MonoidalDMap k g
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) = DMap k2 f -> MonoidalDMap k2 f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k2 v -> f v -> f v -> f v)
-> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
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 k2 v -> f v -> f v -> f v
forall (v :: k). k2 v -> f v -> f v -> f v
c k1 v -> k2 v
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) = DMap k2 f -> MonoidalDMap k2 f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
forall {k} (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
(forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
DMap.mapKeysMonotonic k1 v -> k2 v
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 (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *) b.
(forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b
DMap.foldrWithKey k v -> f v -> b -> b
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 (v :: k). b -> k v -> f v -> b) -> b -> DMap k f -> b
forall {k1} b (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). b -> k2 v -> f v -> b) -> b -> DMap k2 f -> b
DMap.foldlWithKey b -> k v -> f v -> b
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) = DMap k f -> [Some k]
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) = DMap k f -> [DSum k f]
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 = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
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 k v -> f v -> f v -> f v
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) = DMap k f -> [DSum k f]
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) = DMap k f -> [DSum k f]
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) = DMap k f -> [DSum k f]
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 = DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap ((forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
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 k v -> f v -> f v -> f v
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 k v -> DMap k f -> (DMap k f, DMap k f)
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) -> (DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, DMap k f -> MonoidalDMap k f
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 k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
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) -> (DMap k f -> MonoidalDMap k f
forall k (f :: k -> *) (g :: k -> *). DMap f g -> MonoidalDMap f g
MonoidalDMap DMap k f
x, Maybe (f v)
v, DMap k f -> MonoidalDMap k f
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) = DMap k f -> String
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 (v :: k). k v -> f v -> String)
-> Bool -> Bool -> DMap k f -> String
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
(forall (v :: k1). k2 v -> f v -> String)
-> Bool -> Bool -> DMap k2 f -> String
DMap.showTreeWith k v -> f v -> String
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) = DMap k f -> Bool
forall {k1} (k2 :: k1 -> *) (f :: k1 -> *).
GCompare k2 =>
DMap k2 f -> Bool
DMap.valid DMap k f
m