-- incomplete patterns in 'fromDistinct{Asc,Desc}List'
{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}

-- | A structure mapping unique keys to values
module Mini.Data.Map (
  -- * Type
  Map,

  -- * Primitive Recursion
  map,

  -- * Construction
  empty,
  singleton,
  fromList,
  fromListWith,
  fromListWithKey,
  fromAscList,
  fromAscListWith,
  fromAscListWithKey,
  fromDescList,
  fromDescListWith,
  fromDescListWithKey,
  fromDistinctAscList,
  fromDistinctDescList,

  -- * Combination
  compose,
  difference,
  differenceWith,
  differenceWithKey,
  intersection,
  intersectionWith,
  intersectionWithKey,
  union,
  unionWith,
  unionWithKey,
  unions,
  unionsWith,
  unionsWithKey,

  -- * Conversion
  toAscList,
  toDescList,

  -- * Fold
  foldlWithKey,
  foldrWithKey,

  -- * Modification
  adjust,
  adjustWithKey,
  adjustMax,
  adjustMaxWithKey,
  adjustMin,
  adjustMinWithKey,
  delete,
  deleteMax,
  deleteMin,
  filter,
  filterWithKey,
  insert,
  insertWith,
  insertWithKey,
  update,
  updateWithKey,
  updateMax,
  updateMaxWithKey,
  updateMin,
  updateMinWithKey,

  -- * Partition
  partition,
  partitionWithKey,
  split,
  splitMax,
  splitMin,

  -- * Query
  disjoint,
  isSubmapOf,
  isSubmapOfBy,
  lookup,
  lookupGE,
  lookupGT,
  lookupLE,
  lookupLT,
  lookupMax,
  lookupMin,
  member,
  null,
  size,

  -- * Traversal
  fmapWithKey,
  traverseWithKey,

  -- * Validation
  valid,

  -- * Examples
  -- $examples
) where

import Control.Applicative (
  liftA2,
  (<|>),
 )
import Data.Bifunctor (
  bimap,
  first,
  second,
 )
import Data.Bool (
  bool,
 )
import Data.Function (
  on,
 )
import Prelude (
  Applicative,
  Bool (
    False,
    True
  ),
  Eq,
  Foldable,
  Functor,
  Int,
  Maybe (
    Just,
    Nothing
  ),
  Monoid,
  Ord,
  Ordering (
    EQ,
    GT,
    LT
  ),
  Semigroup,
  Show,
  Traversable,
  compare,
  const,
  div,
  error,
  flip,
  fmap,
  foldl,
  foldr,
  fst,
  length,
  max,
  maybe,
  mempty,
  not,
  pure,
  show,
  splitAt,
  traverse,
  uncurry,
  until,
  ($),
  (&&),
  (*),
  (+),
  (-),
  (.),
  (<),
  (<$>),
  (<*>),
  (<>),
  (==),
  (>),
  (||),
 )

{-
 - Type
 -}

-- | A map from keys /k/ to values /a/, internally structured as an AVL tree
data Map k a
  = -- | Empty bin
    E
  | -- | Left-heavy bin
    L (Map k a) k a (Map k a)
  | -- | Balanced bin
    B (Map k a) k a (Map k a)
  | -- | Right-heavy bin
    R (Map k a) k a (Map k a)

instance (Eq k, Eq a) => Eq (Map k a) where
  == :: Map k a -> Map k a -> Bool
(==) = [(k, a)] -> [(k, a)] -> Bool
forall a. Eq a => a -> a -> Bool
(==) ([(k, a)] -> [(k, a)] -> Bool)
-> (Map k a -> [(k, a)]) -> Map k a -> Map k a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
toAscList

instance (Ord k, Ord a) => Ord (Map k a) where
  compare :: Map k a -> Map k a -> Ordering
compare = [(k, a)] -> [(k, a)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([(k, a)] -> [(k, a)] -> Ordering)
-> (Map k a -> [(k, a)]) -> Map k a -> Map k a -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
toAscList

instance (Show k, Show a) => Show (Map k a) where
  show :: Map k a -> String
show = [(k, a)] -> String
forall a. Show a => a -> String
show ([(k, a)] -> String) -> (Map k a -> [(k, a)]) -> Map k a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
toAscList

instance Functor (Map k) where
  fmap :: forall a b. (a -> b) -> Map k a -> Map k b
fmap = (k -> a -> b) -> Map k a -> Map k b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
fmapWithKey ((k -> a -> b) -> Map k a -> Map k b)
-> ((a -> b) -> k -> a -> b) -> (a -> b) -> Map k a -> Map k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> k -> a -> b
forall a b. a -> b -> a
const

instance Foldable (Map k) where
  foldr :: forall a b. (a -> b -> b) -> b -> Map k a -> b
foldr = (k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey ((k -> a -> b -> b) -> b -> Map k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> Map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> k -> a -> b -> b
forall a b. a -> b -> a
const

instance Traversable (Map k) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map k a -> f (Map k b)
traverse = (k -> a -> f b) -> Map k a -> f (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey ((k -> a -> f b) -> Map k a -> f (Map k b))
-> ((a -> f b) -> k -> a -> f b)
-> (a -> f b)
-> Map k a
-> f (Map k b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const

instance (Ord k) => Semigroup (Map k a) where
  <> :: Map k a -> Map k a -> Map k a
(<>) = Map k a -> Map k a -> Map k a
forall k a. Ord k => Map k a -> Map k a -> Map k a
union

instance (Ord k) => Monoid (Map k a) where
  mempty :: Map k a
mempty = Map k a
forall k a. Map k a
empty

{-
 - Primitive recursion
 -}

-- | Primitive recursion on maps (internally structured as trees)
map
  :: b
  -- ^ Value yielded in case of empty node
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Function applied in case of non-empty node:
  -- left child, key, value, right child, left recursion, right recursion
  -- (keys are lesser to the left, greater to the right)
  -> Map k a
  -- ^ Object of the case analysis
  -> b
map :: forall b k a.
b -> (Map k a -> k -> a -> Map k a -> b -> b -> b) -> Map k a -> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
f

-- Primitive recursion on maps
map'
  :: b
  -- ^ Value yielded in case of empty node
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Function applied in case of left-heavy node:
  -- left child, key, value, right child, left recursion, right recursion
  -- (keys are lesser to the left, greater to the right)
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Function applied in case of balanced node:
  -- left child, key, value, right child, left recursion, right recursion
  -- (keys are lesser to the left, greater to the right)
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Function applied in case of right-heavy node:
  -- left child, key, value, right child, left recursion, right recursion
  -- (keys are lesser to the left, greater to the right)
  -> Map k a
  -- ^ Object of the case analysis
  -> b
map' :: forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a
E = b
e
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (L Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (B Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (R Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)

{-
 - Construction
 -}

-- | /O(1)/ The empty map
empty :: Map k a
empty :: forall k a. Map k a
empty = Map k a
forall k a. Map k a
E

-- | /O(1)/ Make a map with a single bin
singleton :: k -> a -> Map k a
singleton :: forall k a. k -> a -> Map k a
singleton k
k a
a = Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
forall k a. Map k a
E

-- | /O(n log n)/ Make a map from a tail-biased list of @(key, value)@ pairs
fromList :: (Ord k) => [(k, a)] -> Map k a
fromList :: forall k a. Ord k => [(k, a)] -> Map k a
fromList = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey ((k -> a -> a -> a) -> [(k, a)] -> Map k a)
-> (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const a -> a -> a
forall a b. a -> b -> a
const

-- | /O(n log n)/ Make a map from a list of pairs, combining matching keys
fromListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWith :: forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWith = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey ((k -> a -> a -> a) -> [(k, a)] -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> [(k, a)]
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | /O(n log n)/ Make a map from a list of pairs, combining matching keys
fromListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey :: forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey k -> a -> a -> a
f = (Map k a -> (k, a) -> Map k a) -> Map k a -> [(k, a)] -> Map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (((k, a) -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((k, a) -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a)
-> ((k -> a -> Map k a -> Map k a) -> (k, a) -> Map k a -> Map k a)
-> (k -> a -> Map k a -> Map k a)
-> Map k a
-> (k, a)
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Map k a -> Map k a) -> (k, a) -> Map k a -> Map k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((k -> a -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a)
-> (k -> a -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
f) Map k a
forall k a. Map k a
empty

-- | /O(n)/ Make a map from a tail-biased list of key-sorted pairs
fromAscList :: (Eq k) => [(k, a)] -> Map k a
fromAscList :: forall k a. Eq k => [(k, a)] -> Map k a
fromAscList = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList ([(k, a)] -> Map k a)
-> ([(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> [(k, a)]
forall k a. Eq k => [(k, a)] -> [(k, a)]
essence

-- | /O(n)/ Make a map from a list of key-sorted pairs, combining matching keys
fromAscListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWith :: forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWith = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWithKey ((k -> a -> a -> a) -> [(k, a)] -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> [(k, a)]
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | /O(n)/ Make a map from a list of key-sorted pairs, combining matching keys
fromAscListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWithKey :: forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWithKey k -> a -> a -> a
f = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList ([(k, a)] -> Map k a)
-> ([(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
essenceWith k -> a -> a -> a
f

-- | /O(n)/ Make a map from a tail-biased list of key-sorted pairs
fromDescList :: (Eq k) => [(k, a)] -> Map k a
fromDescList :: forall k a. Eq k => [(k, a)] -> Map k a
fromDescList = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctDescList ([(k, a)] -> Map k a)
-> ([(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> [(k, a)]
forall k a. Eq k => [(k, a)] -> [(k, a)]
essence

-- | /O(n)/ Make a map from a list of key-sorted pairs, combining matching keys
fromDescListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWith :: forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWith = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWithKey ((k -> a -> a -> a) -> [(k, a)] -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> [(k, a)]
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | /O(n)/ Make a map from a list of key-sorted pairs, combining matching keys
fromDescListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWithKey :: forall k a. Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWithKey k -> a -> a -> a
f = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctDescList ([(k, a)] -> Map k a)
-> ([(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
essenceWith k -> a -> a -> a
f

-- | /O(n)/ Make a map from a sorted list of key-distinct pairs
fromDistinctAscList :: [(k, a)] -> Map k a
fromDistinctAscList :: forall k a. [(k, a)] -> Map k a
fromDistinctAscList = [(k, a)] -> Int -> Map k a
forall {k} {a}. [(k, a)] -> Int -> Map k a
go ([(k, a)] -> Int -> Map k a)
-> ([(k, a)] -> Int) -> [(k, a)] -> Map k a
forall a b.
([(k, a)] -> a -> b) -> ([(k, a)] -> a) -> [(k, a)] -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [(k, a)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
power
 where
  go :: [(k, a)] -> Int -> Map k a
go [] Int
_ = Map k a
forall k a. Map k a
E
  go [(k
k, a
a)] Int
_ = Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
forall k a. Map k a
E
  go [(k, a)]
kas Int
n =
    let len :: Int
len = [(k, a)] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(k, a)]
kas
        n' :: Int
n' = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
        c :: Map k a -> k -> a -> Map k a -> Map k a
c = (Map k a -> k -> a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a)
-> Bool
-> Map k a
-> k
-> a
-> Map k a
-> Map k a
forall a. a -> a -> Bool -> a
bool Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Bool -> Map k a -> k -> a -> Map k a -> Map k a)
-> Bool -> Map k a -> k -> a -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Int
len Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n
        ([(k, a)]
l, (k
k, a
a) : [(k, a)]
r) = Int -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. Int -> [a] -> ([a], [a])
splitAt (Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [(k, a)]
kas
     in Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
c ([(k, a)] -> Int -> Map k a
go [(k, a)]
l Int
n') k
k a
a ([(k, a)] -> Int -> Map k a
go [(k, a)]
r Int
n')

-- | /O(n)/ Make a map from a sorted list of key-distinct pairs
fromDistinctDescList :: [(k, a)] -> Map k a
fromDistinctDescList :: forall k a. [(k, a)] -> Map k a
fromDistinctDescList = [(k, a)] -> Int -> Map k a
forall {k} {a}. [(k, a)] -> Int -> Map k a
go ([(k, a)] -> Int -> Map k a)
-> ([(k, a)] -> Int) -> [(k, a)] -> Map k a
forall a b.
([(k, a)] -> a -> b) -> ([(k, a)] -> a) -> [(k, a)] -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [(k, a)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
power
 where
  go :: [(k, a)] -> Int -> Map k a
go [] Int
_ = Map k a
forall k a. Map k a
E
  go [(k
k, a
a)] Int
_ = Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
forall k a. Map k a
E
  go [(k, a)]
kas Int
n =
    let len :: Int
len = [(k, a)] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(k, a)]
kas
        n' :: Int
n' = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
        c :: Map k a -> k -> a -> Map k a -> Map k a
c = (Map k a -> k -> a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a)
-> Bool
-> Map k a
-> k
-> a
-> Map k a
-> Map k a
forall a. a -> a -> Bool -> a
bool Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Bool -> Map k a -> k -> a -> Map k a -> Map k a)
-> Bool -> Map k a -> k -> a -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Int
len Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n
        ([(k, a)]
l, (k
k, a
a) : [(k, a)]
r) = Int -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. Int -> [a] -> ([a], [a])
splitAt (Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [(k, a)]
kas
     in Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
c ([(k, a)] -> Int -> Map k a
go [(k, a)]
r Int
n') k
k a
a ([(k, a)] -> Int -> Map k a
go [(k, a)]
l Int
n')

{-
 - Combination
 -}

-- | /O(n log m)/ Compose the keys of one set with the values of another
compose :: (Ord b) => Map b c -> Map a b -> Map a c
compose :: forall b c a. Ord b => Map b c -> Map a b -> Map a c
compose Map b c
t1 Map a b
t2 = Map a c
-> (Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c)
-> (Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c)
-> (Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c)
-> Map b c
-> Map a c
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map a c
forall k a. Map k a
empty Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map a c
go Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map a c
go Map b c -> b -> c -> Map b c -> Map a c -> Map a c -> Map a c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map a c
go Map b c
t1
 where
  go :: p -> p -> p -> p -> p -> p -> Map a c
go p
_ p
_ p
_ p
_ p
_ p
_ =
    [(a, c)] -> Map a c
forall k a. [(k, a)] -> Map k a
fromDistinctAscList ([(a, c)] -> Map a c) -> [(a, c)] -> Map a c
forall a b. (a -> b) -> a -> b
$
      (a -> b -> [(a, c)] -> [(a, c)]) -> [(a, c)] -> Map a b -> [(a, c)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
        (\a
a b
b [(a, c)]
ac -> [(a, c)] -> (c -> [(a, c)]) -> Maybe c -> [(a, c)]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [(a, c)]
ac (\c
c -> (a
a, c
c) (a, c) -> [(a, c)] -> [(a, c)]
forall a. a -> [a] -> [a]
: [(a, c)]
ac) (Maybe c -> [(a, c)]) -> Maybe c -> [(a, c)]
forall a b. (a -> b) -> a -> b
$ b -> Map b c -> Maybe c
forall k a. Ord k => k -> Map k a -> Maybe a
lookup b
b Map b c
t1)
        []
        Map a b
t2

-- | /O(m log n)/ Subtract a map by another via key matching
difference :: (Ord k) => Map k a -> Map k b -> Map k a
difference :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
difference Map k a
t1 Map k b
t2 = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
forall k a. Map k a
empty Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a
t1
 where
  go :: p -> p -> p -> p -> p -> p -> Map k a
go p
_ p
_ p
_ p
_ p
_ p
_ = (k -> b -> Map k a -> Map k a) -> Map k a -> Map k b -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k b
_ Map k a
b -> k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete k
k Map k a
b) Map k a
t1 Map k b
t2

-- | /O(m log n)/ Subtract a map by another, updating bins of matching keys
differenceWith
  :: (Ord k) => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWith :: forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWith = (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey ((k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a)
-> ((a -> b -> Maybe a) -> k -> a -> b -> Maybe a)
-> (a -> b -> Maybe a)
-> Map k a
-> Map k b
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> Maybe a) -> k -> a -> b -> Maybe a
forall a b. a -> b -> a
const

-- | /O(m log n)/ Subtract a map by another, updating bins of matching keys
differenceWithKey
  :: (Ord k) => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey :: forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey k -> a -> b -> Maybe a
f Map k a
t1 Map k b
t2 = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
forall k a. Map k a
empty Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a
t1
 where
  go :: p -> p -> p -> p -> p -> p -> Map k a
go p
_ p
_ p
_ p
_ p
_ p
_ =
    (k -> b -> Map k a -> Map k a) -> Map k a -> Map k b -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
      ( \k
k b
b Map k a
t' ->
          Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
            Map k a
t'
            ( \a
a ->
                Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
                  (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k Map k a
t')
                  (\a
a' -> k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a' Map k a
t')
                  (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> b -> Maybe a
f k
k a
a b
b
            )
            (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k a
t1
      )
      Map k a
t1
      Map k b
t2

-- | /O(n log m)/ Intersect a map with another via left-biased key matching
intersection :: (Ord k) => Map k a -> Map k b -> Map k a
intersection :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
intersection = (k -> a -> b -> a) -> Map k a -> Map k b -> Map k a
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey ((k -> a -> b -> a) -> Map k a -> Map k b -> Map k a)
-> (k -> a -> b -> a) -> Map k a -> Map k b -> Map k a
forall a b. (a -> b) -> a -> b
$ (a -> b -> a) -> k -> a -> b -> a
forall a b. a -> b -> a
const a -> b -> a
forall a b. a -> b -> a
const

-- | /O(n log m)/ Intersect a map with another by key matching, combining values
intersectionWith :: (Ord k) => (a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith :: forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith = (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey ((k -> a -> b -> c) -> Map k a -> Map k b -> Map k c)
-> ((a -> b -> c) -> k -> a -> b -> c)
-> (a -> b -> c)
-> Map k a
-> Map k b
-> Map k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> c) -> k -> a -> b -> c
forall a b. a -> b -> a
const

-- | /O(n log m)/ Intersect a map with another by key matching, combining values
intersectionWithKey
  :: (Ord k) => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey :: forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey k -> a -> b -> c
f Map k a
t1 Map k b
t2 = Map k c
-> (Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c)
-> (Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c)
-> (Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c)
-> Map k b
-> Map k c
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k c
forall k a. Map k a
empty Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k c
go Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k c
go Map k b -> k -> b -> Map k b -> Map k c -> Map k c -> Map k c
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k c
go Map k b
t2
 where
  go :: p -> p -> p -> p -> p -> p -> Map k c
go p
_ p
_ p
_ p
_ p
_ p
_ =
    [(k, c)] -> Map k c
forall k a. [(k, a)] -> Map k a
fromDistinctAscList ([(k, c)] -> Map k c) -> [(k, c)] -> Map k c
forall a b. (a -> b) -> a -> b
$
      (k -> a -> [(k, c)] -> [(k, c)]) -> [(k, c)] -> Map k a -> [(k, c)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
        (\k
k a
a [(k, c)]
c -> [(k, c)] -> (b -> [(k, c)]) -> Maybe b -> [(k, c)]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [(k, c)]
c (\b
b -> (k
k, k -> a -> b -> c
f k
k a
a b
b) (k, c) -> [(k, c)] -> [(k, c)]
forall a. a -> [a] -> [a]
: [(k, c)]
c) (Maybe b -> [(k, c)]) -> Maybe b -> [(k, c)]
forall a b. (a -> b) -> a -> b
$ k -> Map k b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k b
t2)
        []
        Map k a
t1

-- | /O(m log n)/ Unite a map with another via left-biased key matching
union :: (Ord k) => Map k a -> Map k a -> Map k a
union :: forall k a. Ord k => Map k a -> Map k a -> Map k a
union = (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey ((k -> a -> a -> a) -> Map k a -> Map k a -> Map k a)
-> (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const a -> a -> a
forall a b. a -> b -> a
const

-- | /O(m log n)/ Unite a map with another, combining values of matching keys
unionWith :: (Ord k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith :: forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith = (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey ((k -> a -> a -> a) -> Map k a -> Map k a -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> Map k a
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | /O(m log n)/ Unite a map with another, combining values of matching keys
unionWithKey :: (Ord k) => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey :: forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey k -> a -> a -> a
f Map k a
t1 Map k a
t2 = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
t1 Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Map k a
go Map k a
t2
 where
  go :: p -> p -> p -> p -> p -> p -> Map k a
go p
_ p
_ p
_ p
_ p
_ p
_ = (k -> a -> Map k a -> Map k a) -> Map k a -> Map k a -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey ((k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
f) Map k a
t2 Map k a
t1

-- | Unite a collection of maps via left-biased key matching
unions :: (Foldable t, Ord k) => t (Map k a) -> Map k a
unions :: forall (t :: * -> *) k a.
(Foldable t, Ord k) =>
t (Map k a) -> Map k a
unions = (k -> a -> a -> a) -> t (Map k a) -> Map k a
forall (t :: * -> *) k a.
(Foldable t, Ord k) =>
(k -> a -> a -> a) -> t (Map k a) -> Map k a
unionsWithKey ((k -> a -> a -> a) -> t (Map k a) -> Map k a)
-> (k -> a -> a -> a) -> t (Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const a -> a -> a
forall a b. a -> b -> a
const

-- | Unite a collection of maps, combining values of matching keys
unionsWith :: (Foldable t, Ord k) => (a -> a -> a) -> t (Map k a) -> Map k a
unionsWith :: forall (t :: * -> *) k a.
(Foldable t, Ord k) =>
(a -> a -> a) -> t (Map k a) -> Map k a
unionsWith = (k -> a -> a -> a) -> t (Map k a) -> Map k a
forall (t :: * -> *) k a.
(Foldable t, Ord k) =>
(k -> a -> a -> a) -> t (Map k a) -> Map k a
unionsWithKey ((k -> a -> a -> a) -> t (Map k a) -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> t (Map k a)
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | Unite a collection of maps, combining values of matching keys
unionsWithKey :: (Foldable t, Ord k) => (k -> a -> a -> a) -> t (Map k a) -> Map k a
unionsWithKey :: forall (t :: * -> *) k a.
(Foldable t, Ord k) =>
(k -> a -> a -> a) -> t (Map k a) -> Map k a
unionsWithKey k -> a -> a -> a
f = (Map k a -> Map k a -> Map k a)
-> Map k a -> t (Map k a) -> Map k a
forall a b. (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey k -> a -> a -> a
f) Map k a
forall k a. Map k a
empty

{-
 - Conversion
 -}

-- | /O(n)/ Turn a map into a list of @(key, value)@ pairs in ascending order
toAscList :: Map k a -> [(k, a)]
toAscList :: forall k a. Map k a -> [(k, a)]
toAscList = (k -> a -> [(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a -> [(k, a)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a [(k, a)]
b -> (k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
b) []

-- | /O(n)/ Turn a map into a list of @(key, value)@ pairs in descending order
toDescList :: Map k a -> [(k, a)]
toDescList :: forall k a. Map k a -> [(k, a)]
toDescList = ([(k, a)] -> k -> a -> [(k, a)]) -> [(k, a)] -> Map k a -> [(k, a)]
forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey (\[(k, a)]
b k
k a
a -> (k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
b) []

{-
 - Fold
 -}

-- | /O(n)/ Reduce a map with a left-associative operation and an accumulator
foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey :: forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey b -> k -> a -> b
f b
b = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
b Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go
 where
  go :: p -> k -> a -> Map k a -> b -> p -> b
go p
_ k
k a
a Map k a
r b
recl p
_ = (b -> k -> a -> b) -> b -> Map k a -> b
forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey b -> k -> a -> b
f (b -> k -> a -> b
f b
recl k
k a
a) Map k a
r

-- | /O(n)/ Reduce a map with a right-associative operation and an accumulator
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey :: forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey k -> a -> b -> b
f b
b = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' b
b Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go
 where
  go :: Map k a -> k -> a -> p -> p -> b -> b
go Map k a
l k
k a
a p
_ p
_ b
recr = (k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey k -> a -> b -> b
f (k -> a -> b -> b
f k
k a
a b
recr) Map k a
l

{-
 - Modification
 -}

-- | /O(log n)/ Adjust with an operation the value of a key in a map
adjust :: (Ord k) => (a -> a) -> k -> Map k a -> Map k a
adjust :: forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
adjust = (k -> a -> a) -> k -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
adjustWithKey ((k -> a -> a) -> k -> Map k a -> Map k a)
-> ((a -> a) -> k -> a -> a) -> (a -> a) -> k -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> k -> a -> a
forall a b. a -> b -> a
const

-- | /O(log n)/ Adjust with an operation the value of a key in a map
adjustWithKey :: (Ord k) => (k -> a -> a) -> k -> Map k a -> Map k a
adjustWithKey :: forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
adjustWithKey k -> a -> a
f k
k0 = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
forall k a. Map k a
E ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R)
 where
  go :: (t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go t -> k -> a -> t -> t
c t
l k
k a
a t
r t
recl t
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
    Ordering
LT -> t -> k -> a -> t -> t
c t
recl k
k a
a t
r
    Ordering
EQ -> t -> k -> a -> t -> t
c t
l k
k (k -> a -> a
f k
k a
a) t
r
    Ordering
GT -> t -> k -> a -> t -> t
c t
l k
k a
a t
recr

-- | /O(log n)/ Adjust with an operation the value of the maximum key in a map
adjustMax :: (a -> a) -> Map k a -> Map k a
adjustMax :: forall a k. (a -> a) -> Map k a -> Map k a
adjustMax = (k -> a -> a) -> Map k a -> Map k a
forall k a. (k -> a -> a) -> Map k a -> Map k a
adjustMaxWithKey ((k -> a -> a) -> Map k a -> Map k a)
-> ((a -> a) -> k -> a -> a) -> (a -> a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> k -> a -> a
forall a b. a -> b -> a
const

-- | /O(log n)/ Adjust with an operation the value of the maximum key in a map
adjustMaxWithKey :: (k -> a -> a) -> Map k a -> Map k a
adjustMaxWithKey :: forall k a. (k -> a -> a) -> Map k a -> Map k a
adjustMaxWithKey k -> a -> a
f = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
forall k a. Map k a
E ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {k} {a} {b} {p}.
(p -> k -> a -> Map k a -> b)
-> p -> k -> a -> Map k a -> p -> Map k a -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {k} {a} {b} {p}.
(p -> k -> a -> Map k a -> b)
-> p -> k -> a -> Map k a -> p -> Map k a -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {p} {k} {a} {b} {p}.
(p -> k -> a -> Map k a -> b)
-> p -> k -> a -> Map k a -> p -> Map k a -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R)
 where
  go :: (p -> k -> a -> Map k a -> b)
-> p -> k -> a -> Map k a -> p -> Map k a -> b
go p -> k -> a -> Map k a -> b
c p
l k
k a
a Map k a
r p
_ Map k a
recr = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' (p -> k -> a -> Map k a -> b
c p
l k
k (k -> a -> a
f k
k a
a) Map k a
r) Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a
r
   where
    go' :: p -> p -> p -> p -> p -> p -> b
go' p
_ p
_ p
_ p
_ p
_ p
_ = p -> k -> a -> Map k a -> b
c p
l k
k a
a Map k a
recr

-- | /O(log n)/ Adjust with an operation the value of the minimum key in a map
adjustMin :: (a -> a) -> Map k a -> Map k a
adjustMin :: forall a k. (a -> a) -> Map k a -> Map k a
adjustMin = (k -> a -> a) -> Map k a -> Map k a
forall k a. (k -> a -> a) -> Map k a -> Map k a
adjustMinWithKey ((k -> a -> a) -> Map k a -> Map k a)
-> ((a -> a) -> k -> a -> a) -> (a -> a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> k -> a -> a
forall a b. a -> b -> a
const

-- | /O(log n)/ Adjust with an operation the value of the minimum key in a map
adjustMinWithKey :: (k -> a -> a) -> Map k a -> Map k a
adjustMinWithKey :: forall k a. (k -> a -> a) -> Map k a -> Map k a
adjustMinWithKey k -> a -> a
f = Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k a
forall k a. Map k a
E ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {k} {a} {p} {b} {p}.
(Map k a -> k -> a -> p -> b)
-> Map k a -> k -> a -> p -> Map k a -> p -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {k} {a} {p} {b} {p}.
(Map k a -> k -> a -> p -> b)
-> Map k a -> k -> a -> p -> Map k a -> p -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B) ((Map k a -> k -> a -> Map k a -> Map k a)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {k} {a} {p} {b} {p}.
(Map k a -> k -> a -> p -> b)
-> Map k a -> k -> a -> p -> Map k a -> p -> b
go Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R)
 where
  go :: (Map k a -> k -> a -> p -> b)
-> Map k a -> k -> a -> p -> Map k a -> p -> b
go Map k a -> k -> a -> p -> b
c Map k a
l k
k a
a p
r Map k a
recl p
_ = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' (Map k a -> k -> a -> p -> b
c Map k a
l k
k (k -> a -> a
f k
k a
a) p
r) Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> b
go' Map k a
l
   where
    go' :: p -> p -> p -> p -> p -> p -> b
go' p
_ p
_ p
_ p
_ p
_ p
_ = Map k a -> k -> a -> p -> b
c Map k a
recl k
k a
a p
r

-- | /O(log n)/ Delete a key from a map
delete :: (Ord k) => k -> Map k a -> Map k a
delete :: forall k a. Ord k => k -> Map k a -> Map k a
delete k
k Map k a
t = Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
t (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k Map k a
t) (Bool -> Map k a) -> Bool -> Map k a
forall a b. (a -> b) -> a -> b
$ k
k k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
`member` Map k a
t

-- | /O(log n)/ Delete the maximum key from a map
deleteMax :: (Ord k) => Map k a -> Map k a
deleteMax :: forall k a. Ord k => Map k a -> Map k a
deleteMax Map k a
t = Map k a -> ((k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
t ((k -> Map k a -> Map k a) -> Map k a -> k -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' Map k a
t (k -> Map k a) -> ((k, a) -> k) -> (k, a) -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) (Maybe (k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMax Map k a
t

-- | /O(log n)/ Delete the minimum key from a map
deleteMin :: (Ord k) => Map k a -> Map k a
deleteMin :: forall k a. Ord k => Map k a -> Map k a
deleteMin Map k a
t = Map k a -> ((k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
t ((k -> Map k a -> Map k a) -> Map k a -> k -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' Map k a
t (k -> Map k a) -> ((k, a) -> k) -> (k, a) -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) (Maybe (k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMin Map k a
t

-- | /O(n)/ Keep the bins whose values satisfy a predicate
filter :: (a -> Bool) -> Map k a -> Map k a
filter :: forall a k. (a -> Bool) -> Map k a -> Map k a
filter = (k -> a -> Bool) -> Map k a -> Map k a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey ((k -> a -> Bool) -> Map k a -> Map k a)
-> ((a -> Bool) -> k -> a -> Bool)
-> (a -> Bool)
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> k -> a -> Bool
forall a b. a -> b -> a
const

-- | /O(n)/ Keep the bins whose keys and values satisfy a predicate
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey :: forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey k -> a -> Bool
p =
  [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList
    ([(k, a)] -> Map k a)
-> (Map k a -> [(k, a)]) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> [(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a -> [(k, a)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a [(k, a)]
b -> [(k, a)] -> [(k, a)] -> Bool -> [(k, a)]
forall a. a -> a -> Bool -> a
bool [(k, a)]
b ((k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
b) (Bool -> [(k, a)]) -> Bool -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ k -> a -> Bool
p k
k a
a) []

-- | /O(log n)/ Insert a key and its value into a map, overwriting if present
insert :: (Ord k) => k -> a -> Map k a -> Map k a
insert :: forall k a. Ord k => k -> a -> Map k a -> Map k a
insert = (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey ((k -> a -> a -> a) -> k -> a -> Map k a -> Map k a)
-> (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const a -> a -> a
forall a b. a -> b -> a
const

-- | /O(log n)/ Insert a key and its value, combining new and old if present
insertWith :: (Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith :: forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith = (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey ((k -> a -> a -> a) -> k -> a -> Map k a -> Map k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> k
-> a
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const

-- | /O(log n)/ Modify the value of a key or delete its bin with an operation
update :: (Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a
update :: forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
update = (k -> a -> Maybe a) -> k -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey ((k -> a -> Maybe a) -> k -> Map k a -> Map k a)
-> ((a -> Maybe a) -> k -> a -> Maybe a)
-> (a -> Maybe a)
-> k
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> k -> a -> Maybe a
forall a b. a -> b -> a
const

-- | /O(log n)/ Modify the value of a key or delete its bin with an operation
updateWithKey :: (Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey :: forall k a. Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey k -> a -> Maybe a
f k
k Map k a
t =
  Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
    Map k a
t
    ( Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
        (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k Map k a
t)
        (\a
a' -> k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a' Map k a
t)
        (Maybe a -> Map k a) -> (a -> Maybe a) -> a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Maybe a
f k
k
    )
    (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k a
t

-- | /O(log n)/ Modify the value of the maximum key or delete its bin
updateMax :: (Ord k) => (a -> Maybe a) -> Map k a -> Map k a
updateMax :: forall k a. Ord k => (a -> Maybe a) -> Map k a -> Map k a
updateMax = (k -> a -> Maybe a) -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMaxWithKey ((k -> a -> Maybe a) -> Map k a -> Map k a)
-> ((a -> Maybe a) -> k -> a -> Maybe a)
-> (a -> Maybe a)
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> k -> a -> Maybe a
forall a b. a -> b -> a
const

-- | /O(log n)/ Modify the value of the maximum key or delete its bin
updateMaxWithKey :: (Ord k) => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMaxWithKey :: forall k a. Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMaxWithKey k -> a -> Maybe a
f Map k a
t =
  Map k a -> ((k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
    Map k a
t
    ( \(k
k, a
a) ->
        Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
          (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k Map k a
t)
          (\a
a' -> k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a' Map k a
t)
          (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe a
f k
k a
a
    )
    (Maybe (k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMax Map k a
t

-- | /O(log n)/ Modify the value of the minimum key or delete its bin
updateMin :: (Ord k) => (a -> Maybe a) -> Map k a -> Map k a
updateMin :: forall k a. Ord k => (a -> Maybe a) -> Map k a -> Map k a
updateMin = (k -> a -> Maybe a) -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMinWithKey ((k -> a -> Maybe a) -> Map k a -> Map k a)
-> ((a -> Maybe a) -> k -> a -> Maybe a)
-> (a -> Maybe a)
-> Map k a
-> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> k -> a -> Maybe a
forall a b. a -> b -> a
const

-- | /O(log n)/ Modify the value of the minimum key or delete its bin
updateMinWithKey :: (Ord k) => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMinWithKey :: forall k a. Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a
updateMinWithKey k -> a -> Maybe a
f Map k a
t =
  Map k a -> ((k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
    Map k a
t
    ( \(k
k, a
a) ->
        Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
          (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k Map k a
t)
          (\a
a' -> k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a' Map k a
t)
          (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe a
f k
k a
a
    )
    (Maybe (k, a) -> Map k a) -> Maybe (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMin Map k a
t

{-
 - Partition
 -}

-- | /O(n)/ Partition a map with a predicate into @(true, false)@ submaps
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
partition :: forall a k. (a -> Bool) -> Map k a -> (Map k a, Map k a)
partition = (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey ((k -> a -> Bool) -> Map k a -> (Map k a, Map k a))
-> ((a -> Bool) -> k -> a -> Bool)
-> (a -> Bool)
-> Map k a
-> (Map k a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> k -> a -> Bool
forall a b. a -> b -> a
const

-- | /O(n)/ Partition a map with a predicate into @(true, false)@ submaps
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey :: forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey k -> a -> Bool
p =
  ([(k, a)] -> Map k a)
-> ([(k, a)] -> Map k a)
-> ([(k, a)], [(k, a)])
-> (Map k a, Map k a)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList
    (([(k, a)], [(k, a)]) -> (Map k a, Map k a))
-> (Map k a -> ([(k, a)], [(k, a)]))
-> Map k a
-> (Map k a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> ([(k, a)], [(k, a)]) -> ([(k, a)], [(k, a)]))
-> ([(k, a)], [(k, a)]) -> Map k a -> ([(k, a)], [(k, a)])
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
      (\k
k a
a -> (([(k, a)] -> [(k, a)])
 -> ([(k, a)], [(k, a)]) -> ([(k, a)], [(k, a)]))
-> (([(k, a)] -> [(k, a)])
    -> ([(k, a)], [(k, a)]) -> ([(k, a)], [(k, a)]))
-> Bool
-> ([(k, a)] -> [(k, a)])
-> ([(k, a)], [(k, a)])
-> ([(k, a)], [(k, a)])
forall a. a -> a -> Bool -> a
bool ([(k, a)] -> [(k, a)])
-> ([(k, a)], [(k, a)]) -> ([(k, a)], [(k, a)])
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second ([(k, a)] -> [(k, a)])
-> ([(k, a)], [(k, a)]) -> ([(k, a)], [(k, a)])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (k -> a -> Bool
p k
k a
a) ((k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
:))
      ([], [])

-- | /O(n)/ Split a map by a key into @(lt, eq, gt)@ submaps
split :: (Ord k) => k -> Map k a -> (Map k a, Maybe a, Map k a)
split :: forall k a. Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
split k
k0 =
  (\([(k, a)]
lt, Maybe a
a, [(k, a)]
gt) -> ([(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList [(k, a)]
lt, Maybe a
a, [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
fromDistinctAscList [(k, a)]
gt))
    (([(k, a)], Maybe a, [(k, a)]) -> (Map k a, Maybe a, Map k a))
-> (Map k a -> ([(k, a)], Maybe a, [(k, a)]))
-> Map k a
-> (Map k a, Maybe a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k
 -> a
 -> ([(k, a)], Maybe a, [(k, a)])
 -> ([(k, a)], Maybe a, [(k, a)]))
-> ([(k, a)], Maybe a, [(k, a)])
-> Map k a
-> ([(k, a)], Maybe a, [(k, a)])
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
      ( \k
k a
a ([(k, a)]
lt, Maybe a
a', [(k, a)]
gt) -> case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
          Ordering
LT -> ((k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
lt, Maybe a
a', [(k, a)]
gt)
          Ordering
EQ -> ([(k, a)]
lt, a -> Maybe a
forall a. a -> Maybe a
Just a
a, [(k, a)]
gt)
          Ordering
GT -> ([(k, a)]
lt, Maybe a
a', (k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
gt)
      )
      ([], Maybe a
forall a. Maybe a
Nothing, [])

-- | /O(log n)/ Split a map by its maximum key
splitMax :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)
splitMax :: forall k a. Ord k => Map k a -> Maybe ((k, a), Map k a)
splitMax Map k a
t = ((,) ((k, a) -> Map k a -> ((k, a), Map k a))
-> ((k, a) -> Map k a) -> (k, a) -> ((k, a), Map k a)
forall a b. ((k, a) -> a -> b) -> ((k, a) -> a) -> (k, a) -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (k -> Map k a -> Map k a) -> Map k a -> k -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' Map k a
t (k -> Map k a) -> ((k, a) -> k) -> (k, a) -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) ((k, a) -> ((k, a), Map k a))
-> Maybe (k, a) -> Maybe ((k, a), Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMax Map k a
t

-- | /O(log n)/ Split a map by its minimum key
splitMin :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)
splitMin :: forall k a. Ord k => Map k a -> Maybe ((k, a), Map k a)
splitMin Map k a
t = ((,) ((k, a) -> Map k a -> ((k, a), Map k a))
-> ((k, a) -> Map k a) -> (k, a) -> ((k, a), Map k a)
forall a b. ((k, a) -> a -> b) -> ((k, a) -> a) -> (k, a) -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (k -> Map k a -> Map k a) -> Map k a -> k -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete' Map k a
t (k -> Map k a) -> ((k, a) -> k) -> (k, a) -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) ((k, a) -> ((k, a), Map k a))
-> Maybe (k, a) -> Maybe ((k, a), Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
lookupMin Map k a
t

{-
 - Query
 -}

-- | /O(m log n)/ Check whether two maps have no keys in common
disjoint :: (Ord k) => Map k a -> Map k a -> Bool
disjoint :: forall k a. Ord k => Map k a -> Map k a -> Bool
disjoint Map k a
t1 Map k a
t2 = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a
t1
 where
  go :: p -> p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ p
_ = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (k -> a -> Bool -> Bool) -> Bool -> Map k a -> Bool
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
_ Bool
b -> k
k k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
`member` Map k a
t1 Bool -> Bool -> Bool
|| Bool
b) Bool
False Map k a
t2

-- | /O(n log m)/ Check whether the bins of one map exist in the other
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOf :: forall k a. (Ord k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOf = (a -> a -> Bool) -> Map k a -> Map k a -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | /O(n log m)/ Check if the bins of one map exist in the other by combination
isSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy :: forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy a -> b -> Bool
p Map k a
t1 Map k b
t2 = Bool
-> (Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool)
-> (Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool)
-> (Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool)
-> Map k b
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' (Map k a -> Bool
forall k a. Map k a -> Bool
null Map k a
t1) Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k b -> k -> b -> Map k b -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k b
t2
 where
  go :: p -> p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ p
_ =
    (k -> a -> Bool -> Bool) -> Bool -> Map k a -> Bool
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
      (\k
k a
a Bool
b -> Bool -> (b -> Bool) -> Maybe b -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((Bool -> Bool -> Bool
&& Bool
b) (Bool -> Bool) -> (b -> Bool) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> Bool
p a
a) (Maybe b -> Bool) -> Maybe b -> Bool
forall a b. (a -> b) -> a -> b
$ k -> Map k b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k b
t2)
      Bool
True
      Map k a
t1

-- | /O(log n)/ Fetch the value of a key in a map, or 'Nothing' if absent
lookup :: (Ord k) => k -> Map k a -> Maybe a
lookup :: forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe a
forall a. Maybe a
Nothing Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ k
k' a
a p
_ Maybe a
recl Maybe a
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k' of
    Ordering
LT -> Maybe a
recl
    Ordering
EQ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
GT -> Maybe a
recr

-- | /O(log n)/ Fetch the least bin greater than or equal to a key
lookupGE :: (Ord k) => k -> Map k a -> Maybe (k, a)
lookupGE :: forall k a. Ord k => k -> Map k a -> Maybe (k, a)
lookupGE k
k0 = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go
 where
  go :: p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go p
_ k
k b
a p
_ Maybe (k, b)
recl Maybe (k, b)
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, b)
recr
    Ordering
EQ -> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)
    Ordering
GT -> Maybe (k, b)
recl Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)

-- | /O(log n)/ Fetch the least bin strictly greater than a key
lookupGT :: (Ord k) => k -> Map k a -> Maybe (k, a)
lookupGT :: forall k a. Ord k => k -> Map k a -> Maybe (k, a)
lookupGT k
k0 = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go
 where
  go :: p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go p
_ k
k b
a p
_ Maybe (k, b)
recl Maybe (k, b)
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, b)
recr
    Ordering
EQ -> Maybe (k, b)
recr
    Ordering
GT -> Maybe (k, b)
recl Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)

-- | /O(log n)/ Fetch the greatest bin less than or equal to a key
lookupLE :: (Ord k) => k -> Map k a -> Maybe (k, a)
lookupLE :: forall k a. Ord k => k -> Map k a -> Maybe (k, a)
lookupLE k
k0 = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go
 where
  go :: p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go p
_ k
k b
a p
_ Maybe (k, b)
recl Maybe (k, b)
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, b)
recr Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)
    Ordering
EQ -> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)
    Ordering
GT -> Maybe (k, b)
recl

-- | /O(log n)/ Fetch the greatest bin strictly less than a key
lookupLT :: (Ord k) => k -> Map k a -> Maybe (k, a)
lookupLT :: forall k a. Ord k => k -> Map k a -> Maybe (k, a)
lookupLT k
k0 = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {b} {p}.
p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go
 where
  go :: p -> k -> b -> p -> Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
go p
_ k
k b
a p
_ Maybe (k, b)
recl Maybe (k, b)
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, b)
recr Maybe (k, b) -> Maybe (k, b) -> Maybe (k, b)
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, b) -> Maybe (k, b)
forall a. a -> Maybe a
Just (k
k, b
a)
    Ordering
EQ -> Maybe (k, b)
recl
    Ordering
GT -> Maybe (k, b)
recl

-- | /O(log n)/ Fetch the bin with the maximum key, or 'Nothing' if empty
lookupMax :: Map k a -> Maybe (k, a)
lookupMax :: forall k a. Map k a -> Maybe (k, a)
lookupMax = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {a} {b} {k} {a} {p}.
p -> a -> b -> Map k a -> p -> Maybe (a, b) -> Maybe (a, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {a} {b} {k} {a} {p}.
p -> a -> b -> Map k a -> p -> Maybe (a, b) -> Maybe (a, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {p} {a} {b} {k} {a} {p}.
p -> a -> b -> Map k a -> p -> Maybe (a, b) -> Maybe (a, b)
go
 where
  go :: p -> a -> b -> Map k a -> p -> Maybe (a, b) -> Maybe (a, b)
go p
_ a
k b
a Map k a
r p
_ Maybe (a, b)
recr = Maybe (a, b)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> Map k a
-> Maybe (a, b)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
k, b
a)) Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
r
   where
    go' :: p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' p
_ p
_ p
_ p
_ p
_ p
_ = Maybe (a, b)
recr

-- | /O(log n)/ Fetch the bin with the minimum key, or 'Nothing' if empty
lookupMin :: Map k a -> Maybe (k, a)
lookupMin :: forall k a. Map k a -> Maybe (k, a)
lookupMin = Maybe (k, a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (k, a)
    -> Maybe (k, a)
    -> Maybe (k, a))
-> Map k a
-> Maybe (k, a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Maybe (k, a)
forall a. Maybe a
Nothing Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {k} {a} {a} {b} {p} {p}.
Map k a -> a -> b -> p -> Maybe (a, b) -> p -> Maybe (a, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {k} {a} {a} {b} {p} {p}.
Map k a -> a -> b -> p -> Maybe (a, b) -> p -> Maybe (a, b)
go Map k a
-> k
-> a
-> Map k a
-> Maybe (k, a)
-> Maybe (k, a)
-> Maybe (k, a)
forall {k} {a} {a} {b} {p} {p}.
Map k a -> a -> b -> p -> Maybe (a, b) -> p -> Maybe (a, b)
go
 where
  go :: Map k a -> a -> b -> p -> Maybe (a, b) -> p -> Maybe (a, b)
go Map k a
l a
k b
a p
_ Maybe (a, b)
recl p
_ = Maybe (a, b)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> Maybe (a, b)
    -> Maybe (a, b)
    -> Maybe (a, b))
-> Map k a
-> Maybe (a, b)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
k, b
a)) Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
-> k
-> a
-> Map k a
-> Maybe (a, b)
-> Maybe (a, b)
-> Maybe (a, b)
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' Map k a
l
   where
    go' :: p -> p -> p -> p -> p -> p -> Maybe (a, b)
go' p
_ p
_ p
_ p
_ p
_ p
_ = Maybe (a, b)
recl

-- | /O(log n)/ Check whether a key is in a map
member :: (Ord k) => k -> Map k a -> Bool
member :: forall k a. Ord k => k -> Map k a -> Bool
member k
k0 = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
False Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go
 where
  go :: p -> k -> p -> p -> Bool -> Bool -> Bool
go p
_ k
k p
_ p
_ Bool
recl Bool
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
    Ordering
LT -> Bool
recl
    Ordering
EQ -> Bool
True
    Ordering
GT -> Bool
recr

-- | /O(1)/ Check whether a map is empty
null :: Map k a -> Bool
null :: forall k a. Map k a -> Bool
null = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go where go :: p -> p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ p
_ = Bool
False

-- | /O(n)/ Get the size of a map
size :: Map k a -> Int
size :: forall k a. Map k a -> Int
size = Int
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> Map k a
-> Int
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Int
0 Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go where go :: p -> p -> p -> p -> a -> a -> a
go p
_ p
_ p
_ p
_ a
recl a
recr = a
1 a -> a -> a
forall a. Num a => a -> a -> a
+ a
recl a -> a -> a
forall a. Num a => a -> a -> a
+ a
recr

{-
 - Traversal
 -}

-- | /O(n)/ Apply an operation across a map, transforming its values
fmapWithKey :: (k -> a -> b) -> Map k a -> Map k b
fmapWithKey :: forall k a b. (k -> a -> b) -> Map k a -> Map k b
fmapWithKey k -> a -> b
f = Map k b
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> Map k a
-> Map k b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Map k b
forall k a. Map k a
E ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b
forall {t} {t} {p} {p}.
(t -> k -> b -> t) -> p -> k -> a -> p -> t -> t
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L) ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b
forall {t} {t} {p} {p}.
(t -> k -> b -> t) -> p -> k -> a -> p -> t -> t
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B) ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b
forall {t} {t} {p} {p}.
(t -> k -> b -> t) -> p -> k -> a -> p -> t -> t
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R)
 where
  go :: (t -> k -> b -> t) -> p -> k -> a -> p -> t -> t
go t -> k -> b -> t
c p
_ k
k a
a p
_ t
recl = t -> k -> b -> t
c t
recl k
k (k -> a -> b
f k
k a
a)

-- | /O(n)/ Lift a map with a lifting operation on keys and values
traverseWithKey :: (Applicative f) => (k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey k -> a -> f b
f = f (Map k b)
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> Map k a
-> f (Map k b)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' (Map k b -> f (Map k b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map k b
forall k a. Map k a
E) ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L) ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B) ((Map k b -> k -> b -> Map k b -> Map k b)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R)
 where
  go :: (a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go a -> k -> b -> a -> b
c p
_ k
k a
a p
_ f a
recl f a
recr = a -> k -> b -> a -> b
c (a -> k -> b -> a -> b) -> f a -> f (k -> b -> a -> b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f a
recl f (k -> b -> a -> b) -> f k -> f (b -> a -> b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> f k
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k f (b -> a -> b) -> f b -> f (a -> b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> a -> f b
f k
k a
a f (a -> b) -> f a -> f b
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f a
recr

{-
 - Validation
 -}

-- | /O(n^2)/ Check whether a map is internally height-balanced and ordered
valid :: (Ord k) => Map k a -> Bool
valid :: forall k a. Ord k => Map k a -> Bool
valid = (Bool -> Bool -> Bool)
-> (Map k a -> Bool) -> (Map k a -> Bool) -> Map k a -> Bool
forall a b c.
(a -> b -> c) -> (Map k a -> a) -> (Map k a -> b) -> Map k a -> c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Bool -> Bool -> Bool
(&&) Map k a -> Bool
forall k a. Map k a -> Bool
balanced Map k a -> Bool
forall {a}. Map k a -> Bool
ordered
 where
  balanced :: Map k a -> Bool
balanced =
    Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      Bool
True
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
  levels :: Map k a -> Int
levels = Int
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> Map k a
-> Int
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Int
0 Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go
   where
    go :: p -> p -> p -> p -> Int -> Int -> Int
go p
_ p
_ p
_ p
_ Int
recl Int
recr = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
recl Int
recr :: Int
  ordered :: Map k a -> Bool
ordered = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go
   where
    go :: Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a
l k
k p
_ Map k a
r Bool
recl Bool
recr =
      Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
lt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
lt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
lt Map k a
l
        Bool -> Bool -> Bool
&& Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map' Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
gt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
gt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
gt Map k a
r
     where
      lt :: p -> k -> p -> p -> p -> p -> Bool
lt p
_ k
lk p
_ p
_ p
_ p
_ = k
lk k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr
      gt :: p -> k -> p -> p -> p -> p -> Bool
gt p
_ k
rk p
_ p
_ p
_ p
_ = k
rk k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr

{-
 - Helpers
 -}

-- O(n) 'nub' on keys for sorted lists of pairs
essence :: (Eq k) => [(k, a)] -> [(k, a)]
essence :: forall k a. Eq k => [(k, a)] -> [(k, a)]
essence [] = []
essence ((k, a)
x : [(k, a)]
xs) = (k, a) -> [(k, a)] -> [(k, a)]
forall {a} {b}. Eq a => (a, b) -> [(a, b)] -> [(a, b)]
essence' (k, a)
x [(k, a)]
xs
 where
  essence' :: (a, b) -> [(a, b)] -> [(a, b)]
essence' (a, b)
ka1 [] = [(a, b)
ka1]
  essence' ka1 :: (a, b)
ka1@(a
k1, b
_) (ka2 :: (a, b)
ka2@(a
k2, b
_) : [(a, b)]
kas) =
    let rest :: [(a, b)]
rest = (a, b) -> [(a, b)] -> [(a, b)]
essence' (a, b)
ka2 [(a, b)]
kas
     in [(a, b)] -> [(a, b)] -> Bool -> [(a, b)]
forall a. a -> a -> Bool -> a
bool ((a, b)
ka1 (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
rest) [(a, b)]
rest (Bool -> [(a, b)]) -> Bool -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ a
k1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k2

-- O(n) 'nub' with a combining function for sorted lists of pairs
essenceWith :: (Eq k) => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
essenceWith :: forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
essenceWith k -> a -> a -> a
_ [] = []
essenceWith k -> a -> a -> a
f ((k, a)
x : [(k, a)]
xs) = (k, a) -> [(k, a)] -> [(k, a)]
essenceWith' (k, a)
x [(k, a)]
xs
 where
  essenceWith' :: (k, a) -> [(k, a)] -> [(k, a)]
essenceWith' (k, a)
ka1 [] = [(k, a)
ka1]
  essenceWith' ka1 :: (k, a)
ka1@(k
k1, a
a1) (ka2 :: (k, a)
ka2@(k
k2, a
a2) : [(k, a)]
kas) =
    [(k, a)] -> [(k, a)] -> Bool -> [(k, a)]
forall a. a -> a -> Bool -> a
bool
      ((k, a)
ka1 (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k, a) -> [(k, a)] -> [(k, a)]
essenceWith' (k, a)
ka2 [(k, a)]
kas)
      ((k, a) -> [(k, a)] -> [(k, a)]
essenceWith' (k
k1, k -> a -> a -> a
f k
k1 a
a2 a
a1) [(k, a)]
kas)
      (Bool -> [(k, a)]) -> Bool -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2

-- The greatest power of 2 <= the length of a non-empty collection
power :: (Foldable t) => t a -> Int
power :: forall (t :: * -> *) a. Foldable t => t a -> Int
power t a
as = (Int -> Bool) -> (Int -> Int) -> Int -> Int
forall a. (a -> Bool) -> (a -> a) -> a -> a
until (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> t a -> Int
forall a. t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
as) (Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2) Int
2 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2

{-
 - Let this comment serve as your warning. Return from whence you came and your
 - sanity will be spared. You have been admonished.
 -}

-- O(log n) Delete a key from a map without checking for membership
delete' :: (Ord k) => k -> Map k a -> Map k a
delete' :: forall k a. Ord k => k -> Map k a -> Map k a
delete' k
k0 =
  Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
    (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L0")
    ( \Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k a
l k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> Map k a -> Map k a
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k a
l Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k a
l k
k a
a Map k a
r
    )
    ( \Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k a
l k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> Map k a -> Map k a
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k a
l Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k a
l k
k a
a Map k a
r
    )
    ( \Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k a
l k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> Map k a -> Map k a
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k a
l Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k a
l k
k a
a Map k a
r
    )
 where
  deleteRl :: Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L1")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteRr :: Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L2")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  deleteBl :: Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L3")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteBr :: Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L4")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  deleteLl :: Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L5")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteLr :: Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L6")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  rebalanceR :: Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L7")
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
            (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L8")
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
rlr k
rk a
ra Map k a
rr))
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr k
rk a
ra Map k a
rr))
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr k
rk a
ra Map k a
rr))
            Map k a
rl
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
  rebalanceL :: Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L9")
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
lr k
k a
a Map k a
r))
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
            (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L10")
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
lrr k
k a
a Map k a
r))
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr k
k a
a Map k a
r))
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr k
k a
a Map k a
r))
            Map k a
lr
      )
      Map k a
l
  checkLeftR :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L11")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftB :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L12")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftL :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L13")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkRightR :: Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L14")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightB :: Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L15")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightL :: Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L16")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
r
  substituteR :: Map k a -> Map k a -> Map k a
substituteR Map k a
l =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L17")
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftB Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map k a
rl k
rk a
ra Map k a
rr
      )
  substituteBr :: Map k a -> Map k a -> Map k a
substituteBr Map k a
l =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      Map k a
forall k a. Map k a
E
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftB Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map k a
rl k
rk a
ra Map k a
rr
      )
  substituteBl :: Map k a -> Map k a -> Map k a
substituteBl Map k a
l Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      Map k a
forall k a. Map k a
E
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightB Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map k a
ll k
lk a
la Map k a
lr
      )
      Map k a
l
  substituteL :: Map k a -> Map k a -> Map k a
substituteL Map k a
l Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L18")
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightB Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map k a
ll k
lk a
la Map k a
lr
      )
      Map k a
l
  checkLeftR' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftR' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftB' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftL' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkRightR' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightB' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightL' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightL' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
r
  popLeftR :: Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
l t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (t
k, t
a, Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
      )
      (\Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftRB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
      )
      Map t t
l
  popLeftB :: Map k a -> k -> a -> Map k a -> (k, a, Map k a)
popLeftB Map k a
l k
k a
a Map k a
r =
    (k, a, Map k a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> Map k a
-> (k, a, Map k a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (k
k, a
a, Map k a
forall k a. Map k a
E)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      Map k a
l
  popLeftL :: Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
l t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> (t, t, Map t t)
forall a. HasCallStack => String -> a
error String
"Map.delete: L19")
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
      )
      (\Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftLB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
      )
      Map t t
l
  popLeftRB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftRB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map t t
forall k a. Map k a
E t
k t
a Map t t
r)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftBB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
forall k a. Map k a
E t
k t
a Map t t
r)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftLB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftLB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
forall k a. Map k a
E t
k t
a Map t t
forall k a. Map k a
E)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftBR :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
  popLeftBL :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
  popRightR :: Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
l t
k t
a =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> (Map t t, t, t)
forall a. HasCallStack => String -> a
error String
"Map.delete: L20")
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr
      )
      (\Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightRB Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
      )
  popRightB :: Map b c -> b -> c -> Map b c -> (Map b c, b, c)
popRightB Map b c
l b
k c
a =
    (Map b c, b, c)
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> Map b c
-> (Map b c, b, c)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map b c
forall k a. Map k a
E, b
k, c
a)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
  popRightL :: Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
l t
k t
a =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map t t
l, t
k, t
a)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr
      )
      (\Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightLB Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
      )
  popRightRB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightRB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
forall k a. Map k a
E t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightBB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightLB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightLB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map t t
l t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightBR :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr =
    (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
  popRightBL :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr =
    (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr

-- | /O(log n)/ Insert a key and its value, combining new and old if present
insertWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey :: forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
f k
k0 a
a0 =
  Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
    (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
l k
k a
a Map k a
r)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
l k
k a
a Map k a
r)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
l k
k a
a Map k a
r)
 where
  insertR :: Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertRl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k (k -> a -> a -> a
f k
k a
a0 a
a) Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertRr Map k a
l k
k a
a Map k a
r
  insertB :: Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertBl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k (k -> a -> a -> a
f k
k a
a0 a
a) Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertBr Map k a
l k
k a
a Map k a
r
  insertL :: Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertLl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k (k -> a -> a -> a
f k
k a
a0 a
a) Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertLr Map k a
l k
k a
a Map k a
r
  insertRl :: Map k a -> k -> a -> Map k a -> Map k a
insertRl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          let l' :: Map k a
l' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
ll k
lk a
la Map k a
lr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L0")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                Map k a
l'
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertBl :: Map k a -> k -> a -> Map k a -> Map k a
insertBl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          let l' :: Map k a
l' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
ll k
lk a
la Map k a
lr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L1")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l' k
k a
a Map k a
r)
                Map k a
l'
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertBr :: Map k a -> k -> a -> Map k a -> Map k a
insertBr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          let r :: Map k a
r = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rl k
rk a
ra Map k a
rr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L2")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
                Map k a
r
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertLr :: Map k a -> k -> a -> Map k a -> Map k a
insertLr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          let r :: Map k a
r = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rl k
rk a
ra Map k a
rr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L3")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                Map k a
r
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertRr :: Map k a -> k -> a -> Map k a -> Map k a
insertRr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L4")
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrl Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr
            Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk (k -> a -> a -> a
f k
rk a
a0 a
ra) Map k a
rr)
            Ordering
GT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrr Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertLl :: Map k a -> k -> a -> Map k a -> Map k a
insertLl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L5")
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLll Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r
            Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk (k -> a -> a -> a
f k
lk a
a0 a
la) Map k a
lr) k
k a
a Map k a
r
            Ordering
GT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLlr Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertRrr :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrr Map k a
l k
k a
a Map k a
rl k
rk a
ra =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rrl k
rrk a
rra Map k a
rrr)))
      ( \Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ ->
          let rr :: Map k a
rr = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rrl k
rrk a
rra Map k a
rrr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L6")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra Map k a
rr))
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
                Map k a
rr
      )
      (\Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rrl k
rrk a
rra Map k a
rrr)))
  insertLll :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLll Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
      (\Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
lll k
llk a
lla Map k a
llr) k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ ->
          let ll' :: Map k a
ll' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
lll k
llk a
lla Map k a
llr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L7")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la Map k a
lr) k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
                Map k a
ll'
      )
      (\Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
lll k
llk a
lla Map k a
llr) k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
ll
  insertRrl :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrl Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
forall k a. Map k a
E) k
k0 a
a0 (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
rk a
ra Map k a
rr))
      (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rll k
rlk a
rla Map k a
rlr) k
rk a
ra Map k a
rr))
      ( \Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ ->
          let rl' :: Map k a
rl' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rll k
rlk a
rla Map k a
rlr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L8")
                ( \Map k a
rll' k
rlk' a
rla' Map k a
rlr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll')
                      k
rlk'
                      a
rla'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
rlr' k
rk a
ra Map k a
rr)
                )
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl' k
rk a
ra Map k a
rr))
                ( \Map k a
rll' k
rlk' a
rla' Map k a
rlr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
rll')
                      k
rlk'
                      a
rla'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr' k
rk a
ra Map k a
rr)
                )
                Map k a
rl'
      )
      (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rll k
rlk a
rla Map k a
rlr) k
rk a
ra Map k a
rr))
      Map k a
rl
  insertLlr :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLlr Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
forall k a. Map k a
E) k
k0 a
a0 (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
r))
      (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
lrl k
lrk a
lra Map k a
lrr)) k
k a
a Map k a
r)
      ( \Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ ->
          let lr' :: Map k a
lr' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
lrl k
lrk a
lra Map k a
lrr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map'
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L9")
                ( \Map k a
lrl' k
lrk' a
lra' Map k a
lrr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl')
                      k
lrk'
                      a
lra'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
lrr' k
k a
a Map k a
r)
                )
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lr') k
k a
a Map k a
r)
                ( \Map k a
lrl' k
lrk' a
lra' Map k a
lrr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
ll k
lk a
la Map k a
lrl')
                      k
lrk'
                      a
lra'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr' k
k a
a Map k a
r)
                )
                Map k a
lr'
      )
      (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
lrl k
lrk a
lra Map k a
lrr)) k
k a
a Map k a
r)
      Map k a
lr

{-
 - Examples
 -}

{- $examples
'fromList': /tail-biased/ means that if a list of @(key, value)@ pairs contains
pairs with identical keys, the rightmost one is kept.

>>> fromList [('a',1),('b',2),('c',3),('b',4),('a',5)]
[('a',5),('b',4),('c',3)]

'fromListWith', 'fromListWithKey': If a list of @(key, value)@ pairs contains
pairs with identical keys, the leftmost one is inserted as is and the subsequent
ones adjust the value with the combining function left-associatively. The
combining function takes the new value as the left operand, and the existing
value as the right operand.

>>> fromListWith (<>) [(1,"a"),(2,"b"),(1,"c"),(1,"d")]
[(1,"dca"),(2,"b")]
>>> let f k new old = old <> ", " <> show k <> new
>>> fromListWithKey f [(1,"a"),(2,"b"),(1,"c"),(1,"d")]
[(1,"a, 1c, 1d"),(2,"b")]

'intersection', 'union', 'unions': /left-biased/ means that if the operands
contain bins with identical keys, the bins from the /left/ operand is kept.

>>> fromList [('a',1),('b',2)] `intersection` fromList [('c',3),('b',4),('a',5)]
[('a',1),('b',2)]
>>> fromList [('a',1),('b',2)] `union` fromList [('c',3),('b',4),('a',5)]
[('a',1),('b',2),('c',3)]

'insertWith', 'insertWithKey': If the key does not exist in the map, it is
inserted with the given value as is. Otherwise, the existing value is adjusted
with the combining function, which takes the given value as the left operand and
the existing value as the right operand.

>>> insertWith (<>) 1 "foo" $ fromList [(2,"bar"),(3,"baz")]
[(1,"foo"),(2,"bar"),(3,"baz")]
>>> insertWith (<>) 2 "foo" $ fromList [(2,"bar"),(3,"baz")]
[(2,"foobar"),(3,"baz")]
>>> let f k new old = k + new - old
>>> insertWithKey f 1 2 $ fromList [(2,3),(3,5)]
[(1,2),(2,3),(3,5)]
>>> insertWithKey f 2 7 $ fromList [(2,3),(3,5)]
[(2,6),(3,5)]

'update': If the key does not exist, the map is unchanged. If the key exists and
the result of the operation is @Just x@, the value of the corresponding bin is
updated to @x@. If the key exists and the result of the operation is @Nothing@,
the corresponding bin is removed.

>>> f a = if a == 2 then Just 9 else Nothing
>>> update f 'c' $ fromList [('a',1),('b',2)]
[('a',1),('b',2)]
>>> update f 'b' $ fromList [('a',1),('b',2)]
[('a',1),('b',9)]
>>> update f 'a' $ fromList [('a',1),('b',2)]
[('b',2)]
-}