{-|
Module      : What4.Utils.AnnotatedMap
Description : A finite map data structure with monoidal annotations
Copyright   : (c) Galois Inc, 2019-2020
License     : BSD3
Maintainer  : huffman@galois.com

A finite map data structure with monoidal annotations.
-}

{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}

module What4.Utils.AnnotatedMap
  ( AnnotatedMap
  , null
  , empty
  , singleton
  , size
  , lookup
  , delete
  , annotation
  , toList
  , fromAscList
  , insert
  , alter
  , alterF
  , union
  , unionWith
  , unionWithKeyMaybe
  , filter
  , mapMaybe
  , mapMaybeWithKey
  , traverseMaybeWithKey
  , difference
  , mergeWithKey
  , mergeWithKeyM
  , mergeA
  , eqBy
  ) where

import           Data.Functor.Identity
import qualified Data.Foldable as Foldable
import           Data.Foldable (foldl')
import           Prelude hiding (null, filter, lookup)

import qualified Data.FingerTree as FT
import           Data.FingerTree ((><), (<|))

----------------------------------------------------------------------
-- Operations on FingerTrees

filterFingerTree ::
  FT.Measured v a =>
  (a -> Bool) -> FT.FingerTree v a -> FT.FingerTree v a
filterFingerTree :: forall v a.
Measured v a =>
(a -> Bool) -> FingerTree v a -> FingerTree v a
filterFingerTree a -> Bool
p =
  forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\FingerTree v a
xs a
x -> if a -> Bool
p a
x then FingerTree v a
xs forall v a. Measured v a => FingerTree v a -> a -> FingerTree v a
FT.|> a
x else FingerTree v a
xs) forall v a. Measured v a => FingerTree v a
FT.empty

mapMaybeFingerTree ::
  (FT.Measured v2 a2) =>
  (a1 -> Maybe a2) -> FT.FingerTree v1 a1 -> FT.FingerTree v2 a2
mapMaybeFingerTree :: forall v2 a2 a1 v1.
Measured v2 a2 =>
(a1 -> Maybe a2) -> FingerTree v1 a1 -> FingerTree v2 a2
mapMaybeFingerTree a1 -> Maybe a2
f =
  forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\FingerTree v2 a2
xs a1
x -> forall b a. b -> (a -> b) -> Maybe a -> b
maybe FingerTree v2 a2
xs (FingerTree v2 a2
xs forall v a. Measured v a => FingerTree v a -> a -> FingerTree v a
FT.|>) (a1 -> Maybe a2
f a1
x)) forall v a. Measured v a => FingerTree v a
FT.empty

traverseMaybeFingerTree ::
  (Applicative f, FT.Measured v2 a2) =>
  (a1 -> f (Maybe a2)) -> FT.FingerTree v1 a1 -> f (FT.FingerTree v2 a2)
traverseMaybeFingerTree :: forall (f :: Type -> Type) v2 a2 a1 v1.
(Applicative f, Measured v2 a2) =>
(a1 -> f (Maybe a2)) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
traverseMaybeFingerTree a1 -> f (Maybe a2)
f =
   forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\f (FingerTree v2 a2)
m a1
x -> forall {v} {a}.
Measured v a =>
FingerTree v a -> Maybe a -> FingerTree v a
rebuild forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> f (FingerTree v2 a2)
m forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> a1 -> f (Maybe a2)
f a1
x) (forall (f :: Type -> Type) a. Applicative f => a -> f a
pure forall v a. Measured v a => FingerTree v a
FT.empty)
 where
 rebuild :: FingerTree v a -> Maybe a -> FingerTree v a
rebuild FingerTree v a
ys Maybe a
Nothing  = FingerTree v a
ys
 rebuild FingerTree v a
ys (Just a
y) = FingerTree v a
ys forall v a. Measured v a => FingerTree v a -> a -> FingerTree v a
FT.|> a
y

----------------------------------------------------------------------
-- Tags

data Tag k v = NoTag | Tag !Int k v
-- The Int is there to support the size function.

instance (Ord k, Semigroup v) => Semigroup (Tag k v) where
  <> :: Tag k v -> Tag k v -> Tag k v
(<>) = forall v k. Semigroup v => Tag k v -> Tag k v -> Tag k v
unionTag

instance (Ord k, Semigroup v) => Monoid (Tag k v) where
  mempty :: Tag k v
mempty  = forall k v. Tag k v
NoTag

unionTag :: (Semigroup v) => Tag k v -> Tag k v -> Tag k v
unionTag :: forall v k. Semigroup v => Tag k v -> Tag k v -> Tag k v
unionTag Tag k v
x Tag k v
NoTag = Tag k v
x
unionTag Tag k v
NoTag Tag k v
y = Tag k v
y
unionTag (Tag Int
ix k
_ v
vx) (Tag Int
iy k
ky v
vy) =
  forall k v. Int -> k -> v -> Tag k v
Tag (Int
ix forall a. Num a => a -> a -> a
+ Int
iy) k
ky (v
vx forall a. Semigroup a => a -> a -> a
<> v
vy)

----------------------------------------------------------------------

newtype AnnotatedMap k v a =
  AnnotatedMap { forall k v a.
AnnotatedMap k v a -> FingerTree (Tag k v) (Entry k v a)
annotatedMap :: FT.FingerTree (Tag k v) (Entry k v a) }
  -- Invariant: The entries in the fingertree must be sorted by key,
  -- strictly increasing from left to right.

data Entry k v a = Entry k v a
  deriving (forall a b. a -> Entry k v b -> Entry k v a
forall a b. (a -> b) -> Entry k v a -> Entry k v b
forall k v a b. a -> Entry k v b -> Entry k v a
forall k v a b. (a -> b) -> Entry k v a -> Entry k v b
forall (f :: Type -> Type).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Entry k v b -> Entry k v a
$c<$ :: forall k v a b. a -> Entry k v b -> Entry k v a
fmap :: forall a b. (a -> b) -> Entry k v a -> Entry k v b
$cfmap :: forall k v a b. (a -> b) -> Entry k v a -> Entry k v b
Functor, forall a. Entry k v a -> Bool
forall m a. Monoid m => (a -> m) -> Entry k v a -> m
forall a b. (a -> b -> b) -> b -> Entry k v a -> b
forall k v a. Eq a => a -> Entry k v a -> Bool
forall k v a. Num a => Entry k v a -> a
forall k v a. Ord a => Entry k v a -> a
forall k v m. Monoid m => Entry k v m -> m
forall k v a. Entry k v a -> Bool
forall k v a. Entry k v a -> Int
forall k v a. Entry k v a -> [a]
forall k v a. (a -> a -> a) -> Entry k v a -> a
forall k v m a. Monoid m => (a -> m) -> Entry k v a -> m
forall k v b a. (b -> a -> b) -> b -> Entry k v a -> b
forall k v a b. (a -> b -> b) -> b -> Entry k v a -> b
forall (t :: Type -> Type).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => Entry k v a -> a
$cproduct :: forall k v a. Num a => Entry k v a -> a
sum :: forall a. Num a => Entry k v a -> a
$csum :: forall k v a. Num a => Entry k v a -> a
minimum :: forall a. Ord a => Entry k v a -> a
$cminimum :: forall k v a. Ord a => Entry k v a -> a
maximum :: forall a. Ord a => Entry k v a -> a
$cmaximum :: forall k v a. Ord a => Entry k v a -> a
elem :: forall a. Eq a => a -> Entry k v a -> Bool
$celem :: forall k v a. Eq a => a -> Entry k v a -> Bool
length :: forall a. Entry k v a -> Int
$clength :: forall k v a. Entry k v a -> Int
null :: forall a. Entry k v a -> Bool
$cnull :: forall k v a. Entry k v a -> Bool
toList :: forall a. Entry k v a -> [a]
$ctoList :: forall k v a. Entry k v a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Entry k v a -> a
$cfoldl1 :: forall k v a. (a -> a -> a) -> Entry k v a -> a
foldr1 :: forall a. (a -> a -> a) -> Entry k v a -> a
$cfoldr1 :: forall k v a. (a -> a -> a) -> Entry k v a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Entry k v a -> b
$cfoldl' :: forall k v b a. (b -> a -> b) -> b -> Entry k v a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Entry k v a -> b
$cfoldl :: forall k v b a. (b -> a -> b) -> b -> Entry k v a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Entry k v a -> b
$cfoldr' :: forall k v a b. (a -> b -> b) -> b -> Entry k v a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Entry k v a -> b
$cfoldr :: forall k v a b. (a -> b -> b) -> b -> Entry k v a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Entry k v a -> m
$cfoldMap' :: forall k v m a. Monoid m => (a -> m) -> Entry k v a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Entry k v a -> m
$cfoldMap :: forall k v m a. Monoid m => (a -> m) -> Entry k v a -> m
fold :: forall m. Monoid m => Entry k v m -> m
$cfold :: forall k v m. Monoid m => Entry k v m -> m
Foldable, forall k v. Functor (Entry k v)
forall k v. Foldable (Entry k v)
forall k v (m :: Type -> Type) a.
Monad m =>
Entry k v (m a) -> m (Entry k v a)
forall k v (f :: Type -> Type) a.
Applicative f =>
Entry k v (f a) -> f (Entry k v a)
forall k v (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Entry k v a -> m (Entry k v b)
forall k v (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Entry k v a -> f (Entry k v b)
forall (t :: Type -> Type).
Functor t
-> Foldable t
-> (forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: Type -> Type) a.
    Applicative f =>
    t (f a) -> f (t a))
-> (forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: Type -> Type) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Entry k v a -> f (Entry k v b)
sequence :: forall (m :: Type -> Type) a.
Monad m =>
Entry k v (m a) -> m (Entry k v a)
$csequence :: forall k v (m :: Type -> Type) a.
Monad m =>
Entry k v (m a) -> m (Entry k v a)
mapM :: forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Entry k v a -> m (Entry k v b)
$cmapM :: forall k v (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Entry k v a -> m (Entry k v b)
sequenceA :: forall (f :: Type -> Type) a.
Applicative f =>
Entry k v (f a) -> f (Entry k v a)
$csequenceA :: forall k v (f :: Type -> Type) a.
Applicative f =>
Entry k v (f a) -> f (Entry k v a)
traverse :: forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Entry k v a -> f (Entry k v b)
$ctraverse :: forall k v (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Entry k v a -> f (Entry k v b)
Traversable)

keyOf :: Entry k v a -> k
keyOf :: forall k v a. Entry k v a -> k
keyOf (Entry k
k v
_ a
_) = k
k

valOf :: Entry k v a -> (v, a)
valOf :: forall k v a. Entry k v a -> (v, a)
valOf (Entry k
_ v
v a
a) = (v
v, a
a)

instance (Ord k, Semigroup v) => FT.Measured (Tag k v) (Entry k v a) where
  measure :: Entry k v a -> Tag k v
measure (Entry k
k v
v a
_) = forall k v. Int -> k -> v -> Tag k v
Tag Int
1 k
k v
v

instance (Ord k, Semigroup v) => Functor (AnnotatedMap k v) where
  fmap :: forall a b. (a -> b) -> AnnotatedMap k v a -> AnnotatedMap k v b
fmap a -> b
f (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
    forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (forall a b v. (a -> b) -> FingerTree v a -> FingerTree v b
FT.unsafeFmap (forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) FingerTree (Tag k v) (Entry k v a)
ft)

instance (Ord k, Semigroup v) => Foldable.Foldable (AnnotatedMap k v) where
  foldr :: forall a b. (a -> b -> b) -> b -> AnnotatedMap k v a -> b
foldr a -> b -> b
f b
z (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
    forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z [ a
a | Entry k
_ v
_ a
a <- forall (t :: Type -> Type) a. Foldable t => t a -> [a]
Foldable.toList FingerTree (Tag k v) (Entry k v a)
ft ]

instance (Ord k, Semigroup v) => Traversable (AnnotatedMap k v) where
  traverse :: forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> AnnotatedMap k v a -> f (AnnotatedMap k v b)
traverse a -> f b
f (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
    forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: Type -> Type) a b v.
Applicative f =>
(a -> f b) -> FingerTree v a -> f (FingerTree v b)
FT.unsafeTraverse (forall (t :: Type -> Type) (f :: Type -> Type) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f) FingerTree (Tag k v) (Entry k v a)
ft

annotation :: (Ord k, Semigroup v) => AnnotatedMap k v a -> Maybe v
annotation :: forall k v a. (Ord k, Semigroup v) => AnnotatedMap k v a -> Maybe v
annotation (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  case forall v a. Measured v a => a -> v
FT.measure FingerTree (Tag k v) (Entry k v a)
ft of
    Tag Int
_ k
_ v
v -> forall a. a -> Maybe a
Just v
v
    Tag k v
NoTag     -> forall a. Maybe a
Nothing

toList :: AnnotatedMap k v a -> [(k, a)]
toList :: forall k v a. AnnotatedMap k v a -> [(k, a)]
toList (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  [ (k
k, a
a) | Entry k
k v
_ a
a <- forall (t :: Type -> Type) a. Foldable t => t a -> [a]
Foldable.toList FingerTree (Tag k v) (Entry k v a)
ft ]

fromAscList :: (Ord k, Semigroup v) => [(k,v,a)] -> AnnotatedMap k v a
fromAscList :: forall k v a.
(Ord k, Semigroup v) =>
[(k, v, a)] -> AnnotatedMap k v a
fromAscList = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall v a. Measured v a => [a] -> FingerTree v a
FT.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {k} {v} {a}. (k, v, a) -> Entry k v a
f
  where
    f :: (k, v, a) -> Entry k v a
f (k
k, v
v, a
a) = forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
a

listEqBy :: (a -> a -> Bool) -> [a] -> [a] -> Bool
listEqBy :: forall a. (a -> a -> Bool) -> [a] -> [a] -> Bool
listEqBy a -> a -> Bool
_ [] [] = Bool
True
listEqBy a -> a -> Bool
f (a
x : [a]
xs) (a
y : [a]
ys)
  | a -> a -> Bool
f a
x a
y = forall a. (a -> a -> Bool) -> [a] -> [a] -> Bool
listEqBy a -> a -> Bool
f [a]
xs [a]
ys
listEqBy a -> a -> Bool
_ [a]
_ [a]
_ = Bool
False

eqBy :: Eq k => (a -> a -> Bool) -> AnnotatedMap k v a -> AnnotatedMap k v a -> Bool
eqBy :: forall k a v.
Eq k =>
(a -> a -> Bool)
-> AnnotatedMap k v a -> AnnotatedMap k v a -> Bool
eqBy a -> a -> Bool
f AnnotatedMap k v a
x AnnotatedMap k v a
y = forall a. (a -> a -> Bool) -> [a] -> [a] -> Bool
listEqBy (\(k
kx,a
ax) (k
ky,a
ay) -> k
kx forall a. Eq a => a -> a -> Bool
== k
ky Bool -> Bool -> Bool
&& a -> a -> Bool
f a
ax a
ay) (forall k v a. AnnotatedMap k v a -> [(k, a)]
toList AnnotatedMap k v a
x) (forall k v a. AnnotatedMap k v a -> [(k, a)]
toList AnnotatedMap k v a
y)

null :: AnnotatedMap k v a -> Bool
null :: forall k v a. AnnotatedMap k v a -> Bool
null (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) = forall v a. FingerTree v a -> Bool
FT.null FingerTree (Tag k v) (Entry k v a)
ft

empty :: (Ord k, Semigroup v) => AnnotatedMap k v a
empty :: forall k v a. (Ord k, Semigroup v) => AnnotatedMap k v a
empty = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall v a. Measured v a => FingerTree v a
FT.empty

singleton :: (Ord k, Semigroup v) => k -> v -> a -> AnnotatedMap k v a
singleton :: forall k v a.
(Ord k, Semigroup v) =>
k -> v -> a -> AnnotatedMap k v a
singleton k
k v
v a
a =
  forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (forall v a. Measured v a => a -> FingerTree v a
FT.singleton (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
a))

size :: (Ord k, Semigroup v) => AnnotatedMap k v a -> Int
size :: forall k v a. (Ord k, Semigroup v) => AnnotatedMap k v a -> Int
size (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  case forall v a. Measured v a => a -> v
FT.measure FingerTree (Tag k v) (Entry k v a)
ft of
    Tag Int
i k
_ v
_ -> Int
i
    Tag k v
NoTag     -> Int
0

splitAtKey ::
  (Ord k, Semigroup v) =>
  k -> FT.FingerTree (Tag k v) (Entry k v a) ->
  ( FT.FingerTree (Tag k v) (Entry k v a)
  , Maybe (Entry k v a)
  , FT.FingerTree (Tag k v) (Entry k v a)
  )
splitAtKey :: forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft =
  case forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Tag k v) (Entry k v a)
r of
    Entry k v a
e FT.:< FingerTree (Tag k v) (Entry k v a)
r' | k
k forall a. Eq a => a -> a -> Bool
== forall k v a. Entry k v a -> k
keyOf Entry k v a
e -> (FingerTree (Tag k v) (Entry k v a)
l, forall a. a -> Maybe a
Just Entry k v a
e, FingerTree (Tag k v) (Entry k v a)
r')
    ViewL (FingerTree (Tag k v)) (Entry k v a)
_ -> (FingerTree (Tag k v) (Entry k v a)
l, forall a. Maybe a
Nothing, FingerTree (Tag k v) (Entry k v a)
r)
  where
    (FingerTree (Tag k v) (Entry k v a)
l, FingerTree (Tag k v) (Entry k v a)
r) = forall v a.
Measured v a =>
(v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)
FT.split forall {v}. Tag k v -> Bool
found FingerTree (Tag k v) (Entry k v a)
ft
    found :: Tag k v -> Bool
found Tag k v
NoTag = Bool
False
    found (Tag Int
_ k
k' v
_) = k
k forall a. Ord a => a -> a -> Bool
<= k
k'

insert ::
  (Ord k, Semigroup v) =>
  k -> v -> a -> AnnotatedMap k v a -> AnnotatedMap k v a
insert :: forall k v a.
(Ord k, Semigroup v) =>
k -> v -> a -> AnnotatedMap k v a -> AnnotatedMap k v a
insert k
k v
v a
a (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
a forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
r))
  where
    (FingerTree (Tag k v) (Entry k v a)
l, Maybe (Entry k v a)
_, FingerTree (Tag k v) (Entry k v a)
r) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft

lookup :: (Ord k, Semigroup v) => k -> AnnotatedMap k v a -> Maybe (v, a)
lookup :: forall k v a.
(Ord k, Semigroup v) =>
k -> AnnotatedMap k v a -> Maybe (v, a)
lookup k
k (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) = forall k v a. Entry k v a -> (v, a)
valOf forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (Entry k v a)
m
  where
    (FingerTree (Tag k v) (Entry k v a)
_, Maybe (Entry k v a)
m, FingerTree (Tag k v) (Entry k v a)
_) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft

delete :: (Ord k, Semigroup v) => k -> AnnotatedMap k v a -> AnnotatedMap k v a
delete :: forall k v a.
(Ord k, Semigroup v) =>
k -> AnnotatedMap k v a -> AnnotatedMap k v a
delete k
k m :: AnnotatedMap k v a
m@(AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  case forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft of
    (FingerTree (Tag k v) (Entry k v a)
_, Maybe (Entry k v a)
Nothing, FingerTree (Tag k v) (Entry k v a)
_) -> AnnotatedMap k v a
m
    (FingerTree (Tag k v) (Entry k v a)
l, Just Entry k v a
_, FingerTree (Tag k v) (Entry k v a)
r)  -> forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Tag k v) (Entry k v a)
r)

alter ::
  (Ord k, Semigroup v) =>
  (Maybe (v, a) -> Maybe (v, a)) -> k -> AnnotatedMap k v a -> AnnotatedMap k v a
alter :: forall k v a.
(Ord k, Semigroup v) =>
(Maybe (v, a) -> Maybe (v, a))
-> k -> AnnotatedMap k v a -> AnnotatedMap k v a
alter Maybe (v, a) -> Maybe (v, a)
f k
k (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  case Maybe (v, a) -> Maybe (v, a)
f (forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v a. Entry k v a -> (v, a)
valOf Maybe (Entry k v a)
m) of
    Maybe (v, a)
Nothing -> forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Tag k v) (Entry k v a)
r)
    Just (v
v, a
a) -> forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
a forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
r))
  where
    (FingerTree (Tag k v) (Entry k v a)
l, Maybe (Entry k v a)
m, FingerTree (Tag k v) (Entry k v a)
r) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft

alterF ::
  (Functor f, Ord k, Semigroup v) =>
  (Maybe (v, a) -> f (Maybe (v, a))) -> k -> AnnotatedMap k v a -> f (AnnotatedMap k v a)
alterF :: forall (f :: Type -> Type) k v a.
(Functor f, Ord k, Semigroup v) =>
(Maybe (v, a) -> f (Maybe (v, a)))
-> k -> AnnotatedMap k v a -> f (AnnotatedMap k v a)
alterF Maybe (v, a) -> f (Maybe (v, a))
f k
k (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) = Maybe (v, a) -> AnnotatedMap k v a
rebuild forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (v, a) -> f (Maybe (v, a))
f (forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v a. Entry k v a -> (v, a)
valOf Maybe (Entry k v a)
m)
  where
    (FingerTree (Tag k v) (Entry k v a)
l, Maybe (Entry k v a)
m, FingerTree (Tag k v) (Entry k v a)
r) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey k
k FingerTree (Tag k v) (Entry k v a)
ft

    rebuild :: Maybe (v, a) -> AnnotatedMap k v a
rebuild Maybe (v, a)
Nothing       = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Tag k v) (Entry k v a)
r)
    rebuild (Just (v
v, a
a)) = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
a) forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
r)


union ::
  (Ord k, Semigroup v) =>
  AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
union :: forall k v a.
(Ord k, Semigroup v) =>
AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
union = forall k v a.
(Ord k, Semigroup v) =>
(Entry k v a -> Entry k v a -> Maybe (Entry k v a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionGeneric (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Maybe a
Just)

unionWith ::
  (Ord k, Semigroup v) =>
  ((v, a) -> (v, a) -> (v, a)) ->
  AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionWith :: forall k v a.
(Ord k, Semigroup v) =>
((v, a) -> (v, a) -> (v, a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionWith (v, a) -> (v, a) -> (v, a)
f = forall k v a.
(Ord k, Semigroup v) =>
(Entry k v a -> Entry k v a -> Maybe (Entry k v a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionGeneric forall {k} {k}. Entry k v a -> Entry k v a -> Maybe (Entry k v a)
g
  where
    g :: Entry k v a -> Entry k v a -> Maybe (Entry k v a)
g (Entry k
k v
v1 a
x1) (Entry k
_ v
v2 a
x2) = forall a. a -> Maybe a
Just (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v3 a
x3)
      where (v
v3, a
x3) = (v, a) -> (v, a) -> (v, a)
f (v
v1, a
x1) (v
v2, a
x2)

unionWithKeyMaybe ::
  (Ord k, Semigroup v) =>
  (k -> a -> a -> Maybe (v, a)) ->
  AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionWithKeyMaybe :: forall k v a.
(Ord k, Semigroup v) =>
(k -> a -> a -> Maybe (v, a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionWithKeyMaybe k -> a -> a -> Maybe (v, a)
f = forall k v a.
(Ord k, Semigroup v) =>
(Entry k v a -> Entry k v a -> Maybe (Entry k v a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionGeneric forall {v} {k} {v}.
Entry k v a -> Entry k v a -> Maybe (Entry k v a)
g
  where g :: Entry k v a -> Entry k v a -> Maybe (Entry k v a)
g (Entry k
k v
_ a
x) (Entry k
_ v
_ a
y) = forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(v
v, a
z) -> forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
z) (k -> a -> a -> Maybe (v, a)
f k
k a
x a
y)

unionGeneric ::
  (Ord k, Semigroup v) =>
  (Entry k v a -> Entry k v a -> Maybe (Entry k v a)) ->
  AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionGeneric :: forall k v a.
(Ord k, Semigroup v) =>
(Entry k v a -> Entry k v a -> Maybe (Entry k v a))
-> AnnotatedMap k v a -> AnnotatedMap k v a -> AnnotatedMap k v a
unionGeneric Entry k v a -> Entry k v a -> Maybe (Entry k v a)
f (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft1) (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft2) = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge1 FingerTree (Tag k v) (Entry k v a)
ft1 FingerTree (Tag k v) (Entry k v a)
ft2)
  where
    merge1 :: FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge1 FingerTree (Tag k v) (Entry k v a)
xs FingerTree (Tag k v) (Entry k v a)
ys =
      case forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Tag k v) (Entry k v a)
xs of
        ViewL (FingerTree (Tag k v)) (Entry k v a)
FT.EmptyL -> FingerTree (Tag k v) (Entry k v a)
ys
        Entry k v a
x FT.:< FingerTree (Tag k v) (Entry k v a)
xs' ->
          case Maybe (Entry k v a)
ym of
            Maybe (Entry k v a)
Nothing -> FingerTree (Tag k v) (Entry k v a)
ys1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (Entry k v a
x forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge2 FingerTree (Tag k v) (Entry k v a)
xs' FingerTree (Tag k v) (Entry k v a)
ys2)
            Just Entry k v a
y ->
              case Entry k v a -> Entry k v a -> Maybe (Entry k v a)
f Entry k v a
x Entry k v a
y of
                Maybe (Entry k v a)
Nothing -> FingerTree (Tag k v) (Entry k v a)
ys1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge2 FingerTree (Tag k v) (Entry k v a)
xs' FingerTree (Tag k v) (Entry k v a)
ys2
                Just Entry k v a
z -> FingerTree (Tag k v) (Entry k v a)
ys1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (Entry k v a
z forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge2 FingerTree (Tag k v) (Entry k v a)
xs' FingerTree (Tag k v) (Entry k v a)
ys2)
          where
            (FingerTree (Tag k v) (Entry k v a)
ys1, Maybe (Entry k v a)
ym, FingerTree (Tag k v) (Entry k v a)
ys2) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey (forall k v a. Entry k v a -> k
keyOf Entry k v a
x) FingerTree (Tag k v) (Entry k v a)
ys

    merge2 :: FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge2 FingerTree (Tag k v) (Entry k v a)
xs FingerTree (Tag k v) (Entry k v a)
ys =
      case forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Tag k v) (Entry k v a)
ys of
        ViewL (FingerTree (Tag k v)) (Entry k v a)
FT.EmptyL -> FingerTree (Tag k v) (Entry k v a)
xs
        Entry k v a
y FT.:< FingerTree (Tag k v) (Entry k v a)
ys' ->
          case Maybe (Entry k v a)
xm of
            Maybe (Entry k v a)
Nothing -> FingerTree (Tag k v) (Entry k v a)
xs1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (Entry k v a
y forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge1 FingerTree (Tag k v) (Entry k v a)
xs2 FingerTree (Tag k v) (Entry k v a)
ys')
            Just Entry k v a
x ->
              case Entry k v a -> Entry k v a -> Maybe (Entry k v a)
f Entry k v a
x Entry k v a
y of
                Maybe (Entry k v a)
Nothing -> FingerTree (Tag k v) (Entry k v a)
xs1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge1 FingerTree (Tag k v) (Entry k v a)
xs2 FingerTree (Tag k v) (Entry k v a)
ys'
                Just Entry k v a
z -> FingerTree (Tag k v) (Entry k v a)
xs1 forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (Entry k v a
z forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
-> FingerTree (Tag k v) (Entry k v a)
merge1 FingerTree (Tag k v) (Entry k v a)
xs2 FingerTree (Tag k v) (Entry k v a)
ys')
          where
            (FingerTree (Tag k v) (Entry k v a)
xs1, Maybe (Entry k v a)
xm, FingerTree (Tag k v) (Entry k v a)
xs2) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey (forall k v a. Entry k v a -> k
keyOf Entry k v a
y) FingerTree (Tag k v) (Entry k v a)
xs

filter ::
  (Ord k, Semigroup v) =>
  (a -> Bool) -> AnnotatedMap k v a -> AnnotatedMap k v a
filter :: forall k v a.
(Ord k, Semigroup v) =>
(a -> Bool) -> AnnotatedMap k v a -> AnnotatedMap k v a
filter a -> Bool
f (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (forall v a.
Measured v a =>
(a -> Bool) -> FingerTree v a -> FingerTree v a
filterFingerTree forall {k} {v}. Entry k v a -> Bool
g FingerTree (Tag k v) (Entry k v a)
ft)
  where g :: Entry k v a -> Bool
g (Entry k
_ v
_ a
a) = a -> Bool
f a
a

mapMaybe ::
  (Ord k, Semigroup v) =>
  (a -> Maybe b) ->
  AnnotatedMap k v a -> AnnotatedMap k v b
mapMaybe :: forall k v a b.
(Ord k, Semigroup v) =>
(a -> Maybe b) -> AnnotatedMap k v a -> AnnotatedMap k v b
mapMaybe a -> Maybe b
f (AnnotatedMap FingerTree (Tag k v) (Entry k v a)
ft) =
  forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (forall v2 a2 a1 v1.
Measured v2 a2 =>
(a1 -> Maybe a2) -> FingerTree v1 a1 -> FingerTree v2 a2
mapMaybeFingerTree forall {k} {v}. Entry k v a -> Maybe (Entry k v b)
g FingerTree (Tag k v) (Entry k v a)
ft)
  where g :: Entry k v a -> Maybe (Entry k v b)
g (Entry k
k v
v a
a) = forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe b
f a
a

mapMaybeWithKey ::
  (Ord k, Semigroup v2) =>
  (k -> v1 -> a1 -> Maybe (v2, a2)) ->
  AnnotatedMap k v1 a1 -> AnnotatedMap k v2 a2
mapMaybeWithKey :: forall k v2 v1 a1 a2.
(Ord k, Semigroup v2) =>
(k -> v1 -> a1 -> Maybe (v2, a2))
-> AnnotatedMap k v1 a1 -> AnnotatedMap k v2 a2
mapMaybeWithKey k -> v1 -> a1 -> Maybe (v2, a2)
f (AnnotatedMap FingerTree (Tag k v1) (Entry k v1 a1)
ft) =
  forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap (forall v2 a2 a1 v1.
Measured v2 a2 =>
(a1 -> Maybe a2) -> FingerTree v1 a1 -> FingerTree v2 a2
mapMaybeFingerTree Entry k v1 a1 -> Maybe (Entry k v2 a2)
g FingerTree (Tag k v1) (Entry k v1 a1)
ft)
  where
    g :: Entry k v1 a1 -> Maybe (Entry k v2 a2)
g (Entry k
k v1
v1 a1
x1) = (\(v2
v2, a2
x2) -> forall k v a. k -> v -> a -> Entry k v a
Entry k
k v2
v2 a2
x2) forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> a1 -> Maybe (v2, a2)
f k
k v1
v1 a1
x1

traverseMaybeWithKey ::
  (Applicative f, Ord k, Semigroup v2) =>
  (k -> v1 -> a1 -> f (Maybe (v2, a2))) ->
  AnnotatedMap k v1 a1 -> f (AnnotatedMap k v2 a2)
traverseMaybeWithKey :: forall (f :: Type -> Type) k v2 v1 a1 a2.
(Applicative f, Ord k, Semigroup v2) =>
(k -> v1 -> a1 -> f (Maybe (v2, a2)))
-> AnnotatedMap k v1 a1 -> f (AnnotatedMap k v2 a2)
traverseMaybeWithKey k -> v1 -> a1 -> f (Maybe (v2, a2))
f (AnnotatedMap FingerTree (Tag k v1) (Entry k v1 a1)
ft) =
  forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: Type -> Type) v2 a2 a1 v1.
(Applicative f, Measured v2 a2) =>
(a1 -> f (Maybe a2)) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
traverseMaybeFingerTree Entry k v1 a1 -> f (Maybe (Entry k v2 a2))
g FingerTree (Tag k v1) (Entry k v1 a1)
ft
  where
    g :: Entry k v1 a1 -> f (Maybe (Entry k v2 a2))
g (Entry k
k v1
v1 a1
x1) = forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(v2
v2, a2
x2) -> forall k v a. k -> v -> a -> Entry k v a
Entry k
k v2
v2 a2
x2) forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> a1 -> f (Maybe (v2, a2))
f k
k v1
v1 a1
x1

difference ::
  (Ord k, Semigroup v, Semigroup w) =>
  AnnotatedMap k v a -> AnnotatedMap k w b -> AnnotatedMap k v a
difference :: forall k v w a b.
(Ord k, Semigroup v, Semigroup w) =>
AnnotatedMap k v a -> AnnotatedMap k w b -> AnnotatedMap k v a
difference AnnotatedMap k v a
a AnnotatedMap k w b
b = forall a. Identity a -> a
runIdentity forall a b. (a -> b) -> a -> b
$ forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(Entry k u a -> Entry k v b -> m (Maybe (Entry k w c)))
-> (AnnotatedMap k u a -> m (AnnotatedMap k w c))
-> (AnnotatedMap k v b -> m (AnnotatedMap k w c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeGeneric (\Entry k v a
_ Entry k w b
_ -> forall a. a -> Identity a
Identity forall a. Maybe a
Nothing) forall (f :: Type -> Type) a. Applicative f => a -> f a
pure (forall a b. a -> b -> a
const (forall (f :: Type -> Type) a. Applicative f => a -> f a
pure forall k v a. (Ord k, Semigroup v) => AnnotatedMap k v a
empty)) AnnotatedMap k v a
a AnnotatedMap k w b
b

mergeWithKey ::
  (Ord k, Semigroup u, Semigroup v, Semigroup w) =>
  (k -> (u, a) -> (v, b) -> Maybe (w, c)) {- ^ for keys present in both maps -} ->
  (AnnotatedMap k u a -> AnnotatedMap k w c) {- ^ for subtrees only in first map -} ->
  (AnnotatedMap k v b -> AnnotatedMap k w c) {- ^ for subtrees only in second map -} ->
  AnnotatedMap k u a -> AnnotatedMap k v b -> AnnotatedMap k w c
mergeWithKey :: forall k u v w a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w) =>
(k -> (u, a) -> (v, b) -> Maybe (w, c))
-> (AnnotatedMap k u a -> AnnotatedMap k w c)
-> (AnnotatedMap k v b -> AnnotatedMap k w c)
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> AnnotatedMap k w c
mergeWithKey k -> (u, a) -> (v, b) -> Maybe (w, c)
f AnnotatedMap k u a -> AnnotatedMap k w c
g1 AnnotatedMap k v b -> AnnotatedMap k w c
g2 AnnotatedMap k u a
m1 AnnotatedMap k v b
m2 = forall a. Identity a -> a
runIdentity forall a b. (a -> b) -> a -> b
$ forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(Entry k u a -> Entry k v b -> m (Maybe (Entry k w c)))
-> (AnnotatedMap k u a -> m (AnnotatedMap k w c))
-> (AnnotatedMap k v b -> m (AnnotatedMap k w c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeGeneric forall {k}.
Entry k u a -> Entry k v b -> Identity (Maybe (Entry k w c))
f' (forall (f :: Type -> Type) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnnotatedMap k u a -> AnnotatedMap k w c
g1) (forall (f :: Type -> Type) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnnotatedMap k v b -> AnnotatedMap k w c
g2) AnnotatedMap k u a
m1 AnnotatedMap k v b
m2
  where
    f' :: Entry k u a -> Entry k v b -> Identity (Maybe (Entry k w c))
f' (Entry k
k u
u a
a) (Entry k
_ v
v b
b) =
      forall a. a -> Identity a
Identity forall a b. (a -> b) -> a -> b
$
      case k -> (u, a) -> (v, b) -> Maybe (w, c)
f k
k (u
u, a
a) (v
v, b
b) of
        Maybe (w, c)
Nothing -> forall a. Maybe a
Nothing
        Just (w
w, c
c) -> forall a. a -> Maybe a
Just (forall k v a. k -> v -> a -> Entry k v a
Entry k
k w
w c
c)

mergeA ::
  (Ord k, Semigroup v, Applicative f) =>
  (k -> (v, a) -> (v, a) -> f (v,a)) ->
  AnnotatedMap k v a -> AnnotatedMap k v a -> f (AnnotatedMap k v a)
mergeA :: forall k v (f :: Type -> Type) a.
(Ord k, Semigroup v, Applicative f) =>
(k -> (v, a) -> (v, a) -> f (v, a))
-> AnnotatedMap k v a
-> AnnotatedMap k v a
-> f (AnnotatedMap k v a)
mergeA k -> (v, a) -> (v, a) -> f (v, a)
f AnnotatedMap k v a
m1 AnnotatedMap k v a
m2 = forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(Entry k u a -> Entry k v b -> m (Maybe (Entry k w c)))
-> (AnnotatedMap k u a -> m (AnnotatedMap k w c))
-> (AnnotatedMap k v b -> m (AnnotatedMap k w c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeGeneric forall {k}. Entry k v a -> Entry k v a -> f (Maybe (Entry k v a))
f' forall (f :: Type -> Type) a. Applicative f => a -> f a
pure forall (f :: Type -> Type) a. Applicative f => a -> f a
pure AnnotatedMap k v a
m1 AnnotatedMap k v a
m2
  where
    f' :: Entry k v a -> Entry k v a -> f (Maybe (Entry k v a))
f' (Entry k
k v
v1 a
x1) (Entry k
_ v
v2 a
x2) = forall {k} {v} {a}. k -> (v, a) -> Maybe (Entry k v a)
g k
k forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> (v, a) -> (v, a) -> f (v, a)
f k
k (v
v1, a
x1) (v
v2, a
x2)
    g :: k -> (v, a) -> Maybe (Entry k v a)
g k
k (v
v, a
x) = forall a. a -> Maybe a
Just (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
v a
x)

mergeWithKeyM :: (Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
  (k -> (u, a) -> (v, b) -> m (w, c)) ->
  (k -> (u, a) -> m (w, c)) ->
  (k -> (v, b) -> m (w, c)) ->
  AnnotatedMap k u a -> AnnotatedMap k v b -> m (AnnotatedMap k w c)
mergeWithKeyM :: forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(k -> (u, a) -> (v, b) -> m (w, c))
-> (k -> (u, a) -> m (w, c))
-> (k -> (v, b) -> m (w, c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeWithKeyM k -> (u, a) -> (v, b) -> m (w, c)
both k -> (u, a) -> m (w, c)
left k -> (v, b) -> m (w, c)
right = forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(Entry k u a -> Entry k v b -> m (Maybe (Entry k w c)))
-> (AnnotatedMap k u a -> m (AnnotatedMap k w c))
-> (AnnotatedMap k v b -> m (AnnotatedMap k w c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeGeneric forall {k}. Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))
both' AnnotatedMap k u a -> m (AnnotatedMap k w c)
left' AnnotatedMap k v b -> m (AnnotatedMap k w c)
right'
  where
    both' :: Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))
both' (Entry k
k u
u a
a) (Entry k
_ v
v b
b) = forall {k} {v} {a}. k -> (v, a) -> Maybe (Entry k v a)
q k
k forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> (u, a) -> (v, b) -> m (w, c)
both k
k (u
u, a
a) (v
v, b
b)
    left' :: AnnotatedMap k u a -> m (AnnotatedMap k w c)
left'  AnnotatedMap k u a
m = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: Type -> Type) v2 a2 a1 v1.
(Applicative f, Measured v2 a2) =>
(a1 -> f (Maybe a2)) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
traverseMaybeFingerTree Entry k u a -> m (Maybe (Entry k w c))
fl (forall k v a.
AnnotatedMap k v a -> FingerTree (Tag k v) (Entry k v a)
annotatedMap AnnotatedMap k u a
m)
    right' :: AnnotatedMap k v b -> m (AnnotatedMap k w c)
right' AnnotatedMap k v b
m = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: Type -> Type) v2 a2 a1 v1.
(Applicative f, Measured v2 a2) =>
(a1 -> f (Maybe a2)) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
traverseMaybeFingerTree Entry k v b -> m (Maybe (Entry k w c))
fr (forall k v a.
AnnotatedMap k v a -> FingerTree (Tag k v) (Entry k v a)
annotatedMap AnnotatedMap k v b
m)

    fl :: Entry k u a -> m (Maybe (Entry k w c))
fl (Entry k
k u
v a
x) = forall {k} {v} {a}. k -> (v, a) -> Maybe (Entry k v a)
q k
k forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> (u, a) -> m (w, c)
left k
k (u
v, a
x)
    fr :: Entry k v b -> m (Maybe (Entry k w c))
fr (Entry k
k v
v b
x) = forall {k} {v} {a}. k -> (v, a) -> Maybe (Entry k v a)
q k
k forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> (v, b) -> m (w, c)
right k
k (v
v, b
x)

    q :: k -> (v, a) -> Maybe (Entry k v a)
q k
k (v
a, a
b) = forall a. a -> Maybe a
Just (forall k v a. k -> v -> a -> Entry k v a
Entry k
k v
a a
b)


mergeGeneric ::
  (Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
  (Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))) {- ^ for keys present in both maps -} ->
  (AnnotatedMap k u a -> m (AnnotatedMap k w c)) {- ^ for subtrees only in first map -} ->
  (AnnotatedMap k v b -> m (AnnotatedMap k w c)) {- ^ for subtrees only in second map -} ->
  AnnotatedMap k u a -> AnnotatedMap k v b -> m (AnnotatedMap k w c)
mergeGeneric :: forall k u v w (m :: Type -> Type) a b c.
(Ord k, Semigroup u, Semigroup v, Semigroup w, Applicative m) =>
(Entry k u a -> Entry k v b -> m (Maybe (Entry k w c)))
-> (AnnotatedMap k u a -> m (AnnotatedMap k w c))
-> (AnnotatedMap k v b -> m (AnnotatedMap k w c))
-> AnnotatedMap k u a
-> AnnotatedMap k v b
-> m (AnnotatedMap k w c)
mergeGeneric Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))
f AnnotatedMap k u a -> m (AnnotatedMap k w c)
g1 AnnotatedMap k v b -> m (AnnotatedMap k w c)
g2 (AnnotatedMap FingerTree (Tag k u) (Entry k u a)
ft1) (AnnotatedMap FingerTree (Tag k v) (Entry k v b)
ft2) = forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> (FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge1 FingerTree (Tag k u) (Entry k u a)
ft1 FingerTree (Tag k v) (Entry k v b)
ft2)
  where
    g1' :: FingerTree (Tag k u) (Entry k u a)
-> m (FingerTree (Tag k w) (Entry k w c))
g1' FingerTree (Tag k u) (Entry k u a)
ft = forall k v a.
AnnotatedMap k v a -> FingerTree (Tag k v) (Entry k v a)
annotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> AnnotatedMap k u a -> m (AnnotatedMap k w c)
g1 (forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap FingerTree (Tag k u) (Entry k u a)
ft)
    g2' :: FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
g2' FingerTree (Tag k v) (Entry k v b)
ft = forall k v a.
AnnotatedMap k v a -> FingerTree (Tag k v) (Entry k v a)
annotatedMap forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> AnnotatedMap k v b -> m (AnnotatedMap k w c)
g2 (forall k v a.
FingerTree (Tag k v) (Entry k v a) -> AnnotatedMap k v a
AnnotatedMap FingerTree (Tag k v) (Entry k v b)
ft)

    rebuild :: FingerTree v a -> Maybe a -> FingerTree v a -> FingerTree v a
rebuild FingerTree v a
l Maybe a
Nothing FingerTree v a
r  = FingerTree v a
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree v a
r
    rebuild FingerTree v a
l (Just a
x) FingerTree v a
r = FingerTree v a
l forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< (a
x forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree v a
r)

    merge1 :: FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge1 FingerTree (Tag k u) (Entry k u a)
xs FingerTree (Tag k v) (Entry k v b)
ys =
      case forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Tag k u) (Entry k u a)
xs of
        ViewL (FingerTree (Tag k u)) (Entry k u a)
FT.EmptyL -> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
g2' FingerTree (Tag k v) (Entry k v b)
ys
        Entry k u a
x FT.:< FingerTree (Tag k u) (Entry k u a)
xs' ->
          let (FingerTree (Tag k v) (Entry k v b)
ys1, Maybe (Entry k v b)
ym, FingerTree (Tag k v) (Entry k v b)
ys2) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey (forall k v a. Entry k v a -> k
keyOf Entry k u a
x) FingerTree (Tag k v) (Entry k v b)
ys in
          case Maybe (Entry k v b)
ym of
            Maybe (Entry k v b)
Nothing -> forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
(><) forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
g2' FingerTree (Tag k v) (Entry k v b)
ys1 forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge2 FingerTree (Tag k u) (Entry k u a)
xs FingerTree (Tag k v) (Entry k v b)
ys2
            Just Entry k v b
y  -> forall {v} {a}.
Measured v a =>
FingerTree v a -> Maybe a -> FingerTree v a -> FingerTree v a
rebuild forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
g2' FingerTree (Tag k v) (Entry k v b)
ys1 forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))
f Entry k u a
x Entry k v b
y forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge2 FingerTree (Tag k u) (Entry k u a)
xs' FingerTree (Tag k v) (Entry k v b)
ys2

    merge2 :: FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge2 FingerTree (Tag k u) (Entry k u a)
xs FingerTree (Tag k v) (Entry k v b)
ys =
      case forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Tag k v) (Entry k v b)
ys of
        ViewL (FingerTree (Tag k v)) (Entry k v b)
FT.EmptyL -> FingerTree (Tag k u) (Entry k u a)
-> m (FingerTree (Tag k w) (Entry k w c))
g1' FingerTree (Tag k u) (Entry k u a)
xs
        Entry k v b
y FT.:< FingerTree (Tag k v) (Entry k v b)
ys' ->
          let (FingerTree (Tag k u) (Entry k u a)
xs1, Maybe (Entry k u a)
xm, FingerTree (Tag k u) (Entry k u a)
xs2) = forall k v a.
(Ord k, Semigroup v) =>
k
-> FingerTree (Tag k v) (Entry k v a)
-> (FingerTree (Tag k v) (Entry k v a), Maybe (Entry k v a),
    FingerTree (Tag k v) (Entry k v a))
splitAtKey (forall k v a. Entry k v a -> k
keyOf Entry k v b
y) FingerTree (Tag k u) (Entry k u a)
xs in
          case Maybe (Entry k u a)
xm of
            Maybe (Entry k u a)
Nothing -> forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
(><) forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> FingerTree (Tag k u) (Entry k u a)
-> m (FingerTree (Tag k w) (Entry k w c))
g1' FingerTree (Tag k u) (Entry k u a)
xs1 forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge1 FingerTree (Tag k u) (Entry k u a)
xs2 FingerTree (Tag k v) (Entry k v b)
ys
            Just Entry k u a
x  -> forall {v} {a}.
Measured v a =>
FingerTree v a -> Maybe a -> FingerTree v a -> FingerTree v a
rebuild forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> FingerTree (Tag k u) (Entry k u a)
-> m (FingerTree (Tag k w) (Entry k w c))
g1' FingerTree (Tag k u) (Entry k u a)
xs1 forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Entry k u a -> Entry k v b -> m (Maybe (Entry k w c))
f Entry k u a
x Entry k v b
y forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> FingerTree (Tag k u) (Entry k u a)
-> FingerTree (Tag k v) (Entry k v b)
-> m (FingerTree (Tag k w) (Entry k w c))
merge1 FingerTree (Tag k u) (Entry k u a)
xs2 FingerTree (Tag k v) (Entry k v b)
ys'