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

-- | Cartesian monoidal categories ('Cartesian': tensor = product, with 'CopyDiscard' as
-- superclass by Fox's theorem), cartesian closed ones ('CCC') and bicartesian closed ones
-- ('BiCCC', which implies 'Distributive'): the meeting point of the monoidal and the product
-- worlds, which never import each other. Lives above
-- "Proarrow.Category.Monoidal.CopyDiscard" rather than with the products, because the superclass
-- points that way.
module Proarrow.Category.Monoidal.Cartesian where

import Data.Kind (Type)
import Prelude (($), type (~))
import Prelude qualified as P

import Proarrow.Category.Instance.Free (Elems, FREE, Free (..), HasStructure (..), Lower, withLowerOb)
import Proarrow.Category.Monoidal (Monoidal (..), MonoidalProfunctor (..), SymMonoidal, UnitF, type (**!))
import Proarrow.Category.Monoidal.Closed (Closed (..), uncurry)
import Proarrow.Category.Monoidal.CopyDiscard (CopyDiscard)
import Proarrow.Category.Monoidal.Distributive (Distributive (..), Traversable (..))
import Proarrow.Colimit.BinaryCoproduct (HasBinaryCoproducts (..), type (||))
import Proarrow.Core (CAT, CategoryOf (..), Profunctor (..), Promonad (..), UN, lmap, type (+->))
import Proarrow.Limit.BinaryProduct
  ( HasBinaryProducts (..)
  , HasProducts
  , PROD (..)
  , Prod (..)
  , diag
  , swapProd
  , type (*!)
  )
import Proarrow.Limit.Terminal (HasTerminalObject (..), Semicartesian, TermF)
import Proarrow.Monoid (CocommutativeComonoid, Comonoid (..))
import Proarrow.Profunctor.Instance.Composition ((:.:) (..))
import Proarrow.Profunctor.Instance.Product ((:*:) (..))
import Proarrow.Profunctor.Representable (RepCostar (..), Representable (..), withObRep)

class (a ** b ~ a && b) => TensorIsProduct a b
instance (a ** b ~ a && b) => TensorIsProduct a b

-- | A cartesian monoidal category: the tensor is the product and the unit the terminal object.
-- By Fox's theorem this is the same as a 'CopyDiscard' category whose 'copy' and 'discard' are
-- natural, so 'CopyDiscard' is a superclass. Every cartesian category supplies its diagonals as
-- comonoids, and anything asking only for copying and discarding (prisms, for instance) accepts
-- a cartesian category directly. The law relating the two is @copy = id &&& id@ and
-- @discard = terminate@.
class
  (HasProducts k, SymMonoidal k, Semicartesian k, CopyDiscard k, forall (a :: k) (b :: k). TensorIsProduct a b) =>
  Cartesian k

instance
  (HasProducts k, SymMonoidal k, Semicartesian k, CopyDiscard k, forall (a :: k) (b :: k). TensorIsProduct a b)
  => Cartesian k

-- | In a category with products every object is a comonoid via the diagonal and the terminal
-- map. With this comonoid structure 'PROD' is 'CopyDiscard' and 'Cartesian'.
instance (HasProducts k, Ob a) => Comonoid (PR (a :: k)) where
  counit :: PR a ~> Unit
counit = (a ~> TerminalObject) -> Prod (~>) (PR a) (PR TerminalObject)
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod a ~> TerminalObject
forall (a :: k). Ob a => a ~> TerminalObject
forall k (a :: k).
(HasTerminalObject k, Ob a) =>
a ~> TerminalObject
terminate
  comult :: PR a ~> (PR a ** PR a)
comult = (a ~> (a && a)) -> Prod (~>) (PR a) (PR (a && a))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod a ~> (a && a)
forall {k} (a :: k). (HasBinaryProducts k, Ob a) => a ~> (a && a)
diag

instance (HasProducts k, Ob a) => CocommutativeComonoid (PR (a :: k))

-- | A category with products, viewed through 'PROD' as a monoidal category, is cartesian.
instance (HasProducts k) => CopyDiscard (PROD k)

instance Closed (PROD Type) where
  -- The wrapper must also stay opaque until the helper's inlining phase.
  {-# INLINE [0] curry #-}
  type a ~~> b = PR (UN PR a ~~> UN PR b)
  withObExp :: forall (a :: PROD Type) (b :: PROD Type) r.
(Ob a, Ob b) =>
(Ob (a ~~> b) => r) -> r
withObExp @(PR a) @(PR b) Ob (a ~~> b) => r
r = forall k (a :: k) (b :: k) r.
(Closed k, Ob a, Ob b) =>
(Ob (a ~~> b) => r) -> r
withObExp @Type @a @b r
Ob (UN PR a ~~> UN PR b) => r
Ob (a ~~> b) => r
r
  curry :: forall (a :: PROD Type) (b :: PROD Type) (c :: PROD Type).
(Ob a, Ob b) =>
((a ** b) ~> c) -> a ~> (b ~~> c)
curry (Prod a1 -> b1
f) = (UN PR a -> (UN PR b -> b1))
-> Prod (->) (PR (UN PR a)) (PR (UN PR b -> b1))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (((UN PR a && UN PR b) ~> b1) -> UN PR a ~> (UN PR b ~~> b1)
forall {k} (a :: k) (b :: k) (c :: k).
(CCC k, TensorIsProduct a b, Ob a, Ob b) =>
((a && b) ~> c) -> a ~> (b ~~> c)
curryProd (UN PR a && UN PR b) ~> b1
a1 -> b1
f)
  apply :: forall (a :: PROD Type) (b :: PROD Type).
(Ob a, Ob b) =>
((a ~~> b) ** a) ~> b
apply @(PR a) @(PR b) = ((UN PR a -> UN PR b, UN PR a) -> UN PR b)
-> Prod (->) (PR (UN PR a -> UN PR b, UN PR a)) (PR (UN PR b))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (forall {k} (a :: k) (b :: k).
(CCC k, TensorIsProduct (a ~~> b) a, Ob a, Ob b) =>
((a ~~> b) && a) ~> b
forall a b.
(CCC Type, TensorIsProduct (a ~~> b) a, Ob a, Ob b) =>
((a ~~> b) && a) ~> b
applyProd @a @b)

-- | In a cartesian category the tensor /is/ the product ('TensorIsProduct'), but GHC only applies
-- that equation at the top of a type, never under another type family such as @('||')@, and
-- using the quantified form of it directly sends the solver in circles. These two identities take
-- the equation as an ordinary given (discharged at the call site from the quantified superclass
-- of 'Cartesian'), so it can be applied where a product-typed leg meets tensor-typed plumbing.
tensorToProduct :: forall {k} (a :: k) b. (HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) => (a ** b) ~> (a && b)
tensorToProduct :: forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) =>
(a ** b) ~> (a && b)
tensorToProduct = forall k (a :: k) (b :: k) r.
(HasBinaryProducts k, Ob a, Ob b) =>
(Ob (a && b) => r) -> r
withObProd @k @a @b (a && b) ~> (a && b)
Ob (a && b) => (a && b) ~> (a && b)
forall (a :: k). Ob a => a ~> a
forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id

productToTensor :: forall {k} (a :: k) b. (HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) => (a && b) ~> (a ** b)
productToTensor :: forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) =>
(a && b) ~> (a ** b)
productToTensor = forall k (a :: k) (b :: k) r.
(HasBinaryProducts k, Ob a, Ob b) =>
(Ob (a && b) => r) -> r
withObProd @k @a @b (a && b) ~> (a && b)
Ob (a && b) => (a && b) ~> (a && b)
forall (a :: k). Ob a => a ~> a
forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id

-- | Every functor between cartesian categories is oplax monoidal, @f (a && b) ~> f a && f b@ by the
-- projections and @f Unit ~> Unit@ by terminality. On the 'RepCostar' of its representable profunctor
-- this is 'Proarrow.Category.Monoidal.OplaxMonoidal'.
instance (Representable p, Cartesian j, Cartesian k) => MonoidalProfunctor (RepCostar (p :: j +-> k)) where
  one :: RepCostar p Unit Unit
one = forall {j} {k} (p :: j +-> k) (a :: j) r.
(Representable p, Ob a) =>
(Ob (p % a) => r) -> r
forall (p :: j +-> k) (a :: j) r.
(Representable p, Ob a) =>
(Ob (p % a) => r) -> r
withObRep @p @Unit (((p % TerminalObject) ~> TerminalObject)
-> RepCostar p TerminalObject TerminalObject
forall {k} {j} (a :: k) (p :: k +-> j) (b :: j).
Ob a =>
((p % a) ~> b) -> RepCostar p a b
RepCostar (p % TerminalObject) ~> TerminalObject
forall (a :: k). Ob a => a ~> TerminalObject
forall k (a :: k).
(HasTerminalObject k, Ob a) =>
a ~> TerminalObject
terminate)
  RepCostar @a (p % x1) ~> x2
f ** :: forall (x1 :: j) (x2 :: k) (y1 :: j) (y2 :: k).
RepCostar p x1 x2
-> RepCostar p y1 y2 -> RepCostar p (x1 ** y1) (x2 ** y2)
** RepCostar @b (p % y1) ~> y2
g = forall k (a :: k) (b :: k) r.
(Monoidal k, Ob a, Ob b) =>
(Ob (a ** b) => r) -> r
withOb2 @j @a @b (((p % (x1 ** y1)) ~> (x2 ** y2))
-> RepCostar p (x1 ** y1) (x2 ** y2)
forall {k} {j} (a :: k) (p :: k +-> j) (b :: j).
Ob a =>
((p % a) ~> b) -> RepCostar p a b
RepCostar (forall {j} {k} (p :: j +-> k) (a :: j) (b :: j) (a' :: k)
       (b' :: k).
(Representable p, Cartesian k, Cartesian j, TensorIsProduct a b,
 TensorIsProduct a' b', Ob a, Ob b) =>
((p % a) ~> a') -> ((p % b) ~> b') -> (p % (a ** b)) ~> (a' ** b')
forall (p :: j +-> k) (a :: j) (b :: j) (a' :: k) (b' :: k).
(Representable p, Cartesian k, Cartesian j, TensorIsProduct a b,
 TensorIsProduct a' b', Ob a, Ob b) =>
((p % a) ~> a') -> ((p % b) ~> b') -> (p % (a ** b)) ~> (a' ** b')
unparRepCartesian @p @a @b (p % x1) ~> x2
f (p % y1) ~> y2
g))

unparRepCartesian
  :: forall {j} {k} p (a :: j) b a' b'
   . ( Representable (p :: j +-> k)
     , Cartesian k
     , Cartesian j
     , TensorIsProduct a b
     , TensorIsProduct a' b'
     , Ob a
     , Ob b
     )
  => (p % a ~> a') -> (p % b ~> b') -> p % (a ** b) ~> (a' ** b')
unparRepCartesian :: forall {j} {k} (p :: j +-> k) (a :: j) (b :: j) (a' :: k)
       (b' :: k).
(Representable p, Cartesian k, Cartesian j, TensorIsProduct a b,
 TensorIsProduct a' b', Ob a, Ob b) =>
((p % a) ~> a') -> ((p % b) ~> b') -> (p % (a ** b)) ~> (a' ** b')
unparRepCartesian (p % a) ~> a'
f (p % b) ~> b'
g = (p % a) ~> a'
f ((p % a) ~> a')
-> ((p % (a && b)) ~> (p % a)) -> (p % (a && b)) ~> a'
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. forall {j} {k} (p :: j +-> k) (a :: j) (b :: j).
Representable p =>
(a ~> b) -> (p % a) ~> (p % b)
forall (p :: j +-> k) (a :: j) (b :: j).
Representable p =>
(a ~> b) -> (p % a) ~> (p % b)
repMap @p (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> a
fst @j @a @b) ((p % (a && b)) ~> a')
-> ((p % (a && b)) ~> b') -> (p % (a && b)) ~> (a' && b')
forall (a :: k) (x :: k) (y :: k).
(a ~> x) -> (a ~> y) -> a ~> (x && y)
forall k (a :: k) (x :: k) (y :: k).
HasBinaryProducts k =>
(a ~> x) -> (a ~> y) -> a ~> (x && y)
&&& (p % b) ~> b'
g ((p % b) ~> b')
-> ((p % (a && b)) ~> (p % b)) -> (p % (a && b)) ~> b'
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. forall {j} {k} (p :: j +-> k) (a :: j) (b :: j).
Representable p =>
(a ~> b) -> (p % a) ~> (p % b)
forall (p :: j +-> k) (a :: j) (b :: j).
Representable p =>
(a ~> b) -> (p % a) ~> (p % b)
repMap @p (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> b
snd @j @a @b)

class (Cartesian k, Closed k) => CCC k
instance (Cartesian k, Closed k) => CCC k

-- | Currying with the product, obtained from 'curry' using the cartesian tensor/product equality.
-- It satisfies the currying bijection in the laws of 'Closed'.
-- Keep @INLINE [0]@ on a delegating instance method too, to preserve delayed inlining.
curryProd :: forall {k} (a :: k) b c. (CCC k, TensorIsProduct a b, Ob a, Ob b) => (a && b) ~> c -> a ~> (b ~~> c)
curryProd :: forall {k} (a :: k) (b :: k) (c :: k).
(CCC k, TensorIsProduct a b, Ob a, Ob b) =>
((a && b) ~> c) -> a ~> (b ~~> c)
curryProd = forall k (a :: k) (b :: k) (c :: k).
(Closed k, Ob a, Ob b) =>
((a ** b) ~> c) -> a ~> (b ~~> c)
curry @k @a @b
-- Delay exposing the underlying curry to limit dictionary expansion in nested SMC terms.
{-# INLINE [0] curryProd #-}

-- | Evaluation with the product, obtained from 'apply' using the cartesian tensor/product equality.
-- Together with 'curryProd' it satisfies the currying bijection in the laws of 'Closed'.
applyProd :: forall {k} (a :: k) b. (CCC k, TensorIsProduct (a ~~> b) a, Ob a, Ob b) => ((a ~~> b) && a) ~> b
applyProd :: forall {k} (a :: k) (b :: k).
(CCC k, TensorIsProduct (a ~~> b) a, Ob a, Ob b) =>
((a ~~> b) && a) ~> b
applyProd = forall k (a :: k) (b :: k).
(Closed k, Ob a, Ob b) =>
((a ~~> b) ** a) ~> b
apply @k @a @b
{-# INLINE applyProd #-}

type Bicartesian k = (Cartesian k, Distributive k)

-- | Bicartesian closed: cartesian closed with coproducts. Every such category is distributive
-- (@a &&@ is a left adjoint, so it preserves coproducts), and the class says so, so that
-- 'Distributive' never has to be asked for separately.
class (CCC k, Distributive k) => BiCCC k

instance (CCC k, Distributive k) => BiCCC k

-- | Distributivity of the /product/ over coproducts, derived from closedness: in any BiCCC the
-- functor @a &&@ is a left adjoint and so preserves coproducts.
distLProd :: forall {k} (a :: k) (b :: k) (c :: k). (BiCCC k, Ob a, Ob b, Ob c) => (a && (b || c)) ~> (a && b || a && c)
distLProd :: forall {k} (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
(a && (b || c)) ~> ((a && b) || (a && c))
distLProd = (forall (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
swapProd @b @a ((b && a) ~> (a && b))
-> ((c && a) ~> (a && c))
-> ((b && a) || (c && a)) ~> ((a && b) || (a && c))
forall (a :: k) (b :: k) (x :: k) (y :: k).
(a ~> x) -> (b ~> y) -> (a || b) ~> (x || y)
forall k (a :: k) (b :: k) (x :: k) (y :: k).
HasBinaryCoproducts k =>
(a ~> x) -> (b ~> y) -> (a || b) ~> (x || y)
+++ forall (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
swapProd @c @a) (((b && a) || (c && a)) ~> ((a && b) || (a && c)))
-> ((a && (b || c)) ~> ((b && a) || (c && a)))
-> (a && (b || c)) ~> ((a && b) || (a && c))
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. forall (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
((a || b) && c) ~> ((a && c) || (b && c))
forall {k} (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
((a || b) && c) ~> ((a && c) || (b && c))
distRProd @b @c @a (((b || c) && a) ~> ((b && a) || (c && a)))
-> ((a && (b || c)) ~> ((b || c) && a))
-> (a && (b || c)) ~> ((b && a) || (c && a))
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. forall k (a :: k) (b :: k) r.
(HasBinaryCoproducts k, Ob a, Ob b) =>
(Ob (a || b) => r) -> r
withObCoprod @k @b @c (forall (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> (b && a)
swapProd @a @(b || c))

distRProd :: forall {k} (a :: k) (b :: k) (c :: k). (BiCCC k, Ob a, Ob b, Ob c) => ((a || b) && c) ~> (a && c || b && c)
distRProd :: forall {k} (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
((a || b) && c) ~> ((a && c) || (b && c))
distRProd =
  forall k (a :: k) (b :: k) r.
(HasBinaryProducts k, Ob a, Ob b) =>
(Ob (a && b) => r) -> r
withObProd @k @a @c ((Ob (a && c) => ((a || b) && c) ~> ((a && c) || (b && c)))
 -> ((a || b) && c) ~> ((a && c) || (b && c)))
-> (Ob (a && c) => ((a || b) && c) ~> ((a && c) || (b && c)))
-> ((a || b) && c) ~> ((a && c) || (b && c))
forall a b. (a -> b) -> a -> b
$
    forall k (a :: k) (b :: k) r.
(HasBinaryProducts k, Ob a, Ob b) =>
(Ob (a && b) => r) -> r
withObProd @k @b @c ((Ob (b && c) => ((a || b) && c) ~> ((a && c) || (b && c)))
 -> ((a || b) && c) ~> ((a && c) || (b && c)))
-> (Ob (b && c) => ((a || b) && c) ~> ((a && c) || (b && c)))
-> ((a || b) && c) ~> ((a && c) || (b && c))
forall a b. (a -> b) -> a -> b
$
      forall k (a :: k) (b :: k) r.
(HasBinaryCoproducts k, Ob a, Ob b) =>
(Ob (a || b) => r) -> r
withObCoprod @k @(a && c) @(b && c) ((Ob ((a && c) || (b && c)) =>
  ((a || b) && c) ~> ((a && c) || (b && c)))
 -> ((a || b) && c) ~> ((a && c) || (b && c)))
-> (Ob ((a && c) || (b && c)) =>
    ((a || b) && c) ~> ((a && c) || (b && c)))
-> ((a || b) && c) ~> ((a && c) || (b && c))
forall a b. (a -> b) -> a -> b
$
        forall (b :: k) (c :: k) (a :: k).
(Closed k, Ob b, Ob c) =>
(a ~> (b ~~> c)) -> (a ** b) ~> c
forall {k} (b :: k) (c :: k) (a :: k).
(Closed k, Ob b, Ob c) =>
(a ~> (b ~~> c)) -> (a ** b) ~> c
uncurry @c (forall k (a :: k) (b :: k) (c :: k).
(Closed k, Ob a, Ob b) =>
((a ** b) ~> c) -> a ~> (b ~~> c)
curry @k @a @c (forall k (a :: k) (b :: k).
(HasBinaryCoproducts k, Ob a, Ob b) =>
a ~> (a || b)
lft @k @(a && c) @(b && c)) (a ~> (c ~~> ((a && c) || (b && c))))
-> (b ~> (c ~~> ((a && c) || (b && c))))
-> (a || b) ~> (c ~~> ((a && c) || (b && c)))
forall (x :: k) (a :: k) (y :: k).
(x ~> a) -> (y ~> a) -> (x || y) ~> a
forall k (x :: k) (a :: k) (y :: k).
HasBinaryCoproducts k =>
(x ~> a) -> (y ~> a) -> (x || y) ~> a
||| forall k (a :: k) (b :: k) (c :: k).
(Closed k, Ob a, Ob b) =>
((a ** b) ~> c) -> a ~> (b ~~> c)
curry @k @b @c (forall k (a :: k) (b :: k).
(HasBinaryCoproducts k, Ob a, Ob b) =>
b ~> (a || b)
rgt @k @(a && c) @(b && c)))

instance (BiCCC k) => Distributive (PROD k) where
  distL :: forall (a :: PROD k) (b :: PROD k) (c :: PROD k).
(Ob a, Ob b, Ob c) =>
(a ** (b || c)) ~> ((a ** b) || (a ** c))
distL @(PR a) @(PR b) @(PR c) = ((UN PR a && (UN PR b || UN PR c))
 ~> ((UN PR a && UN PR b) || (UN PR a && UN PR c)))
-> Prod
     (~>)
     (PR (UN PR a && (UN PR b || UN PR c)))
     (PR ((UN PR a && UN PR b) || (UN PR a && UN PR c)))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (forall (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
(a && (b || c)) ~> ((a && b) || (a && c))
forall {k} (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
(a && (b || c)) ~> ((a && b) || (a && c))
distLProd @a @b @c)
  distR :: forall (a :: PROD k) (b :: PROD k) (c :: PROD k).
(Ob a, Ob b, Ob c) =>
((a || b) ** c) ~> ((a ** c) || (b ** c))
distR @(PR a) @(PR b) @(PR c) = (((UN PR a || UN PR b) && UN PR c)
 ~> ((UN PR a && UN PR c) || (UN PR b && UN PR c)))
-> Prod
     (~>)
     (PR ((UN PR a || UN PR b) && UN PR c))
     (PR ((UN PR a && UN PR c) || (UN PR b && UN PR c)))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (forall (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
((a || b) && c) ~> ((a && c) || (b && c))
forall {k} (a :: k) (b :: k) (c :: k).
(BiCCC k, Ob a, Ob b, Ob c) =>
((a || b) && c) ~> ((a && c) || (b && c))
distRProd @a @b @c)
  absorbL :: forall (a :: PROD k). Ob a => (a ** InitialObject) ~> InitialObject
absorbL @(PR a) = ((UN PR a && InitialObject) ~> InitialObject)
-> Prod (~>) (PR (UN PR a && InitialObject)) (PR InitialObject)
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> b
snd @k @a)
  absorbR :: forall (a :: PROD k). Ob a => (InitialObject ** a) ~> InitialObject
absorbR @(PR a) = ((InitialObject && UN PR a) ~> InitialObject)
-> Prod (~>) (PR (InitialObject && UN PR a)) (PR InitialObject)
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> a
fst @k @_ @a)

instance (Cartesian k, Traversable p, Traversable q) => Traversable ((p :: k +-> k) :*: q) where
  traverse :: forall (p :: k +-> k).
StrongDistributiveProfunctor p =>
((p :*: q) :.: p) :~> (p :.: (p :*: q))
traverse ((p a b
p :*: q a b
q) :.: p b b
r) = case ((:.:) p p a b -> (:.:) p p a b
(p :.: p) :~> (p :.: p)
forall {k} (t :: k +-> k) (p :: k +-> k).
(Traversable t, StrongDistributiveProfunctor p) =>
(t :.: p) :~> (p :.: t)
forall (p :: k +-> k).
StrongDistributiveProfunctor p =>
(p :.: p) :~> (p :.: p)
traverse (p a b
p p a b -> p b b -> (:.:) p p a b
forall {j} {k} {i} (b :: j) (a :: k) (c :: i) (p :: j +-> k)
       (q :: i +-> j).
p a b -> q b c -> (:.:) p q a c
:.: p b b
r), (:.:) q p a b -> (:.:) p q a b
(q :.: p) :~> (p :.: q)
forall {k} (t :: k +-> k) (p :: k +-> k).
(Traversable t, StrongDistributiveProfunctor p) =>
(t :.: p) :~> (p :.: t)
forall (p :: k +-> k).
StrongDistributiveProfunctor p =>
(q :.: p) :~> (p :.: q)
traverse (q a b
q q a b -> p b b -> (:.:) q p a b
forall {j} {k} {i} (b :: j) (a :: k) (c :: i) (p :: j +-> k)
       (q :: i +-> j).
p a b -> q b c -> (:.:) p q a c
:.: p b b
r)) of
    ((:.:) @a p a b
r' p b b
p', (:.:) @b p a b
r'' q b b
q') -> (a ~> (a && a)) -> p (a && a) (b ** b) -> p a (b ** b)
forall (c :: k) (a :: k) (b :: k). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> (a && a)
forall {k} (a :: k). (HasBinaryProducts k, Ob a) => a ~> (a && a)
diag (p a b
r' p a b -> p a b -> p (a ** a) (b ** b)
forall (x1 :: k) (x2 :: k) (y1 :: k) (y2 :: k).
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
forall {j} {k} (p :: j +-> k) (x1 :: k) (x2 :: j) (y1 :: k)
       (y2 :: j).
MonoidalProfunctor p =>
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
** p a b
r'') p a (b ** b) -> (:*:) p q (b ** b) b -> (:.:) p (p :*: q) a b
forall {j} {k} {i} (b :: j) (a :: k) (c :: i) (p :: j +-> k)
       (q :: i +-> j).
p a b -> q b c -> (:.:) p q a c
:.: (((b ** b) ~> b) -> p b b -> p (b ** b) b
forall (c :: k) (a :: k) (b :: k). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> a
fst @k @a @b) p b b
p' p (b ** b) b -> q (b ** b) b -> (:*:) p q (b ** b) b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) (q :: j +-> k).
p a b -> q a b -> (:*:) p q a b
:*: ((b ** b) ~> b) -> q b b -> q (b ** b) b
forall (c :: k) (a :: k) (b :: k). (c ~> a) -> q a b -> q c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap (forall k (a :: k) (b :: k).
(HasBinaryProducts k, Ob a, Ob b) =>
(a && b) ~> b
snd @k @a @b) q b b
q') ((Ob a, Ob b) => (:.:) p (p :*: q) a b)
-> p a b -> (:.:) p (p :*: q) a b
forall (a :: k) (b :: k) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a b
p ((Ob b, Ob b) => (:.:) p (p :*: q) a b)
-> p b b -> (:.:) p (p :*: q) a b
forall (a :: k) (b :: k) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p b b
p' ((Ob b, Ob b) => (:.:) p (p :*: q) a b)
-> q b b -> (:.:) p (p :*: q) a b
forall (a :: k) (b :: k) r. ((Ob a, Ob b) => r) -> q a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ q b b
q'

ap
  :: forall {j} {k} y a x p
   . (Closed j, Cartesian k, MonoidalProfunctor (p :: j +-> k), Ob y)
  => p a (x ~~> y)
  -> p a x
  -> p a y
ap :: forall {j} {k} (y :: j) (a :: k) (x :: j) (p :: j +-> k).
(Closed j, Cartesian k, MonoidalProfunctor p, Ob y) =>
p a (x ~~> y) -> p a x -> p a y
ap p a (x ~~> y)
pf p a x
px = (a ~> (a && a))
-> (((x ~~> y) ** x) ~> y) -> p (a && a) ((x ~~> y) ** x) -> p a y
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> p a b -> p c d
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap a ~> (a && a)
forall {k} (a :: k). (HasBinaryProducts k, Ob a) => a ~> (a && a)
diag (forall k (a :: k) (b :: k).
(Closed k, Ob a, Ob b) =>
((a ~~> b) ** a) ~> b
apply @j @x @y) (p a (x ~~> y)
pf p a (x ~~> y) -> p a x -> p (a ** a) ((x ~~> y) ** x)
forall (x1 :: k) (x2 :: j) (y1 :: k) (y2 :: j).
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
forall {j} {k} (p :: j +-> k) (x1 :: k) (x2 :: j) (y1 :: k)
       (y2 :: j).
MonoidalProfunctor p =>
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
** p a x
px) ((Ob a, Ob x) => p a y) -> p a x -> p a y
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a x
px

-- | The free-category structure for 'Cartesian'. The free category cannot satisfy the /type
-- equality/ @tensor = product@ ('TensorIsProduct' fails on it, see "Proarrow.Category.Instance.Free"),
-- but it can carry the corresponding isomorphisms as formal arrows, interpreted to the identity in
-- any cartesian target ('productToTensor' and friends). So a free category can serve as syntax
-- for cartesian (closed) categories without collapsing its object grammar.
instance
  ('[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] `Elems` cs)
  => HasStructure cs (p :: CAT k) Cartesian
  where
  data Struct Cartesian i o where
    ProdToTensor :: (Ob a, Ob b) => Struct Cartesian (a *! b) (a **! b)
    TensorToProd :: (Ob a, Ob b) => Struct Cartesian (a **! b) (a *! b)
    TermToUnit :: Struct Cartesian TermF UnitF
    UnitToTerm :: Struct Cartesian UnitF TermF
  foldStructure :: forall {k'} (f :: k +-> k') (a :: FREE cs p) (b :: FREE cs p).
(Cartesian k', All cs k', Representable f) =>
(forall (x :: FREE cs p) (y :: FREE cs p).
 (x ~> y) -> Lower f x ~> Lower f y)
-> Struct Cartesian a b -> Lower f a ~> Lower f b
foldStructure @f forall (x :: FREE cs p) (y :: FREE cs p).
(x ~> y) -> Lower f x ~> Lower f y
_ (ProdToTensor @a @b) =
    forall {k} {k'} {cs :: [Type -> Constraint]} {p :: CAT k}
       (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
forall (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
withLowerOb @f @a (forall {k} {k'} {cs :: [Type -> Constraint]} {p :: CAT k}
       (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
forall (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
withLowerOb @f @b (forall (a :: k') (b :: k').
(HasBinaryProducts k', TensorIsProduct a b, Ob a, Ob b) =>
(a && b) ~> (a ** b)
forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) =>
(a && b) ~> (a ** b)
productToTensor @(Lower f a) @(Lower f b)))
  foldStructure @f forall (x :: FREE cs p) (y :: FREE cs p).
(x ~> y) -> Lower f x ~> Lower f y
_ (TensorToProd @a @b) =
    forall {k} {k'} {cs :: [Type -> Constraint]} {p :: CAT k}
       (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
forall (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
withLowerOb @f @a (forall {k} {k'} {cs :: [Type -> Constraint]} {p :: CAT k}
       (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
forall (f :: k +-> k') (a :: FREE cs p) r.
(IsFreeOb a, Representable f, All cs k') =>
(Ob (Lower f a) => r) -> r
withLowerOb @f @b (forall (a :: k') (b :: k').
(HasBinaryProducts k', TensorIsProduct a b, Ob a, Ob b) =>
(a ** b) ~> (a && b)
forall {k} (a :: k) (b :: k).
(HasBinaryProducts k, TensorIsProduct a b, Ob a, Ob b) =>
(a ** b) ~> (a && b)
tensorToProduct @(Lower f a) @(Lower f b)))
  foldStructure forall (x :: FREE cs p) (y :: FREE cs p).
(x ~> y) -> Lower f x ~> Lower f y
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
TermToUnit = Lower f a ~> Lower f b
TerminalObject ~> TerminalObject
forall (a :: k'). Ob a => a ~> a
forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id
  foldStructure forall (x :: FREE cs p) (y :: FREE cs p).
(x ~> y) -> Lower f x ~> Lower f y
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
UnitToTerm = Lower f a ~> Lower f b
TerminalObject ~> TerminalObject
forall (a :: k'). Ob a => a ~> a
forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id

instance P.Show (Struct Cartesian a b) where
  showsPrec :: Int -> Struct Cartesian a b -> ShowS
showsPrec Int
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
ProdToTensor = String -> ShowS
P.showString String
"prodToTensor"
  showsPrec Int
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
TensorToProd = String -> ShowS
P.showString String
"tensorToProd"
  showsPrec Int
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
TermToUnit = String -> ShowS
P.showString String
"termToUnit"
  showsPrec Int
_ Struct Cartesian a b
R:StructkcspCartesianio k cs p a b
UnitToTerm = String -> ShowS
P.showString String
"unitToTerm"

-- | The formal @tensor = product@ isomorphisms of a free category with 'Cartesian' in its list.
prodToTensor
  :: forall {k} {cs} {p :: CAT k} (a :: FREE cs p) b
   . ('[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] `Elems` cs, Ob a, Ob b)
  => (a *! b) ~> (a **! b)
prodToTensor :: forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p) (b :: FREE cs p).
(Elems
   '[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] cs,
 Ob a, Ob b) =>
(a *! b) ~> (a **! b)
prodToTensor = Struct Cartesian (a *! b) (a **! b)
-> Free (a *! b) (a *! b) -> Free (a *! b) (a **! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (c :: Type -> Constraint) (a1 :: FREE cs p) (b :: FREE cs p)
       (a :: FREE cs p).
(HasStructure cs p c, Ob a1, Ob b) =>
Struct c a1 b -> Free a a1 -> Free a b
St Struct Cartesian (a *! b) (a **! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p) (b :: FREE cs p).
(Ob a, Ob b) =>
Struct Cartesian (a *! b) (a **! b)
ProdToTensor Free (a *! b) (a *! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p).
Ob a =>
Free a a
Nil

tensorToProd
  :: forall {k} {cs} {p :: CAT k} (a :: FREE cs p) b
   . ('[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] `Elems` cs, Ob a, Ob b)
  => (a **! b) ~> (a *! b)
tensorToProd :: forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p) (b :: FREE cs p).
(Elems
   '[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] cs,
 Ob a, Ob b) =>
(a **! b) ~> (a *! b)
tensorToProd = Struct Cartesian (a **! b) (a *! b)
-> Free (a **! b) (a **! b) -> Free (a **! b) (a *! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (c :: Type -> Constraint) (a1 :: FREE cs p) (b :: FREE cs p)
       (a :: FREE cs p).
(HasStructure cs p c, Ob a1, Ob b) =>
Struct c a1 b -> Free a a1 -> Free a b
St Struct Cartesian (a **! b) (a *! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p) (b :: FREE cs p).
(Ob a, Ob b) =>
Struct Cartesian (a **! b) (a *! b)
TensorToProd Free (a **! b) (a **! b)
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p).
Ob a =>
Free a a
Nil

termToUnit
  :: forall {k} {cs} {p :: CAT k}
   . ('[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] `Elems` cs)
  => (TermF :: FREE cs p) ~> UnitF
termToUnit :: forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}.
Elems
  '[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] cs =>
TermF ~> UnitF
termToUnit = Struct Cartesian TermF UnitF
-> Free TermF TermF -> Free TermF UnitF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (c :: Type -> Constraint) (a1 :: FREE cs p) (b :: FREE cs p)
       (a :: FREE cs p).
(HasStructure cs p c, Ob a1, Ob b) =>
Struct c a1 b -> Free a a1 -> Free a b
St Struct Cartesian TermF UnitF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}.
Struct Cartesian TermF UnitF
TermToUnit Free TermF TermF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p).
Ob a =>
Free a a
Nil

unitToTerm
  :: forall {k} {cs} {p :: CAT k}
   . ('[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] `Elems` cs)
  => (UnitF :: FREE cs p) ~> TermF
unitToTerm :: forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}.
Elems
  '[Cartesian, HasTerminalObject, HasBinaryProducts, Monoidal] cs =>
UnitF ~> TermF
unitToTerm = Struct Cartesian UnitF TermF
-> Free UnitF UnitF -> Free UnitF TermF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (c :: Type -> Constraint) (a1 :: FREE cs p) (b :: FREE cs p)
       (a :: FREE cs p).
(HasStructure cs p c, Ob a1, Ob b) =>
Struct c a1 b -> Free a a1 -> Free a b
St Struct Cartesian UnitF TermF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}.
Struct Cartesian UnitF TermF
UnitToTerm Free UnitF UnitF
forall {k} {cs :: [Type -> Constraint]} {p :: CAT k}
       (a :: FREE cs p).
Ob a =>
Free a a
Nil