{-# LANGUAGE Safe #-}
{-# OPTIONS_GHC -Wno-orphans #-}

module Yaya.Containers.Pattern.Map
  ( MapF (BinF, TipF),
  )
where

import "base" Control.Category (Category ((.)))
import "base" Data.Bool (Bool (False, True), (&&))
import "base" Data.Eq (Eq ((==)))
import "base" Data.Foldable (Foldable)
import "base" Data.Function (($))
import "base" Data.Functor (Functor (fmap))
import "base" Data.Functor.Classes
  ( Eq1 (liftEq),
    Eq2 (liftEq2),
    Ord1 (liftCompare),
    Ord2 (liftCompare2),
    Show1 (liftShowsPrec),
    Show2 (liftShowsPrec2),
  )
import "base" Data.Ord (Ord (compare, (<=)), Ordering (EQ, GT, LT))
import "base" Data.Semigroup ((<>))
import "base" Data.Traversable (Traversable)
import qualified "base" Data.Tuple as Tuple
import "base" GHC.Generics (Generic, Generic1)
import "base" Text.Show (Show (showList, showsPrec), showParen, showString)
import qualified "containers" Data.Map.Internal as Map
import "yaya" Yaya.Fold
  ( Projectable (project),
    Recursive (cata),
    Steppable (embed),
  )
import "base" Prelude (Num ((+)))

data MapF k v r = TipF | BinF Map.Size k ~v r r
  deriving stock
    ( MapF k v r -> MapF k v r -> Bool
(MapF k v r -> MapF k v r -> Bool)
-> (MapF k v r -> MapF k v r -> Bool) -> Eq (MapF k v r)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v r.
(Eq k, Eq v, Eq r) =>
MapF k v r -> MapF k v r -> Bool
$c== :: forall k v r.
(Eq k, Eq v, Eq r) =>
MapF k v r -> MapF k v r -> Bool
== :: MapF k v r -> MapF k v r -> Bool
$c/= :: forall k v r.
(Eq k, Eq v, Eq r) =>
MapF k v r -> MapF k v r -> Bool
/= :: MapF k v r -> MapF k v r -> Bool
Eq,
      Eq (MapF k v r)
Eq (MapF k v r) =>
(MapF k v r -> MapF k v r -> Ordering)
-> (MapF k v r -> MapF k v r -> Bool)
-> (MapF k v r -> MapF k v r -> Bool)
-> (MapF k v r -> MapF k v r -> Bool)
-> (MapF k v r -> MapF k v r -> Bool)
-> (MapF k v r -> MapF k v r -> MapF k v r)
-> (MapF k v r -> MapF k v r -> MapF k v r)
-> Ord (MapF k v r)
MapF k v r -> MapF k v r -> Bool
MapF k v r -> MapF k v r -> Ordering
MapF k v r -> MapF k v r -> MapF k v r
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k v r. (Ord k, Ord v, Ord r) => Eq (MapF k v r)
forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Bool
forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Ordering
forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> MapF k v r
$ccompare :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Ordering
compare :: MapF k v r -> MapF k v r -> Ordering
$c< :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Bool
< :: MapF k v r -> MapF k v r -> Bool
$c<= :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Bool
<= :: MapF k v r -> MapF k v r -> Bool
$c> :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Bool
> :: MapF k v r -> MapF k v r -> Bool
$c>= :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> Bool
>= :: MapF k v r -> MapF k v r -> Bool
$cmax :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> MapF k v r
max :: MapF k v r -> MapF k v r -> MapF k v r
$cmin :: forall k v r.
(Ord k, Ord v, Ord r) =>
MapF k v r -> MapF k v r -> MapF k v r
min :: MapF k v r -> MapF k v r -> MapF k v r
Ord,
      (forall x. MapF k v r -> Rep (MapF k v r) x)
-> (forall x. Rep (MapF k v r) x -> MapF k v r)
-> Generic (MapF k v r)
forall x. Rep (MapF k v r) x -> MapF k v r
forall x. MapF k v r -> Rep (MapF k v r) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v r x. Rep (MapF k v r) x -> MapF k v r
forall k v r x. MapF k v r -> Rep (MapF k v r) x
$cfrom :: forall k v r x. MapF k v r -> Rep (MapF k v r) x
from :: forall x. MapF k v r -> Rep (MapF k v r) x
$cto :: forall k v r x. Rep (MapF k v r) x -> MapF k v r
to :: forall x. Rep (MapF k v r) x -> MapF k v r
Generic,
      Size -> MapF k v r -> ShowS
[MapF k v r] -> ShowS
MapF k v r -> String
(Size -> MapF k v r -> ShowS)
-> (MapF k v r -> String)
-> ([MapF k v r] -> ShowS)
-> Show (MapF k v r)
forall a.
(Size -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v r.
(Show k, Show v, Show r) =>
Size -> MapF k v r -> ShowS
forall k v r. (Show k, Show v, Show r) => [MapF k v r] -> ShowS
forall k v r. (Show k, Show v, Show r) => MapF k v r -> String
$cshowsPrec :: forall k v r.
(Show k, Show v, Show r) =>
Size -> MapF k v r -> ShowS
showsPrec :: Size -> MapF k v r -> ShowS
$cshow :: forall k v r. (Show k, Show v, Show r) => MapF k v r -> String
show :: MapF k v r -> String
$cshowList :: forall k v r. (Show k, Show v, Show r) => [MapF k v r] -> ShowS
showList :: [MapF k v r] -> ShowS
Show,
      (forall m. Monoid m => MapF k v m -> m)
-> (forall m a. Monoid m => (a -> m) -> MapF k v a -> m)
-> (forall m a. Monoid m => (a -> m) -> MapF k v a -> m)
-> (forall a b. (a -> b -> b) -> b -> MapF k v a -> b)
-> (forall a b. (a -> b -> b) -> b -> MapF k v a -> b)
-> (forall b a. (b -> a -> b) -> b -> MapF k v a -> b)
-> (forall b a. (b -> a -> b) -> b -> MapF k v a -> b)
-> (forall a. (a -> a -> a) -> MapF k v a -> a)
-> (forall a. (a -> a -> a) -> MapF k v a -> a)
-> (forall a. MapF k v a -> [a])
-> (forall a. MapF k v a -> Bool)
-> (forall a. MapF k v a -> Size)
-> (forall a. Eq a => a -> MapF k v a -> Bool)
-> (forall a. Ord a => MapF k v a -> a)
-> (forall a. Ord a => MapF k v a -> a)
-> (forall a. Num a => MapF k v a -> a)
-> (forall a. Num a => MapF k v a -> a)
-> Foldable (MapF k v)
forall a. Eq a => a -> MapF k v a -> Bool
forall a. Num a => MapF k v a -> a
forall a. Ord a => MapF k v a -> a
forall m. Monoid m => MapF k v m -> m
forall a. MapF k v a -> Bool
forall a. MapF k v a -> Size
forall a. MapF k v a -> [a]
forall a. (a -> a -> a) -> MapF k v a -> a
forall m a. Monoid m => (a -> m) -> MapF k v a -> m
forall b a. (b -> a -> b) -> b -> MapF k v a -> b
forall a b. (a -> b -> b) -> b -> MapF k v a -> b
forall k v a. Eq a => a -> MapF k v a -> Bool
forall k v a. Num a => MapF k v a -> a
forall k v a. Ord a => MapF k v a -> a
forall k v m. Monoid m => MapF k v m -> m
forall k v a. MapF k v a -> Bool
forall k v a. MapF k v a -> Size
forall k v a. MapF k v a -> [a]
forall k v a. (a -> a -> a) -> MapF k v a -> a
forall k v m a. Monoid m => (a -> m) -> MapF k v a -> m
forall k v b a. (b -> a -> b) -> b -> MapF k v a -> b
forall k v a b. (a -> b -> b) -> b -> MapF k v a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Size)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall k v m. Monoid m => MapF k v m -> m
fold :: forall m. Monoid m => MapF k v m -> m
$cfoldMap :: forall k v m a. Monoid m => (a -> m) -> MapF k v a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> MapF k v a -> m
$cfoldMap' :: forall k v m a. Monoid m => (a -> m) -> MapF k v a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> MapF k v a -> m
$cfoldr :: forall k v a b. (a -> b -> b) -> b -> MapF k v a -> b
foldr :: forall a b. (a -> b -> b) -> b -> MapF k v a -> b
$cfoldr' :: forall k v a b. (a -> b -> b) -> b -> MapF k v a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> MapF k v a -> b
$cfoldl :: forall k v b a. (b -> a -> b) -> b -> MapF k v a -> b
foldl :: forall b a. (b -> a -> b) -> b -> MapF k v a -> b
$cfoldl' :: forall k v b a. (b -> a -> b) -> b -> MapF k v a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> MapF k v a -> b
$cfoldr1 :: forall k v a. (a -> a -> a) -> MapF k v a -> a
foldr1 :: forall a. (a -> a -> a) -> MapF k v a -> a
$cfoldl1 :: forall k v a. (a -> a -> a) -> MapF k v a -> a
foldl1 :: forall a. (a -> a -> a) -> MapF k v a -> a
$ctoList :: forall k v a. MapF k v a -> [a]
toList :: forall a. MapF k v a -> [a]
$cnull :: forall k v a. MapF k v a -> Bool
null :: forall a. MapF k v a -> Bool
$clength :: forall k v a. MapF k v a -> Size
length :: forall a. MapF k v a -> Size
$celem :: forall k v a. Eq a => a -> MapF k v a -> Bool
elem :: forall a. Eq a => a -> MapF k v a -> Bool
$cmaximum :: forall k v a. Ord a => MapF k v a -> a
maximum :: forall a. Ord a => MapF k v a -> a
$cminimum :: forall k v a. Ord a => MapF k v a -> a
minimum :: forall a. Ord a => MapF k v a -> a
$csum :: forall k v a. Num a => MapF k v a -> a
sum :: forall a. Num a => MapF k v a -> a
$cproduct :: forall k v a. Num a => MapF k v a -> a
product :: forall a. Num a => MapF k v a -> a
Foldable,
      (forall a b. (a -> b) -> MapF k v a -> MapF k v b)
-> (forall a b. a -> MapF k v b -> MapF k v a)
-> Functor (MapF k v)
forall a b. a -> MapF k v b -> MapF k v a
forall a b. (a -> b) -> MapF k v a -> MapF k v b
forall k v a b. a -> MapF k v b -> MapF k v a
forall k v a b. (a -> b) -> MapF k v a -> MapF k v b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k v a b. (a -> b) -> MapF k v a -> MapF k v b
fmap :: forall a b. (a -> b) -> MapF k v a -> MapF k v b
$c<$ :: forall k v a b. a -> MapF k v b -> MapF k v a
<$ :: forall a b. a -> MapF k v b -> MapF k v a
Functor,
      (forall a. MapF k v a -> Rep1 (MapF k v) a)
-> (forall a. Rep1 (MapF k v) a -> MapF k v a)
-> Generic1 (MapF k v)
forall a. Rep1 (MapF k v) a -> MapF k v a
forall a. MapF k v a -> Rep1 (MapF k v) a
forall k v a. Rep1 (MapF k v) a -> MapF k v a
forall k v a. MapF k v a -> Rep1 (MapF k v) a
forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cfrom1 :: forall k v a. MapF k v a -> Rep1 (MapF k v) a
from1 :: forall a. MapF k v a -> Rep1 (MapF k v) a
$cto1 :: forall k v a. Rep1 (MapF k v) a -> MapF k v a
to1 :: forall a. Rep1 (MapF k v) a -> MapF k v a
Generic1,
      Functor (MapF k v)
Foldable (MapF k v)
(Functor (MapF k v), Foldable (MapF k v)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> MapF k v a -> f (MapF k v b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    MapF k v (f a) -> f (MapF k v a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> MapF k v a -> m (MapF k v b))
-> (forall (m :: * -> *) a.
    Monad m =>
    MapF k v (m a) -> m (MapF k v a))
-> Traversable (MapF k v)
forall k v. Functor (MapF k v)
forall k v. Foldable (MapF k v)
forall k v (m :: * -> *) a.
Monad m =>
MapF k v (m a) -> m (MapF k v a)
forall k v (f :: * -> *) a.
Applicative f =>
MapF k v (f a) -> f (MapF k v a)
forall k v (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MapF k v a -> m (MapF k v b)
forall k v (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MapF k v a -> f (MapF k v b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => MapF k v (m a) -> m (MapF k v a)
forall (f :: * -> *) a.
Applicative f =>
MapF k v (f a) -> f (MapF k v a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MapF k v a -> m (MapF k v b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MapF k v a -> f (MapF k v b)
$ctraverse :: forall k v (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MapF k v a -> f (MapF k v b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MapF k v a -> f (MapF k v b)
$csequenceA :: forall k v (f :: * -> *) a.
Applicative f =>
MapF k v (f a) -> f (MapF k v a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
MapF k v (f a) -> f (MapF k v a)
$cmapM :: forall k v (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MapF k v a -> m (MapF k v b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MapF k v a -> m (MapF k v b)
$csequence :: forall k v (m :: * -> *) a.
Monad m =>
MapF k v (m a) -> m (MapF k v a)
sequence :: forall (m :: * -> *) a. Monad m => MapF k v (m a) -> m (MapF k v a)
Traversable
    )

instance Projectable (->) (Map.Map k v) (MapF k v) where
  project :: Coalgebra (->) (MapF k v) (Map k v)
project Map k v
Map.Tip = MapF k v (Map k v)
forall k v r. MapF k v r
TipF
  project (Map.Bin Size
size k
k v
v Map k v
l Map k v
r) = Size -> k -> v -> Map k v -> Coalgebra (->) (MapF k v) (Map k v)
forall k v r. Size -> k -> v -> r -> r -> MapF k v r
BinF Size
size k
k v
v Map k v
l Map k v
r

instance Recursive (->) (Map.Map k v) (MapF k v) where
  cata :: forall a. Algebra (->) (MapF k v) a -> Map k v -> a
cata Algebra (->) (MapF k v) a
φ = Algebra (->) (MapF k v) a
φ Algebra (->) (MapF k v) a
-> (Map k v -> MapF k v a) -> Map k v -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Map k v -> a) -> MapF k v (Map k v) -> MapF k v a
forall a b. (a -> b) -> MapF k v a -> MapF k v b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Algebra (->) (MapF k v) a -> Map k v -> a
forall a. Algebra (->) (MapF k v) a -> Map k v -> a
forall {k} {k1} (c :: k -> k1 -> *) (t :: k) (f :: k1 -> k)
       (a :: k1).
Recursive c t f =>
Algebra c f a -> c t a
cata Algebra (->) (MapF k v) a
φ) (MapF k v (Map k v) -> MapF k v a)
-> (Map k v -> MapF k v (Map k v)) -> Map k v -> MapF k v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Map k v -> MapF k v (Map k v)
forall {k} {k1} (c :: k -> k1 -> *) (t :: k) (f :: k -> k1).
Projectable c t f =>
Coalgebra c f t
project

instance Steppable (->) (Map.Map k v) (MapF k v) where
  embed :: Algebra (->) (MapF k v) (Map k v)
embed MapF k v (Map k v)
TipF = Map k v
forall k a. Map k a
Map.Tip
  embed (BinF Size
size k
k v
v Map k v
l Map k v
r) = Size -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Map.Bin Size
size k
k v
v Map k v
l Map k v
r

instance (Eq k, Eq v) => Eq1 (MapF k v) where
  -- TODO: Remove this once base-4.18 is the oldest supported verson, as it’s
  --       the default impl.
  liftEq :: forall a b. (a -> b -> Bool) -> MapF k v a -> MapF k v b -> Bool
liftEq = (v -> v -> Bool)
-> (a -> b -> Bool) -> MapF k v a -> MapF k v b -> Bool
forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> MapF k a c -> MapF k b d -> Bool
forall (f :: * -> * -> *) a b c d.
Eq2 f =>
(a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool
liftEq2 v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)

instance (Eq k) => Eq2 (MapF k) where
  liftEq2 :: forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> MapF k a c -> MapF k b d -> Bool
liftEq2 a -> b -> Bool
f c -> d -> Bool
g = ((MapF k a c, MapF k b d) -> Bool)
-> MapF k a c -> MapF k b d -> Bool
forall a b c. ((a, b) -> c) -> a -> b -> c
Tuple.curry (((MapF k a c, MapF k b d) -> Bool)
 -> MapF k a c -> MapF k b d -> Bool)
-> ((MapF k a c, MapF k b d) -> Bool)
-> MapF k a c
-> MapF k b d
-> Bool
forall a b. (a -> b) -> a -> b
$ \case
    (MapF k a c
TipF, MapF k b d
TipF) -> Bool
True
    (BinF Size
size k
k a
v c
l c
r, BinF Size
size' k
k' b
v' d
l' d
r') ->
      Size
size Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
size' Bool -> Bool -> Bool
&& k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k' Bool -> Bool -> Bool
&& a -> b -> Bool
f a
v b
v' Bool -> Bool -> Bool
&& c -> d -> Bool
g c
l d
l' Bool -> Bool -> Bool
&& c -> d -> Bool
g c
r d
r'
    (MapF k a c
_, MapF k b d
_) -> Bool
False

instance (Ord k, Ord v) => Ord1 (MapF k v) where
  -- TODO: Remove this once base-4.18 is the oldest supported verson, as it’s
  --       the default impl.
  liftCompare :: forall a b.
(a -> b -> Ordering) -> MapF k v a -> MapF k v b -> Ordering
liftCompare = (v -> v -> Ordering)
-> (a -> b -> Ordering) -> MapF k v a -> MapF k v b -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> MapF k a c -> MapF k b d -> Ordering
forall (f :: * -> * -> *) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 v -> v -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

instance (Ord k) => Ord2 (MapF k) where
  liftCompare2 :: forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> MapF k a c -> MapF k b d -> Ordering
liftCompare2 a -> b -> Ordering
f c -> d -> Ordering
g = ((MapF k a c, MapF k b d) -> Ordering)
-> MapF k a c -> MapF k b d -> Ordering
forall a b c. ((a, b) -> c) -> a -> b -> c
Tuple.curry (((MapF k a c, MapF k b d) -> Ordering)
 -> MapF k a c -> MapF k b d -> Ordering)
-> ((MapF k a c, MapF k b d) -> Ordering)
-> MapF k a c
-> MapF k b d
-> Ordering
forall a b. (a -> b) -> a -> b
$ \case
    (MapF k a c
TipF, MapF k b d
TipF) -> Ordering
EQ
    (MapF k a c
TipF, BinF {}) -> Ordering
LT
    (BinF {}, MapF k b d
TipF) -> Ordering
GT
    (BinF Size
size k
k a
v c
l c
r, BinF Size
size' k
k' b
v' d
l' d
r') ->
      Size -> Size -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Size
size Size
size' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> a -> b -> Ordering
f a
v b
v' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> c -> d -> Ordering
g c
l d
l' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> c -> d -> Ordering
g c
r d
r'

instance (Show k, Show v) => Show1 (MapF k v) where
  -- TODO: Remove this once base-4.18 is the oldest supported verson, as it’s
  --       the default impl.
  liftShowsPrec :: forall a.
(Size -> a -> ShowS)
-> ([a] -> ShowS) -> Size -> MapF k v a -> ShowS
liftShowsPrec = (Size -> v -> ShowS)
-> ([v] -> ShowS)
-> (Size -> a -> ShowS)
-> ([a] -> ShowS)
-> Size
-> MapF k v a
-> ShowS
forall a b.
(Size -> a -> ShowS)
-> ([a] -> ShowS)
-> (Size -> b -> ShowS)
-> ([b] -> ShowS)
-> Size
-> MapF k a b
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Size -> a -> ShowS)
-> ([a] -> ShowS)
-> (Size -> b -> ShowS)
-> ([b] -> ShowS)
-> Size
-> f a b
-> ShowS
liftShowsPrec2 Size -> v -> ShowS
forall a. Show a => Size -> a -> ShowS
showsPrec [v] -> ShowS
forall a. Show a => [a] -> ShowS
showList

instance (Show k) => Show2 (MapF k) where
  liftShowsPrec2 :: forall a b.
(Size -> a -> ShowS)
-> ([a] -> ShowS)
-> (Size -> b -> ShowS)
-> ([b] -> ShowS)
-> Size
-> MapF k a b
-> ShowS
liftShowsPrec2 Size -> a -> ShowS
showsPrecV [a] -> ShowS
_showListV Size -> b -> ShowS
showsPrecR [b] -> ShowS
_showListR Size
prec =
    let appPrec :: a
appPrec = a
10
        nextPrec :: a
nextPrec = a
forall {a}. Num a => a
appPrec a -> a -> a
forall a. Num a => a -> a -> a
+ a
1
     in \case
          MapF k a b
TipF -> String -> ShowS
showString String
"TipF"
          BinF Size
size k
k a
v b
l b
r ->
            Bool -> ShowS -> ShowS
showParen (Size
forall {a}. Num a => a
nextPrec Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
<= Size
prec) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
              String -> ShowS
showString String
"BinF "
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Size -> Size -> ShowS
forall a. Show a => Size -> a -> ShowS
showsPrec Size
forall {a}. Num a => a
nextPrec Size
size
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. String -> ShowS
showString String
" "
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Size -> k -> ShowS
forall a. Show a => Size -> a -> ShowS
showsPrec Size
forall {a}. Num a => a
nextPrec k
k
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. String -> ShowS
showString String
" "
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Size -> a -> ShowS
showsPrecV Size
forall {a}. Num a => a
nextPrec a
v
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. String -> ShowS
showString String
" "
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Size -> b -> ShowS
showsPrecR Size
forall {a}. Num a => a
nextPrec b
l
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. String -> ShowS
showString String
" "
                ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Size -> b -> ShowS
showsPrecR Size
forall {a}. Num a => a
nextPrec b
r