{-# LANGUAGE AllowAmbiguousTypes #-}
-- The instances on 'SHEAVES' are orphans for the reason "Proarrow.Category.Enriched.Finitary.Topos"
-- gives for its own: the kind is 'SUBCAT' of a predicate, and both come from other modules.
{-# OPTIONS_GHC -Wno-orphans #-}

-- | Sheaves on a finite site, decided by enumeration.
--
-- A site is a category where each object @a@ has some /covers/: families of arrows into @a@. A
-- profunctor is a sheaf when an element at @a@ is the same thing as a /matching family/ on a
-- cover: one element at the source of each leg, agreeing wherever two legs overlap. With finitely
-- many objects and elements both sides can be listed, and 'sheafAt' compares the two lists. They
-- must agree as multisets. Equal lengths are not enough: a presheaf can have as many elements as
-- matching families and still not be a sheaf.
--
-- A cover of @a@ generates a 'Sieve', the arrows into @a@ that factor through a leg, and the
-- matching families are the natural transformations out of it ('withSieve').
--
-- The coverage also gives a closure on sieves ('closure', 'lawvereTierney'), truth values
-- ('ClosedSieve') and a sheafification ('Sheafify') with its unit and universal property. All of
-- them are computed, so they too can be enumerated and compared, and together they make 'SHEAVES'
-- an elementary topos.
module Proarrow.Category.Enriched.Finitary.Sheaf where

import Data.List (find, genericIndex, genericLength, sort)
import Data.Map.Strict qualified as M
import Data.Maybe (fromMaybe, isJust, listToMaybe, mapMaybe)
import Numeric.Natural (Natural)
import Prelude (type (~))
import Prelude qualified as P

import Proarrow.Category.Enriched.Finitary
  ( Finitary (..)
  , FiniteCat
  , LocallyFinite
  , factorThrough
  , factorsThrough
  , foreachOb
  )
import Proarrow.Category.Enriched.Finitary.Topos
  ( FINITARY
  , KnownTables
  , Reindex
  , Retabulation (..)
  , Tabulated
  , coequalizeNat
  , equalizeNat
  , factorThroughEqualizer
  , familyIndex
  , fromTabulated
  , graphSieve
  , natDomain
  , natElements
  , natIndex
  , natKey
  , natPositionsBy
  , natTable
  , preimageMaybe
  , sieveTable
  , toTabulated
  , withSubobject
  , withTables
  )
import Proarrow.Category.Enriched.Thin (Enumerable)
import Proarrow.Category.Instance.Opposite (OPPOSITE (..))
import Proarrow.Category.Instance.Prof (Prof (..))
import Proarrow.Category.Instance.Sub (SUBCAT (..), Sub (..))
import Proarrow.Category.Sheaf
  ( Coverage
  , Factors (..)
  , HasFiniteCovers (..)
  , PulledBack (..)
  , Sheaf (..)
  , Site (..)
  , SomeCover (..)
  , SomeLeg (..)
  , StableSite (..)
  )
import Proarrow.Category.Topos (ElementaryTopos, HasEpiMonoFactorization, HasSubobjectClassifier (..))
import Proarrow.Colimit.BinaryCoproduct (HasBinaryCoproducts (..))
import Proarrow.Colimit.Coequalizer (HasCoequalizers (..))
import Proarrow.Colimit.Initial (HasInitialObject (..))
import Proarrow.Colimit.Pushout (HasPushouts (..))
import Proarrow.Core
  ( CategoryOf (..)
  , Kind
  , OB
  , Profunctor (..)
  , Promonad (..)
  , UN
  , (//)
  , (\\)
  , type (+->)
  , type (:&&:)
  , type (:~>)
  )
import Proarrow.Limit.BinaryProduct (PROD (..), Prod (..))
import Proarrow.Limit.Equalizer (HasEqualizers (..))
import Proarrow.Limit.Pullback (HasPullbacks)
import Proarrow.Profunctor.Instance.Coproduct ((:+:) (..))
import Proarrow.Profunctor.Instance.Exponential ((:~>:) (..))
import Proarrow.Profunctor.Instance.Initial (InitialProfunctor)
import Proarrow.Profunctor.Instance.Sieve (Sieve (..), maximalSieve, sieveMeet)
import Proarrow.Profunctor.Instance.Terminal (TerminalProfunctor (..))
import Proarrow.Profunctor.Instance.Yoneda (Yo (..))

-- * Sieves and their closure

-- | The sieve a cover generates at @(a, b)@: the arrows into @a@ that factor through a leg,
-- paired with every arrow out of @b@.
generatedSieve
  :: forall t {j} {k} (a :: k) (b :: j) c
   . (Site t k, LocallyFinite k, CategoryOf j, Ob a, Ob b)
  => Cover t k a c
  -> Sieve a b
generatedSieve :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j) (c :: Coverage).
(Site t k, LocallyFinite k, CategoryOf j, Ob a, Ob b) =>
Cover t k a c -> Sieve a b
generatedSieve Cover t k a c
c = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
g b ~> d
_ -> (SomeLeg t k a c -> Bool) -> [SomeLeg t k a c] -> Bool
forall (t :: Coverage -> Coverage) (a :: Coverage).
Foldable t =>
(a -> Bool) -> t a -> Bool
P.any (\(SomeLeg Leg t k a c x
l) -> let f :: x ~> a
f = Leg t k a c x -> x ~> a
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l in (c ~> a) -> (x ~> a) -> Bool
forall {k :: Coverage} (x :: k) (y :: k) (a :: k).
(LocallyFinite k, Ob x, Ob y, Ob a) =>
(x ~> a) -> (y ~> a) -> Bool
factorsThrough c ~> a
g x ~> a
f ((Ob x, Ob a) => Bool) -> (x ~> a) -> Bool
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ x ~> a
f ((Ob c, Ob a) => Bool) -> (c ~> a) -> Bool
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ c ~> a
g) (Cover t k a c -> [SomeLeg t k a c]
forall (a :: k) (c :: Coverage). Cover t k a c -> [SomeLeg t k a c]
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage).
Site t k =>
Cover t k a c -> [SomeLeg t k a c]
legs Cover t k a c
c)

-- | Whether a sieve is the maximal one, containing every arrow of the category.
isMaximal :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k) => Sieve a b -> P.Bool
isMaximal :: forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isMaximal Sieve a b
s = [Bool] -> Bool
forall (t :: Coverage -> Coverage). Foldable t => t Bool -> Bool
P.and (Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s)

-- | Whether every point of the second sieve is a point of the first.
contains :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k) => Sieve a b -> Sieve a b -> P.Bool
contains :: forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b -> Bool
contains Sieve a b
s = \Sieve a b
s' -> [Bool] -> Bool
forall (t :: Coverage -> Coverage). Foldable t => t Bool -> Bool
P.and ((Bool -> Bool -> Bool) -> [Bool] -> [Bool] -> [Bool]
forall (a :: Coverage) (b :: Coverage) (c :: Coverage).
(a -> b -> c) -> [a] -> [b] -> [c]
P.zipWith (\Bool
x Bool
y -> Bool -> Bool
P.not Bool
y Bool -> Bool -> Bool
P.|| Bool
x) [Bool]
ts (Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s'))
  where
    -- tabulated before the second sieve arrives, so a partial application tabulates @s@ once
    ts :: [Bool]
ts = Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s

-- | Whether a sieve is covering: either it is the maximal sieve, or it contains the sieve that some
-- cover of its object generates. A sieve is closed under composition, so that amounts to
-- containing the cover's legs ('coveringCover').
--
-- This takes the coverage at face value. It agrees with the Grothendieck topology the coverage
-- generates only when the covers are stable and compose. When they do not, 'closure' stops being
-- idempotent, which 'Proarrow.Testing.Laws.testLawvereTierney' detects.
isCovering
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k)
  => Sieve a b
  -> P.Bool
isCovering :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isCovering Sieve a b
s = Sieve a b -> Bool
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isMaximal Sieve a b
s Bool -> Bool -> Bool
P.|| Maybe (SomeCover t k a) -> Bool
forall (a :: Coverage). Maybe a -> Bool
isJust (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, CategoryOf j) =>
Sieve a b -> Maybe (SomeCover t k a)
coveringCover @t Sieve a b
s)

-- | The first listed cover all of whose legs lie in the sieve, if there is one. Both 'isCovering'
-- and 'extendPlus' use this search. It needs no tabulation, since whether a sieve contains the
-- legs at the identity decides whether it contains everything they generate.
--
-- This relies on the closure that "Proarrow.Profunctor.Instance.Sieve" does not enforce. On a
-- hand-built predicate that is not a sieve it can say yes where comparing the whole generated
-- sieve says no.
coveringCover
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, CategoryOf j)
  => Sieve a b
  -> P.Maybe (SomeCover t k a)
coveringCover :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, CategoryOf j) =>
Sieve a b -> Maybe (SomeCover t k a)
coveringCover (Sieve forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s) = (SomeCover t k a -> Bool)
-> [SomeCover t k a] -> Maybe (SomeCover t k a)
forall (t :: Coverage -> Coverage) (a :: Coverage).
Foldable t =>
(a -> Bool) -> t a -> Maybe a
find (\(SomeCover Cover t k a c
c) -> (SomeLeg t k a c -> Bool) -> [SomeLeg t k a c] -> Bool
forall (t :: Coverage -> Coverage) (a :: Coverage).
Foldable t =>
(a -> Bool) -> t a -> Bool
P.all (\(SomeLeg Leg t k a c x
l) -> (x ~> a) -> (b ~> b) -> Bool
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s (Leg t k a c x -> x ~> a
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l) b ~> b
forall (a :: j). Ob a => a ~> a
forall {k :: Coverage} (p :: CAT k) (a :: k).
(Promonad p, Ob a) =>
p a a
id) (Cover t k a c -> [SomeLeg t k a c]
forall (a :: k) (c :: Coverage). Cover t k a c -> [SomeLeg t k a c]
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage).
Site t k =>
Cover t k a c -> [SomeLeg t k a c]
legs Cover t k a c
c)) (forall (t :: Coverage) (k :: Coverage) (a :: k).
(HasFiniteCovers t k, Ob a) =>
[SomeCover t k a]
covers @t @k @a)

-- | The Lawvere–Tierney closure of a sieve: the pairs @(g, h)@ along which it pulls back to a
-- covering one. A sieve is covering iff its closure is the maximal sieve.
--
-- This uses @'dimap' g h@, not @'lmap' g@. A coverage constrains only the contravariant side, but
-- a sieve over @j '+->' k@ has two sides, and 'closure' has to be natural in both.
closure
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k)
  => Sieve a b
  -> Sieve a b
closure :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b
closure s :: Sieve a b
s@Sieve{} = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
g b ~> d
h -> forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isCovering @t ((c ~> a) -> (b ~> d) -> Sieve a b -> Sieve c d
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> Sieve a b -> Sieve c d
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
g b ~> d
h Sieve a b
s) ((Ob c, Ob a) => Bool) -> (c ~> a) -> Bool
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ c ~> a
g ((Ob b, Ob d) => Bool) -> (b ~> d) -> Bool
forall (a :: j) (b :: j) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ b ~> d
h

-- | Whether a sieve is /closed/ for the topology, i.e. equal to its own 'closure'. These are the
-- truth values of the sheaf topos, as the sieves are of the presheaf one (see 'ClosedSieve').
isClosed
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k)
  => Sieve a b
  -> P.Bool
isClosed :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isClosed Sieve a b
s = Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b
closure @t Sieve a b
s) [Bool] -> [Bool] -> Bool
forall (a :: Coverage). Eq a => a -> a -> Bool
P.== Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s

-- | The coverage as a Lawvere–Tierney topology on the topos of finitary profunctors: 'closure', as
-- an arrow on the subobject classifier.
lawvereTierney
  :: forall t j k. (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => (Omega :: PROD (FINITARY j k)) ~> Omega
lawvereTierney :: forall (t :: Coverage) (j :: Coverage) (k :: Coverage).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Omega ~> Omega
lawvereTierney = Sub Prof (SUB Sieve) (SUB Sieve)
-> Prod (Sub Prof) (PR (SUB Sieve)) (PR (SUB Sieve))
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a1 :: k)
       (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (Prof Sieve Sieve -> Sub Prof (SUB Sieve) (SUB Sieve)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((Sieve :~> Sieve) -> Prof Sieve Sieve
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \s :: Sieve a b
s@Sieve{} -> forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b
closure @t Sieve a b
s))

-- * Deciding the sheaf condition

-- | Whether a finitary profunctor is a sheaf for the coverage: at every pair of objects and every
-- cover, restriction is a bijection from the elements at the covered object to the matching
-- families on the sieve the cover generates.
isSheaf
  :: forall t {j} {k} (p :: j +-> k)
   . (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k)
  => P.Bool
isSheaf :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) =>
Bool
isSheaf =
  [Bool] -> Bool
forall (t :: Coverage -> Coverage). Foldable t => t Bool -> Bool
P.and
    ( forall (k :: Coverage) (r :: Coverage).
Enumerable k =>
(forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @a ->
        let cs :: [SomeCover t k a]
cs = forall (t :: Coverage) (k :: Coverage) (a :: k).
(HasFiniteCovers t k, Ob a) =>
[SomeCover t k a]
covers @t @k @a -- does not depend on @b@, so bound outside the inner walk
        in forall (k :: Coverage) (r :: Coverage).
Enumerable k =>
(forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @b -> [forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j) (c :: Coverage).
(Site t k, Finitary p, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Cover t k a c -> Bool
sheafAt @t @p @a @b Cover t k a c
c | SomeCover Cover t k a c
c <- [SomeCover t k a]
cs]
    )

-- | The sheaf condition at one cover: the restrictions of the elements at the covered object are
-- the matching families on the sieve it generates, as multisets.
sheafAt
  :: forall t {j} {k} (p :: j +-> k) (a :: k) (b :: j) c
   . (Site t k, Finitary p, FiniteCat j, FiniteCat k, Ob a, Ob b)
  => Cover t k a c
  -> P.Bool
sheafAt :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j) (c :: Coverage).
(Site t k, Finitary p, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Cover t k a c -> Bool
sheafAt Cover t k a c
c = Sieve a b
-> (forall (q :: j +-> k).
    Finitary q =>
    (q :~> Yo a (OP b)) -> Bool)
-> Bool
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j) (c :: Coverage).
(Site t k, LocallyFinite k, CategoryOf j, Ob a, Ob b) =>
Cover t k a c -> Sieve a b
generatedSieve @t @a @b Cover t k a c
c) \ @q q :~> Yo a (OP b)
incl ->
  [[Natural]] -> [[Natural]]
forall (a :: Coverage). Ord a => [a] -> [a]
sort [forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
(p :~> q) -> [Natural]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
(p :~> q) -> [Natural]
natTable @q @p (\q a b
y -> case q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl q a b
y of Yo a ~> a
g b1 ~> b
h -> (a ~> a) -> (b ~> b) -> p a b -> p a b
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> p a b -> p c d
forall {j :: Coverage} {k :: Coverage} (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
g b ~> b
b1 ~> b
h p a b
x) | p a b
x <- forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @p @a @b]
    [[Natural]] -> [[Natural]] -> Bool
forall (a :: Coverage). Eq a => a -> a -> Bool
P.== [[Natural]] -> [[Natural]]
forall (a :: Coverage). Ord a => [a] -> [a]
sort (forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
natElements @q @p)

-- | A sieve as a subobject of the representable @'Yo' a ('OP' b)@, handed on with its inclusion.
-- A natural transformation out of it picks an element for every arrow in the sieve, compatibly
-- with precomposition, which is what a matching family on the sieve is. 'sheafAt' and 'Plus' both
-- define matching families this way.
--
-- The error branch is unreachable for any coverage, since 'generatedSieve' and 'leastDenseSieve'
-- always give real sieves. Reaching it would take a 'Finitary' instance on the hom-profunctor
-- whose 'elements' omits an arrow, which 'Proarrow.Testing.Laws.testFinitary' rules out.
withSieve
  :: forall {j} {k} (a :: k) (b :: j) r
   . (FiniteCat j, FiniteCat k)
  => Sieve a b
  -> (forall q. (Finitary q) => (q :~> Yo a (OP b)) -> r)
  -> r
withSieve :: forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (Sieve forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s) forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r
k =
  forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool)
-> (forall (q :: j +-> k). Finitary q => (FIN q ~> FIN p) -> r)
-> r
-> r
forall (p :: j +-> k) (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool)
-> (forall (q :: j +-> k). Finitary q => (FIN q ~> FIN p) -> r)
-> r
-> r
withSubobject @(Yo a (OP b))
    (\(Yo a ~> a
g b1 ~> b
h) -> (a ~> a) -> (b ~> b) -> Bool
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s a ~> a
g b ~> b
b1 ~> b
h)
    (\ @q (Sub (Prof q :~> Yo a (OP b)
incl)) -> forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r
k @q q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl)
    ([Char] -> r
forall a. HasCallStack => [Char] -> a
P.error [Char]
"withSieve: not a sieve")

-- * Presenting a sheaf by its tables

-- | Present a finitary profunctor by its tables, as
-- 'Proarrow.Category.Enriched.Finitary.Topos.withTabulated' does, tagged with the coverage so that
-- it has a 'Sheaf' instance. That instance is decided here by 'isSheaf'; the failure continuation
-- is taken when @p@ is no sheaf for @t@.
--
-- This makes a sheaf with no 'Sheaf' instance of its own (a representable, a sheafification) an
-- object of 'SHEAVES'. Deciding on the tables is also cheaper than on @p@: a 'Sheafify' answers
-- each 'toIndex' by re-running the plus construction.
withTabulatedSheaf
  :: forall t {j} {k} (p :: j +-> k) r
   . (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k)
  => ( forall {lm} {rm} (tab :: j +-> k)
        . (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab)
       => (p :~> tab)
       -> (tab :~> p)
       -> r
     )
  -> r
  -> r
withTabulatedSheaf :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (r :: Coverage).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) =>
(forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
 (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
 (p :~> tab) -> (tab :~> p) -> r)
-> r -> r
withTabulatedSheaf forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
ok r
notSheaf = forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
forall (p :: j +-> k) (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
withTables @p \ @lm @rm ->
  if forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) =>
Bool
isSheaf @t @(Tabulated t lm rm :: j +-> k)
    then forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
forall (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
ok @(Tabulated t lm rm) p a b -> Tabulated t lm rm a b
p :~> Tabulated t lm rm
forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k).
Finitary p =>
p :~> Tabulated t lm rm
toTabulated Tabulated t lm rm a b -> p a b
Tabulated t lm rm :~> p
forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k).
Finitary p =>
Tabulated t lm rm :~> p
fromTabulated
    else r
notSheaf

-- | 'withTabulatedSheaf' for a profunctor that already is a 'Sheaf', so there is nothing to decide.
-- The colimits below present their apex, a 'Sheafify', with this, because an unpresented
-- 'Sheafify' re-runs the whole plus construction each time the continuation asks for elements.
withSheafTables
  :: forall t {j} {k} (p :: j +-> k) r
   . (Sheaf t p, Finitary p, FiniteCat j, FiniteCat k)
  => ( forall {lm} {rm} (tab :: j +-> k)
        . (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab)
       => (p :~> tab)
       -> (tab :~> p)
       -> r
     )
  -> r
withSheafTables :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (r :: Coverage).
(Sheaf t p, Finitary p, FiniteCat j, FiniteCat k) =>
(forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
 (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
 (p :~> tab) -> (tab :~> p) -> r)
-> r
withSheafTables forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
ok = forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
forall (p :: j +-> k) (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
withTables @p \ @lm @rm -> forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
forall (tab :: j +-> k).
(tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
(p :~> tab) -> (tab :~> p) -> r
ok @(Tabulated t lm rm) p a b -> Tabulated t lm rm a b
p :~> Tabulated t lm rm
forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k).
Finitary p =>
p :~> Tabulated t lm rm
toTabulated Tabulated t lm rm a b -> p a b
Tabulated t lm rm :~> p
forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k).
Finitary p =>
Tabulated t lm rm :~> p
fromTabulated

-- * Descent

-- | Extend a /partial/ natural transformation into a sheaf to a total one. Where @f@ is undefined
-- at an element @y@, it must be defined on the restrictions of @y@ along the legs of some listed
-- cover, and those values are glued in @q@. Only this one level of descent is tried.
--
-- 'extendPlus' is this at @'Plus' t p@. The colimits below need it because an epimorphism of
-- sheaves is only /locally/ onto: an element may have no preimage while its restrictions along a
-- cover all do.
--
-- 'glue' is lawful here when @f@ commutes with restriction where it is defined. For the callers
-- below that means the arrow being factored is constant on the fibres it factors through.
factorLocally
  :: forall t {j} {k} (p :: j +-> k) q
   . (HasFiniteCovers t k, CategoryOf j, Profunctor p, Sheaf t q)
  => (forall c d. (Ob c, Ob d) => p c d -> P.Maybe (q c d))
  -> p :~> q
factorLocally :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Profunctor p, Sheaf t q) =>
(forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d))
-> p :~> q
factorLocally forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d)
f p a b
y =
  p a b
y p a b -> ((Ob a, Ob b) => q a b) -> q a b
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// case p a b -> Maybe (q a b)
forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d)
f p a b
y of
    P.Just q a b
v -> q a b
v
    Maybe (q a b)
P.Nothing -> case forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, CategoryOf j) =>
Sieve a b -> Maybe (SomeCover t k a)
coveringCover @t (p a b -> Sieve a b
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Sieve a b
domainSieve p a b
y) of
      P.Just (SomeCover Cover t k a c
c) ->
        -- the error is unreachable: 'coveringCover' returned this cover by testing these same legs
        forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (p :: j +-> k) (a :: k) (c :: Coverage) (b :: j).
(Sheaf t p, Ob a, Ob b) =>
Cover t k a c -> (forall (x :: k). Leg t k a c x -> p x b) -> p a b
forall (t :: Coverage) (p :: j +-> k) (a :: k) (c :: Coverage)
       (b :: j).
(Sheaf t p, Ob a, Ob b) =>
Cover t k a c -> (forall (x :: k). Leg t k a c x -> p x b) -> p a b
glue @t Cover t k a c
c \Leg t k a c x
l -> q x b -> Maybe (q x b) -> q x b
forall (a :: Coverage). a -> Maybe a -> a
fromMaybe ([Char] -> q x b
forall a. HasCallStack => [Char] -> a
P.error [Char]
"factorLocally: a leg outside the domain") (p x b -> Maybe (q x b)
forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d)
f ((x ~> a) -> p a b -> p x b
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap (Leg t k a c x -> x ~> a
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l) p a b
y) ((Ob x, Ob a) => Maybe (q x b)) -> (x ~> a) -> Maybe (q x b)
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ Leg t k a c x -> x ~> a
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l)
      Maybe (SomeCover t k a)
P.Nothing -> [Char] -> q a b
forall a. HasCallStack => [Char] -> a
P.error [Char]
"factorLocally: the partial transformation is not defined on a cover of this element"
  where
    -- where the partial function is defined on restrictions of @y@. This is a sieve, since a
    -- restriction of a restriction is one. Taking the element as an argument pins its objects.
    domainSieve :: forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Sieve a b
    domainSieve :: forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Sieve a b
domainSieve p a b
x = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
g b ~> d
_ -> Maybe (q c b) -> Bool
forall (a :: Coverage). Maybe a -> Bool
isJust (p c b -> Maybe (q c b)
forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d)
f ((c ~> a) -> p a b -> p c b
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap c ~> a
g p a b
x)) ((Ob c, Ob a) => Bool) -> (c ~> a) -> Bool
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ c ~> a
g

-- | Factor through a map that is onto only locally: @'factorLocally'@ of the preimage search.
-- Where 'Proarrow.Category.Enriched.Finitary.Topos.factorThroughCoequalizer' asks the map to be
-- onto, this asks only what being epi in the sheaves gives.
--
-- A pushout needs this for its pair of injections, which are jointly locally onto but not
-- separately. That case is this at the coproduct, since two arrows into an object are one arrow
-- out of @a ':+:' b@. One search over that is also one 'toIndex' of the element instead of two.
factorThroughLocalEpi
  :: forall t {j} {k} (c :: j +-> k) x c'
   . (HasFiniteCovers t k, CategoryOf j, Finitary c, Finitary x, Sheaf t c')
  => (x :~> c)
  -> (x :~> c')
  -> c :~> c'
factorThroughLocalEpi :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (c :: j +-> k) (x :: j +-> k) (c' :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Finitary c, Finitary x,
 Sheaf t c') =>
(x :~> c) -> (x :~> c') -> c :~> c'
factorThroughLocalEpi x :~> c
proj x :~> c'
h = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Profunctor p, Sheaf t q) =>
(forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d))
-> p :~> q
factorLocally @t \c c d
y -> (x c d -> c' c d) -> Maybe (x c d) -> Maybe (c' c d)
forall (a :: Coverage) (b :: Coverage).
(a -> b) -> Maybe a -> Maybe b
forall (f :: Coverage -> Coverage) (a :: Coverage) (b :: Coverage).
Functor f =>
(a -> b) -> f a -> f b
P.fmap x c d -> c' c d
x :~> c'
h ((x c d -> c c d) -> c c d -> Maybe (x c d)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, Ob a, Ob b) =>
(p a b -> q a b) -> q a b -> Maybe (p a b)
preimageMaybe x c d -> c c d
x :~> c
proj c c d
y)

-- * Sheafification

-- | One step of the plus construction for the topology @t@. A 'Plus' value is a matching family on
-- some dense sieve, given as a partial function: it is defined at @(g, h)@ iff that pair is in the
-- sieve ('support'), so the sieve cannot disagree with the family. Two values are the same
-- element when they agree on a dense sieve. Intuitively an element at @a@ is an element of @p@
-- given locally: pieces on a cover of @a@ that agree on overlaps.
--
-- On a finite site whose covers compose ('HasFiniteCovers'\'s Composition law) there is a least
-- dense sieve, 'leastDenseSieve', and each element has one family on it. A value is identified by
-- its restriction there ('plusTable'), which is what 'Finitary' numbers and "Proarrow.Testing"
-- compares, so no quotient is needed. 'leastDenseSieve' fails loudly where the law does not hold.
--
-- __The constructor does not check__ that the support is a dense sieve or that the family is
-- matching. 'plusElements' builds only lawful values; one built by hand is its builder's
-- responsibility.
type Plus :: forall {j} {k}. Coverage -> j +-> k -> j +-> k
data Plus t p a b where
  Plus :: (Ob a, Ob b) => (forall c d. c ~> a -> b ~> d -> P.Maybe (p c d)) -> Plus t p a b

instance (CategoryOf j, CategoryOf k) => Profunctor (Plus t p :: j +-> k) where
  dimap :: forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> Plus t p a b -> Plus t p c d
dimap c ~> a
l b ~> d
r (Plus forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f) = c ~> a
l (c ~> a) -> ((Ob c, Ob a) => Plus t p c d) -> Plus t p c d
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
r (b ~> d) -> ((Ob b, Ob d) => Plus t p c d) -> Plus t p c d
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// (forall (c :: k) (d :: j). (c ~> c) -> (d ~> d) -> Maybe (p c d))
-> Plus t p c d
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k) (t :: Coverage).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
Plus \c ~> c
g d ~> d
h -> (c ~> a) -> (b ~> d) -> Maybe (p c d)
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f (c ~> a
l (c ~> a) -> (c ~> c) -> c ~> a
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k :: Coverage} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. c ~> c
g) (d ~> d
h (d ~> d) -> (b ~> d) -> b ~> d
forall (b :: j) (c :: j) (a :: j). (b ~> c) -> (a ~> b) -> a ~> c
forall {k :: Coverage} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. b ~> d
r)
  (Ob a, Ob b) => r
r \\ :: forall (a :: k) (b :: j) (r :: Coverage).
((Ob a, Ob b) => r) -> Plus t p a b -> r
\\ Plus{} = r
(Ob a, Ob b) => r
r

-- | The sieve a value is defined on.
support :: Plus t p :~> Sieve
support :: forall {k1 :: Coverage} {k :: Coverage} (t :: Coverage)
       (p :: k1 +-> k) (a :: k) (b :: k1).
Plus t p a b -> Sieve a b
support (Plus forall (c :: k) (d :: k1). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f) = (forall (c :: k) (d :: k1). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
g b ~> d
h -> Maybe (p c d) -> Bool
forall (a :: Coverage). Maybe a -> Bool
isJust ((c ~> a) -> (b ~> d) -> Maybe (p c d)
forall (c :: k) (d :: k1). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f c ~> a
g b ~> d
h)

-- | Whether a sieve is dense for the topology: its 'closure' is the maximal sieve. On a lawful
-- coverage this agrees with 'isCovering' ('Proarrow.Testing.Laws.testDenseIsCovering' checks
-- that). But density is the stable notion, and 'Plus' needs stability, since 'dimap' pulls a
-- support back along arrows.
isDense
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k)
  => Sieve a b
  -> P.Bool
isDense :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isDense Sieve a b
s = Sieve a b -> Bool
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isMaximal (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b
closure @t Sieve a b
s)

-- | The meet of all the dense sieves at a pair of objects. When the covers compose, 'closure'
-- preserves meets, so this is the least dense sieve. Restriction to it picks one matching family
-- out of each element of 'Plus'. On a coverage whose covers pull back but do not compose the meet
-- need not be dense, and then this errors, naming the law that failed, instead of letting 'Plus'
-- compute on it. The smallest example is a poset @w ≤ x ≤ a@, @w ≤ y ≤ a@ with @a@ covered by @x@
-- and by @y@ separately and each of those by @w@.
leastDenseSieve
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b)
  => Sieve a b
leastDenseSieve :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Sieve a b
leastDenseSieve
  | forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isDense @t Sieve a b
s = Sieve a b
s
  | Bool
P.otherwise = [Char] -> Sieve a b
forall a. HasCallStack => [Char] -> a
P.error [Char]
"leastDenseSieve: the dense sieves have no least one -- the covers do not compose"
  where
    s :: Sieve a b
s = (Sieve a b -> Sieve a b -> Sieve a b)
-> Sieve a b -> [Sieve a b] -> Sieve a b
forall (a :: Coverage) (b :: Coverage).
(a -> b -> b) -> b -> [a] -> b
forall (t :: Coverage -> Coverage) (a :: Coverage) (b :: Coverage).
Foldable t =>
(a -> b -> b) -> b -> t a -> b
P.foldr Sieve a b -> Sieve a b -> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
Sieve a b -> Sieve a b -> Sieve a b
sieveMeet Sieve a b
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(CategoryOf j, CategoryOf k, Ob a, Ob b) =>
Sieve a b
maximalSieve ((Sieve a b -> Bool) -> [Sieve a b] -> [Sieve a b]
forall (a :: Coverage). (a -> Bool) -> [a] -> [a]
P.filter (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isDense @t) (forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Sieve :: j +-> k) @a @b))

-- | The elements of 'Plus' at a pair of objects: the matching families on the least dense sieve, in
-- the order 'natElements' lists them.
plusElements
  :: forall t {j} {k} (p :: j +-> k) (a :: k) (b :: j)
   . (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k, Ob a, Ob b)
  => [Plus t p a b]
plusElements :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k, Ob a,
 Ob b) =>
[Plus t p a b]
plusElements = Sieve a b
-> (forall (q :: j +-> k).
    Finitary q =>
    (q :~> Yo a (OP b)) -> [Plus t p a b])
-> [Plus t p a b]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Sieve a b
leastDenseSieve @t @a @b) \ @q q :~> Yo a (OP b)
incl ->
  -- the sieve's points as points of the representable, at the positions a row lists them
  let pos :: Map NatKey Int
pos = forall {j :: Coverage} {k :: Coverage} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey)
-> Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey)
-> Map NatKey Int
natPositionsBy @q \q a b
y -> Yo a (OP b) a b -> NatKey
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey (q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl q a b
y)
  in [ (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k) (t :: Coverage).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
Plus \c ~> a
g b ~> d
h -> c ~> a
g (c ~> a) -> ((Ob c, Ob a) => Maybe (p c d)) -> Maybe (p c d)
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
h (b ~> d) -> ((Ob b, Ob d) => Maybe (p c d)) -> Maybe (p c d)
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// (Int -> p c d) -> Maybe Int -> Maybe (p c d)
forall (a :: Coverage) (b :: Coverage).
(a -> b) -> Maybe a -> Maybe b
forall (f :: Coverage -> Coverage) (a :: Coverage) (b :: Coverage).
Functor f =>
(a -> b) -> f a -> f b
P.fmap (forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex @p (Natural -> p c d) -> (Int -> Natural) -> Int -> p c d
forall (b :: Coverage) (c :: Coverage) (a :: Coverage).
(b -> c) -> (a -> b) -> a -> c
P.. ([Natural]
row [Natural] -> Int -> Natural
forall (a :: Coverage). HasCallStack => [a] -> Int -> a
P.!!)) (NatKey -> Map NatKey Int -> Maybe Int
forall (k :: Coverage) (a :: Coverage).
Ord k =>
k -> Map k a -> Maybe a
M.lookup (Yo a (OP b) c d -> NatKey
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey ((c ~> a) -> (b ~> d) -> Yo a (OP b) c d
forall {k :: Coverage} {j :: Coverage} (c :: k) (a :: k) (b1 :: j)
       (d :: j).
(c ~> a) -> (b1 ~> d) -> Yo a (OP b1) c d
Yo c ~> a
g b ~> d
h)) Map NatKey Int
pos)
     | [Natural]
row <- forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
natElements @q @p
     ]

-- | A value restricted to a sieve reified as a subobject: the natural transformation out of it
-- that the value's family is.
restrictTo
  :: forall {j} {k} q (a :: k) (b :: j) t (p :: j +-> k)
   . (q :~> Yo a (OP b))
  -> Plus t p a b
  -> q :~> p
restrictTo :: forall {j :: Coverage} {k :: Coverage} (q :: k -> j -> Coverage)
       (a :: k) (b :: j) (t :: Coverage) (p :: k -> j -> Coverage).
(q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
restrictTo q :~> Yo a (OP b)
incl (Plus forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f) q a b
y = case q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl q a b
y of
  Yo a ~> a
g b1 ~> b
h ->
    p a b -> Maybe (p a b) -> p a b
forall (a :: Coverage). a -> Maybe a -> a
fromMaybe ([Char] -> p a b
forall a. HasCallStack => [Char] -> a
P.error [Char]
"restrictTo: the sieve is not inside the support -- see HasFiniteCovers's Composition law") ((a ~> a) -> (b ~> b) -> Maybe (p a b)
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d)
f a ~> a
g b ~> b
b1 ~> b
h)

-- | A value's restriction to the least dense sieve, as its 'natTable': the indices of its values
-- at that sieve's points. See 'Plus' for what that determines.
plusTable
  :: forall t {j} {k} (p :: j +-> k) (a :: k) (b :: j)
   . (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k)
  => Plus t p a b
  -> [Natural]
plusTable :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) =>
Plus t p a b -> [Natural]
plusTable x :: Plus t p a b
x@Plus{} = Sieve a b
-> (forall (q :: j +-> k).
    Finitary q =>
    (q :~> Yo a (OP b)) -> [Natural])
-> [Natural]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Sieve a b
leastDenseSieve @t @a @b) \ @q q :~> Yo a (OP b)
incl -> forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
(p :~> q) -> [Natural]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
(p :~> q) -> [Natural]
natTable @q @p ((q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
forall {j :: Coverage} {k :: Coverage} (q :: k -> j -> Coverage)
       (a :: k) (b :: j) (t :: Coverage) (p :: k -> j -> Coverage).
(q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
restrictTo q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl Plus t p a b
x)

-- | Whether two values stand for the same element: their restrictions to the least dense sieve
-- agree. This builds one sieve for the pair, where two 'plusTable's would each build their own.
-- "Proarrow.Testing"\'s equality on 'Plus' uses it, since it compares far more often than it shows.
samePlus
  :: forall t {j} {k} (p :: j +-> k) (a :: k) (b :: j)
   . (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k)
  => Plus t p a b
  -> Plus t p a b
  -> P.Bool
samePlus :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) =>
Plus t p a b -> Plus t p a b -> Bool
samePlus x :: Plus t p a b
x@Plus{} Plus t p a b
y = Sieve a b
-> (forall (q :: j +-> k).
    Finitary q =>
    (q :~> Yo a (OP b)) -> Bool)
-> Bool
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Sieve a b
leastDenseSieve @t @a @b) \ @q q :~> Yo a (OP b)
incl ->
  -- one walk for the pair, and one 'toIndex' per point: at 'Sheafify' that is itself an enumeration
  [Bool] -> Bool
forall (t :: Coverage -> Coverage). Foldable t => t Bool -> Bool
P.and
    (forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
forall (p :: j +-> k) (r :: Coverage).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain @q @P.Bool \ @c @d q a b
z -> let ix :: p a b -> Natural
ix = forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex @p @c @d in p a b -> Natural
ix ((q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
forall {j :: Coverage} {k :: Coverage} (q :: k -> j -> Coverage)
       (a :: k) (b :: j) (t :: Coverage) (p :: k -> j -> Coverage).
(q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
restrictTo q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl Plus t p a b
x q a b
z) Natural -> Natural -> Bool
forall (a :: Coverage). Eq a => a -> a -> Bool
P.== p a b -> Natural
ix ((q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
forall {j :: Coverage} {k :: Coverage} (q :: k -> j -> Coverage)
       (a :: k) (b :: j) (t :: Coverage) (p :: k -> j -> Coverage).
(q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
restrictTo q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl Plus t p a b
y q a b
z))

-- | Numbered by 'plusElements', as the internal hom is numbered by the natural transformations
-- out of its weight.
instance (HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k) => Finitary (Plus t p :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [Plus t p a b] -> Natural
forall (i :: Coverage) (a :: Coverage). Num i => [a] -> i
genericLength (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k, Ob a,
 Ob b) =>
[Plus t p a b]
plusElements @t @p @a @b)

  -- above the argument lambda: the sieve too, not just 'natIndex'\'s enumeration
  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Plus t p a b -> Natural
toIndex @a @b = Sieve a b
-> (forall (q :: j +-> k).
    Finitary q =>
    (q :~> Yo a (OP b)) -> Plus t p a b -> Natural)
-> Plus t p a b
-> Natural
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j)
       (r :: Coverage).
(FiniteCat j, FiniteCat k) =>
Sieve a b
-> (forall (q :: j +-> k). Finitary q => (q :~> Yo a (OP b)) -> r)
-> r
withSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Sieve a b
leastDenseSieve @t @a @b) \ @q q :~> Yo a (OP b)
incl ->
    let ix :: (q :~> p) -> Natural
ix = forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[Char] -> (p :~> q) -> Natural
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[Char] -> (p :~> q) -> Natural
natIndex @q @p [Char]
"toIndex: not natural on the least dense sieve"
    in \Plus t p a b
x -> (q :~> p) -> Natural
ix ((q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
forall {j :: Coverage} {k :: Coverage} (q :: k -> j -> Coverage)
       (a :: k) (b :: j) (t :: Coverage) (p :: k -> j -> Coverage).
(q :~> Yo a (OP b)) -> Plus t p a b -> q :~> p
restrictTo q a b -> Yo a (OP b) a b
q :~> Yo a (OP b)
incl Plus t p a b
x)
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Plus t p a b
fromIndex @a @b = [Plus t p a b] -> Natural -> Plus t p a b
forall (i :: Coverage) (a :: Coverage). Integral i => [a] -> i -> a
genericIndex (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k, Ob a,
 Ob b) =>
[Plus t p a b]
plusElements @t @p @a @b)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Plus t p a b]
elements @a @b = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (a :: k) (b :: j).
(HasFiniteCovers t k, Finitary p, FiniteCat j, FiniteCat k, Ob a,
 Ob b) =>
[Plus t p a b]
plusElements @t @p @a @b

-- | Sheafification: the plus construction twice. One 'Plus' makes a profunctor /separated/ (two
-- elements with the same restrictions to a dense sieve are equal), and the second makes it a
-- sheaf. The first alone need not: the constant presheaf with two values on the discrete two-point
-- space has one section over the empty set after one plus, but still two over the whole space
-- where a sheaf needs four. On a site whose covers have no overlaps, such as
-- 'Proarrow.Category.Sheaf.Atomic' on the walking arrow, one plus is already a sheaf and the
-- second changes nothing.
type Sheafify :: forall {j} {k}. Coverage -> j +-> k -> j +-> k
type Sheafify t p = Plus t (Plus t p)

-- | The unit of the plus construction: an element as the family of its own restrictions, on the
-- maximal sieve.
unitPlus :: forall t {j} {k} (p :: j +-> k). (Profunctor p) => p :~> Plus t p
unitPlus :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Plus t p
unitPlus p a b
x = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k) (t :: Coverage).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
Plus (\c ~> a
g b ~> d
h -> p c d -> Maybe (p c d)
forall (a :: Coverage). a -> Maybe a
P.Just ((c ~> a) -> (b ~> d) -> p a b -> p c d
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> p a b -> p c d
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
g b ~> d
h p a b
x)) ((Ob a, Ob b) => Plus t p a b) -> p a b -> Plus t p a b
forall (a :: k) (b :: j) (r :: Coverage).
((Ob a, Ob b) => r) -> p a b -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a b
x

-- | 'unitPlus' twice: the unit of sheafification.
unitSheafify :: forall t {j} {k} (p :: j +-> k). (Profunctor p) => p :~> Sheafify t p
unitSheafify :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify p a b
x = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Plus t p
unitPlus @t (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Plus t p
unitPlus @t p a b
x)

-- | The universal property, one plus at a time: a map into a sheaf extends along 'unitPlus'. A
-- dense support is either everything, and then the family is read off at the identity, or it
-- contains the legs of some listed cover (density at the identity says so, and 'coveringCover'
-- finds it), and then the family restricted to those legs glues. Since @q@ is a sheaf, it does not
-- matter which cover is found. @q@ need not be 'Finitary'; only gluing is asked of it.
extendPlus
  :: forall t {j} {k} (p :: j +-> k) q
   . (HasFiniteCovers t k, Sheaf t q)
  => (p :~> q) -> Plus t p :~> q
extendPlus :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Plus t p :~> q
extendPlus p :~> q
n = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Profunctor p, Sheaf t q) =>
(forall (c :: k) (d :: j). (Ob c, Ob d) => p c d -> Maybe (q c d))
-> p :~> q
factorLocally @t \(Plus forall (c :: k) (d :: j). (c ~> c) -> (d ~> d) -> Maybe (p c d)
f) -> (p c d -> q c d) -> Maybe (p c d) -> Maybe (q c d)
forall (a :: Coverage) (b :: Coverage).
(a -> b) -> Maybe a -> Maybe b
forall (f :: Coverage -> Coverage) (a :: Coverage) (b :: Coverage).
Functor f =>
(a -> b) -> f a -> f b
P.fmap p c d -> q c d
p :~> q
n ((c ~> c) -> (d ~> d) -> Maybe (p c d)
forall (c :: k) (d :: j). (c ~> c) -> (d ~> d) -> Maybe (p c d)
f c ~> c
forall (a :: k). Ob a => a ~> a
forall {k :: Coverage} (p :: CAT k) (a :: k).
(Promonad p, Ob a) =>
p a a
id d ~> d
forall (a :: j). Ob a => a ~> a
forall {k :: Coverage} (p :: CAT k) (a :: k).
(Promonad p, Ob a) =>
p a a
id)

-- | Gluing for the plus construction: a matching family over a cover, assembled into one value.
-- At @(g, h)@ it takes the first leg @l@ with @g = l . u@ ('factorThrough') whose family is
-- defined at @(u, h)@. The support of the result is generated by the legs' supports, so it is dense
-- by 'Proarrow.Category.Sheaf.HasFiniteCovers'\'s Composition law. For a matching family the choice
-- of leg and factorisation does not matter, and 'glue' promises nothing on others.
gluePlus
  :: forall t {j} {k} (q :: j +-> k) (a :: k) c (b :: j)
   . (Site t k, LocallyFinite k, Ob a, Ob b)
  => Cover t k a c
  -> (forall x. Leg t k a c x -> Plus t q x b)
  -> Plus t q a b
gluePlus :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (q :: j +-> k) (a :: k) (c :: Coverage) (b :: j).
(Site t k, LocallyFinite k, Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> Plus t q x b) -> Plus t q a b
gluePlus Cover t k a c
c forall (x :: k). Leg t k a c x -> Plus t q x b
m =
  let ls :: [SomeLeg t k a c]
ls = Cover t k a c -> [SomeLeg t k a c]
forall (a :: k) (c :: Coverage). Cover t k a c -> [SomeLeg t k a c]
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage).
Site t k =>
Cover t k a c -> [SomeLeg t k a c]
legs Cover t k a c
c
  in (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (q c d))
-> Plus t q a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j)
       (p :: j +-> k) (t :: Coverage).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Maybe (p c d))
-> Plus t p a b
Plus \c ~> a
g b ~> d
h ->
       -- matching @Plus f@ is what brings the leg's source into scope, as 'plusTable' also relies on
       c ~> a
g (c ~> a) -> ((Ob c, Ob a) => Maybe (q c d)) -> Maybe (q c d)
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// [q c d] -> Maybe (q c d)
forall (a :: Coverage). [a] -> Maybe a
listToMaybe ((SomeLeg t k a c -> Maybe (q c d)) -> [SomeLeg t k a c] -> [q c d]
forall (a :: Coverage) (b :: Coverage).
(a -> Maybe b) -> [a] -> [b]
mapMaybe (\(SomeLeg Leg t k a c x
l) -> case Leg t k a c x -> Plus t q x b
forall (x :: k). Leg t k a c x -> Plus t q x b
m Leg t k a c x
l of Plus forall (c :: k) (d :: j). (c ~> x) -> (b ~> d) -> Maybe (q c d)
f -> (c ~> a) -> (x ~> a) -> Maybe (c ~> x)
forall {k :: Coverage} (x :: k) (y :: k) (a :: k).
(LocallyFinite k, Ob x, Ob y, Ob a) =>
(x ~> a) -> (y ~> a) -> Maybe (x ~> y)
factorThrough c ~> a
g (Leg t k a c x -> x ~> a
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l) Maybe (c ~> x) -> ((c ~> x) -> Maybe (q c d)) -> Maybe (q c d)
forall (a :: Coverage) (b :: Coverage).
Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: Coverage -> Coverage) (a :: Coverage) (b :: Coverage).
Monad m =>
m a -> (a -> m b) -> m b
P.>>= \c ~> x
u -> (c ~> x) -> (b ~> d) -> Maybe (q c d)
forall (c :: k) (d :: j). (c ~> x) -> (b ~> d) -> Maybe (q c d)
f c ~> x
u b ~> d
h) [SomeLeg t k a c]
ls)

-- | Sheafification lands in the sheaves (@'isSheaf' \@t \@('Sheafify' t p)@ confirms it by
-- enumeration), so a 'Sheafify' can be used wherever a 'Sheaf' is asked for.
--
-- 'gluePlus' is lawful only on a /separated/ @q@, which @'Plus' t p@ always is, hence the double
-- plus in the head. The also true @'Sheaf' t p => 'Sheaf' t ('Plus' t p)@ would overlap this
-- instance with neither more specific.
instance (Site t k, LocallyFinite k, CategoryOf j) => Sheaf t (Sheafify t (p :: j +-> k)) where
  glue :: forall (a :: k) (c :: Coverage) (b :: j).
(Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> Sheafify t p x b)
-> Sheafify t p a b
glue = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (q :: j +-> k) (a :: k) (c :: Coverage) (b :: j).
(Site t k, LocallyFinite k, Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> Plus t q x b) -> Plus t q a b
gluePlus @t

-- | 'extendPlus' twice: a map into a sheaf extends along 'unitSheafify'.
extendSheafify
  :: forall t {j} {k} (p :: j +-> k) q
   . (HasFiniteCovers t k, Sheaf t q)
  => (p :~> q) -> Sheafify t p :~> q
extendSheafify :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Sheafify t p :~> q
extendSheafify p :~> q
n = forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Plus t p :~> q
extendPlus @t (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Plus t p :~> q
extendPlus @t p a b -> q a b
p :~> q
n)

-- * The truth values of the topos

-- | A sieve equal to its own 'closure'. These are the truth values of the sheaves for @t@, as all
-- sieves are of the presheaves. A subsheaf @s@ of @p@ sends an element @x@ to the sieve of pairs
-- @(g, h)@ with @'dimap' g h x@ in @s@. That sieve is closed: if the restrictions of @x@ along a
-- cover are in @s@, gluing puts @x@ in @s@.
--
-- It is a newtype because the object has to be nameable, and the equalizer of 'lawvereTierney'
-- and the identity on 'Omega' ('equalizeNat') binds its table existentially.
--
-- It is the classifier only when the coverage is a Grothendieck topology ('HasFiniteCovers'\'s
-- Composition law, checked by 'Proarrow.Testing.Laws.testLawvereTierney_'). Otherwise it quietly
-- computes something else, while 'leastDenseSieve' fails loudly.
--
-- __The constructor checks nothing.__ 'elements' produces only closed sieves, and 'closedSieve'
-- closes any sieve.
type ClosedSieve :: forall {j} {k}. Coverage -> j +-> k
newtype ClosedSieve t (a :: k) (b :: j) = ClosedSieve (Sieve a b)

-- | Closure commutes with 'dimap' (the Lawvere–Tierney axiom that 'lawvereTierney' packages as an
-- arrow on 'Omega'), so a restriction of a closed sieve is closed.
instance (CategoryOf j, CategoryOf k) => Profunctor (ClosedSieve t :: j +-> k) where
  dimap :: forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> ClosedSieve t a b -> ClosedSieve t c d
dimap c ~> a
l b ~> d
r (ClosedSieve Sieve a b
s) = Sieve c d -> ClosedSieve t c d
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j).
Sieve a b -> ClosedSieve t a b
ClosedSieve ((c ~> a) -> (b ~> d) -> Sieve a b -> Sieve c d
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> Sieve a b -> Sieve c d
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
l b ~> d
r Sieve a b
s)
  (Ob a, Ob b) => r
x \\ :: forall (a :: k) (b :: j) (r :: Coverage).
((Ob a, Ob b) => r) -> ClosedSieve t a b -> r
\\ ClosedSieve Sieve a b
s = r
(Ob a, Ob b) => r
x ((Ob a, Ob b) => r) -> Sieve a b -> r
forall (a :: k) (b :: j) (r :: Coverage).
((Ob a, Ob b) => r) -> Sieve a b -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ Sieve a b
s

-- | The closed sieves at a pair of objects, in the order 'Sieve' lists them.
closedSieves
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b)
  => [ClosedSieve t a b]
closedSieves :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[ClosedSieve t a b]
closedSieves = [Sieve a b -> ClosedSieve t a b
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j).
Sieve a b -> ClosedSieve t a b
ClosedSieve Sieve a b
s | Sieve a b
s <- forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Sieve :: j +-> k) @a @b, forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Bool
isClosed @t Sieve a b
s]

instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => Finitary (ClosedSieve t :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [ClosedSieve t a b] -> Natural
forall (i :: Coverage) (a :: Coverage). Num i => [a] -> i
genericLength (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[ClosedSieve t a b]
closedSieves @t @a @b)

  -- the closed ones are found by filtering every sieve, so that walk is bound outside the lambda
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
ClosedSieve t a b -> Natural
toIndex @a @b =
    let tables :: [[Bool]]
tables = (ClosedSieve t a b -> [Bool]) -> [ClosedSieve t a b] -> [[Bool]]
forall (a :: Coverage) (b :: Coverage). (a -> b) -> [a] -> [b]
P.map (\(ClosedSieve Sieve a b
s) -> Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s) (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[ClosedSieve t a b]
closedSieves @t @a @b)
    in \(ClosedSieve Sieve a b
s) -> [Char] -> [[Bool]] -> [Bool] -> Natural
forall (v :: Coverage). Eq v => [Char] -> [[v]] -> [v] -> Natural
familyIndex [Char]
"toIndex: not a closed sieve" [[Bool]]
tables (Sieve a b -> [Bool]
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable Sieve a b
s)
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> ClosedSieve t a b
fromIndex @a @b = [ClosedSieve t a b] -> Natural -> ClosedSieve t a b
forall (i :: Coverage) (a :: Coverage). Integral i => [a] -> i -> a
genericIndex (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[ClosedSieve t a b]
closedSieves @t @a @b)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [ClosedSieve t a b]
elements @a @b = forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[ClosedSieve t a b]
closedSieves @t @a @b

-- | Whether an arrow pair is in a closed sieve.
inClosedSieve :: forall {j} {k} t (a :: k) (b :: j) c d. ClosedSieve t a b -> c ~> a -> b ~> d -> P.Bool
inClosedSieve :: forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j) (c :: k) (d :: j).
ClosedSieve t a b -> (c ~> a) -> (b ~> d) -> Bool
inClosedSieve (ClosedSieve (Sieve forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s)) c ~> a
g b ~> d
h = (c ~> a) -> (b ~> d) -> Bool
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s c ~> a
g b ~> d
h

-- | The classifier is a sheaf, with gluing built directly: the glued sieve contains @g@ iff every
-- leg of the cover pulled back along @g@ is in the sieve of the family member it factors through.
-- Anything in the glued sieve passes this test, since sieves are closed under precomposition, and
-- anything that passes is in it, since the sieves are /closed/.
instance (StableSite t k, CategoryOf j) => Sheaf t (ClosedSieve t :: j +-> k) where
  glue :: forall (a :: k) (c :: Coverage) (b :: j).
(Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> ClosedSieve t x b)
-> ClosedSieve t a b
glue Cover t k a c
c forall (x :: k). Leg t k a c x -> ClosedSieve t x b
m =
    Sieve a b -> ClosedSieve t a b
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j).
Sieve a b -> ClosedSieve t a b
ClosedSieve
      ( (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k :: Coverage} {j :: Coverage} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
g b ~> d
h ->
          c ~> a
g (c ~> a) -> ((Ob c, Ob a) => Bool) -> Bool
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// case Cover t k a c -> (c ~> a) -> PulledBack t k a c c
forall (b :: k) (a :: k) (c :: Coverage).
Ob b =>
Cover t k a c -> (b ~> a) -> PulledBack t k a c b
forall (t :: Coverage) (k :: Coverage) (b :: k) (a :: k)
       (c :: Coverage).
(StableSite t k, Ob b) =>
Cover t k a c -> (b ~> a) -> PulledBack t k a c b
pullbackCover Cover t k a c
c c ~> a
g of
            AlreadyFactors (Factors Leg t k a c y
l c ~> y
u) -> ClosedSieve t y b -> (c ~> y) -> (b ~> d) -> Bool
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j) (c :: k) (d :: j).
ClosedSieve t a b -> (c ~> a) -> (b ~> d) -> Bool
inClosedSieve (Leg t k a c y -> ClosedSieve t y b
forall (x :: k). Leg t k a c x -> ClosedSieve t x b
m Leg t k a c y
l) c ~> y
u b ~> d
h
            PulledBack Cover t k c c'
c' forall (x :: k). Leg t k c c' x -> Factors t k a c x
factorsThroughLeg ->
              (SomeLeg t k c c' -> Bool) -> [SomeLeg t k c c'] -> Bool
forall (t :: Coverage -> Coverage) (a :: Coverage).
Foldable t =>
(a -> Bool) -> t a -> Bool
P.all (\(SomeLeg Leg t k c c' x
l') -> case Leg t k c c' x -> Factors t k a c x
forall (x :: k). Leg t k c c' x -> Factors t k a c x
factorsThroughLeg Leg t k c c' x
l' of Factors Leg t k a c y
l x ~> y
u -> ClosedSieve t y b -> (x ~> y) -> (b ~> d) -> Bool
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j) (c :: k) (d :: j).
ClosedSieve t a b -> (c ~> a) -> (b ~> d) -> Bool
inClosedSieve (Leg t k a c y -> ClosedSieve t y b
forall (x :: k). Leg t k a c x -> ClosedSieve t x b
m Leg t k a c y
l) x ~> y
u b ~> d
h) (Cover t k c c' -> [SomeLeg t k c c']
forall (a :: k) (c :: Coverage). Cover t k a c -> [SomeLeg t k a c]
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage).
Site t k =>
Cover t k a c -> [SomeLeg t k a c]
legs Cover t k c c'
c')
      )

-- | Any sieve as a closed one: 'lawvereTierney' corestricted to its fixed points, which is the
-- reflection of the presheaf classifier onto the sheaf one.
closedSieve
  :: forall t {j} {k} (a :: k) (b :: j)
   . (HasFiniteCovers t k, FiniteCat j, FiniteCat k)
  => Sieve a b
  -> ClosedSieve t a b
closedSieve :: forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> ClosedSieve t a b
closedSieve Sieve a b
s = Sieve a b -> ClosedSieve t a b
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j).
Sieve a b -> ClosedSieve t a b
ClosedSieve (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> Sieve a b
closure @t Sieve a b
s)

-- * The category of sheaves

-- | The full subcategory of @'FINITARY' j k@ on the sheaves for @t@. Finite limits and the
-- exponential are 'FINITARY'\'s, and are sheaves by the closure instances ('TerminalProfunctor',
-- ':*:', 'Proarrow.Category.Enriched.Finitary.Topos.Reindex', ':~>:'). Colimits are 'FINITARY'\'s
-- followed by 'Sheafify', since a quotient of sheaves need not be a sheaf, and their universal
-- property uses 'factorLocally', since an epi of sheaves is onto only locally.
-- @'Proarrow.Category.Topos.Omega'@ is 'ClosedSieve'.
type SHEAVES :: Coverage -> Kind -> Kind -> Kind
type SHEAVES t j k = SUBCAT ((Finitary :&&: Sheaf t) :: OB (j +-> k))

-- | A sheaf as an object of 'SHEAVES', as 'Proarrow.Category.Enriched.Finitary.Topos.FIN' names
-- an object of 'FINITARY'.
type SHF :: forall {j} {k}. forall (t :: Coverage) -> (j +-> k) -> SHEAVES t j k
type SHF t (p :: j +-> k) = SUB p :: SHEAVES t j k

-- | Equalizers as in 'FINITARY', by 'equalizeNat'; the result is a sheaf for every coverage, which
-- 'Proarrow.Testing.Laws.testEqualizersAreSheaves' checks by enumeration.
instance (Site t k, Enumerable j, Enumerable k) => HasEqualizers (SHEAVES t j k) where
  equalize :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k) (r :: Coverage).
(a ~> b)
-> (a ~> b) -> (forall (e :: SHEAVES t j k). (e ~> a) -> r) -> r
equalize (Sub (Prof a1 :~> b1
f)) (Sub (Prof a1 :~> b1
g)) forall (e :: SHEAVES t j k). (e ~> a) -> r
k = (a1 :~> b1)
-> (a1 :~> b1)
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    (Reindex Subobject a1 fs :~> a1) -> r)
-> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k) (r :: Coverage).
(Finitary p, Finitary q, Enumerable j, Enumerable k) =>
(p :~> q)
-> (p :~> q)
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    (Reindex Subobject p fs :~> p) -> r)
-> r
equalizeNat a1 a b -> b1 a b
a1 :~> b1
f a1 a b -> b1 a b
a1 :~> b1
g \Reindex Subobject a1 fs :~> a1
incl -> (SUB (Reindex Subobject a1 fs) ~> a) -> r
forall (e :: SHEAVES t j k). (e ~> a) -> r
k (Prof (Reindex Subobject a1 fs) a1
-> Sub Prof (SUB (Reindex Subobject a1 fs)) (SUB a1)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((Reindex Subobject a1 fs :~> a1)
-> Prof (Reindex Subobject a1 fs) a1
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof Reindex Subobject a1 fs a b -> a1 a b
Reindex Subobject a1 fs :~> a1
incl))
  factorEqualizer :: forall (e :: SHEAVES t j k) (x :: SHEAVES t j k)
       (e' :: SHEAVES t j k).
(e ~> x) -> (e' ~> x) -> e' ~> e
factorEqualizer (Sub (Prof a1 :~> b1
incl)) (Sub (Prof a1 :~> b1
h)) = Prof a1 a1 -> Sub Prof (SUB a1) (SUB a1)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((a1 :~> a1) -> Prof a1 a1
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof ((a1 :~> b1) -> (a1 :~> b1) -> a1 :~> a1
forall {j :: Coverage} {k :: Coverage} (e :: j +-> k)
       (x :: j +-> k) (e' :: j +-> k).
(Finitary e, Finitary x, Profunctor e') =>
(e :~> x) -> (e' :~> x) -> e' :~> e
factorThroughEqualizer a1 a b -> b1 a b
a1 :~> b1
incl a1 a b -> b1 a b
a1 :~> b1
h))

instance (Site t k, Enumerable j, Enumerable k) => HasPullbacks (SHEAVES t j k)

-- | Colimits are the presheaf colimits, sheafified: take the 'FINITARY' colimit, follow its cocone
-- with 'unitSheafify', and get the universal property from 'extendSheafify'. This works because
-- sheafification is a left adjoint.
--
-- The initial sheaf need not be the initial presheaf. 'Proarrow.Category.Sheaf.Joins' covers the
-- bottom of a lattice by the empty family, so every sheaf has one section there.
instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasInitialObject (SHEAVES t j k) where
  type InitialObject @(SHEAVES t j k) = SUB (Sheafify t InitialProfunctor)
  initiate :: forall (a :: SHEAVES t j k). Ob a => InitialObject ~> a
initiate @(SUB q) = case forall (k :: Coverage) (a :: k).
(HasInitialObject k, Ob a) =>
InitialObject ~> a
initiate @(j +-> k) @q of Prof InitialProfunctor :~> UN SUB a
n -> Prof (Sheafify t InitialProfunctor) (UN SUB a)
-> Sub Prof (SUB (Sheafify t InitialProfunctor)) (SUB (UN SUB a))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((Sheafify t InitialProfunctor :~> UN SUB a)
-> Prof (Sheafify t InitialProfunctor) (UN SUB a)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Sheafify t p :~> q
extendSheafify @t InitialProfunctor a b -> UN SUB a a b
InitialProfunctor :~> UN SUB a
n))

instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasBinaryCoproducts (SHEAVES t j k) where
  type (||) @(SHEAVES t j k) a b = SUB (Sheafify t (UN SUB a :+: UN SUB b))
  withObCoprod :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k) (r :: Coverage).
(Ob a, Ob b) =>
(Ob (a || b) => r) -> r
withObCoprod Ob (a || b) => r
r = r
Ob (a || b) => r
r
  lft :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k).
(Ob a, Ob b) =>
a ~> (a || b)
lft = Prof (UN SUB a) (Sheafify t (UN SUB a :+: UN SUB b))
-> Sub
     Prof (SUB (UN SUB a)) (SUB (Sheafify t (UN SUB a :+: UN SUB b)))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((UN SUB a :~> Sheafify t (UN SUB a :+: UN SUB b))
-> Prof (UN SUB a) (Sheafify t (UN SUB a :+: UN SUB b))
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \UN SUB a a b
x -> forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify @t (UN SUB a a b -> (:+:) (UN SUB a) (UN SUB b) a b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (q :: j +-> k).
p a b -> (:+:) p q a b
InjL UN SUB a a b
x))
  rgt :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k).
(Ob a, Ob b) =>
b ~> (a || b)
rgt = Prof (UN SUB b) (Sheafify t (UN SUB a :+: UN SUB b))
-> Sub
     Prof (SUB (UN SUB b)) (SUB (Sheafify t (UN SUB a :+: UN SUB b)))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((UN SUB b :~> Sheafify t (UN SUB a :+: UN SUB b))
-> Prof (UN SUB b) (Sheafify t (UN SUB a :+: UN SUB b))
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \UN SUB b a b
y -> forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify @t (UN SUB b a b -> (:+:) (UN SUB a) (UN SUB b) a b
forall {j :: Coverage} {k :: Coverage} (q :: j +-> k) (a :: k)
       (b :: j) (p :: j +-> k).
q a b -> (:+:) p q a b
InjR UN SUB b a b
y))
  Sub (Prof a1 :~> b1
f) ||| :: forall (x :: SHEAVES t j k) (a :: SHEAVES t j k)
       (y :: SHEAVES t j k).
(x ~> a) -> (y ~> a) -> (x || y) ~> a
||| Sub (Prof a1 :~> b1
g) = Prof (Sheafify t (a1 :+: a1)) b1
-> Sub Prof (SUB (Sheafify t (a1 :+: a1))) (SUB b1)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((Sheafify t (a1 :+: a1) :~> b1) -> Prof (Sheafify t (a1 :+: a1)) b1
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (q :: j +-> k).
(HasFiniteCovers t k, Sheaf t q) =>
(p :~> q) -> Sheafify t p :~> q
extendSheafify @t \case InjL a1 a b
x -> a1 a b -> b1 a b
a1 :~> b1
f a1 a b
x; InjR a1 a b
y -> a1 a b -> b1 a b
a1 :~> b1
g a1 a b
y))

-- | The quotient a coequalizer takes is 'coequalizeNat'\'s, sheafified. Its projection is epi in
-- the sheaves but need not be onto (the sheafification unit is not), so 'factorCoequalizer' is not
-- 'FINITARY'\'s. It descends, by 'factorThroughLocalEpi'.
instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasCoequalizers (SHEAVES t j k) where
  coequalize :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k) (r :: Coverage).
(a ~> b)
-> (a ~> b) -> (forall (c :: SHEAVES t j k). (b ~> c) -> r) -> r
coequalize (Sub (Prof @_ @q a1 :~> b1
f)) (Sub (Prof a1 :~> b1
g)) forall (c :: SHEAVES t j k). (b ~> c) -> r
k =
    (a1 :~> b1)
-> (a1 :~> b1)
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    (b1 :~> Reindex Quotient b1 fs) -> r)
-> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k) (r :: Coverage).
(Finitary p, Finitary q, Enumerable j, Enumerable k) =>
(p :~> q)
-> (p :~> q)
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    (q :~> Reindex Quotient q fs) -> r)
-> r
coequalizeNat a1 a b -> b1 a b
a1 :~> b1
f a1 a b -> b1 a b
a1 :~> b1
g \ @fs b1 :~> Reindex Quotient b1 fs
proj ->
      forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (r :: Coverage).
(Sheaf t p, Finitary p, FiniteCat j, FiniteCat k) =>
(forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
 (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
 (p :~> tab) -> (tab :~> p) -> r)
-> r
withSheafTables @t @(Sheafify t (Reindex Quotient q fs))
        \Sheafify t (Reindex Quotient b1 fs) :~> tab
toTab tab :~> Sheafify t (Reindex Quotient b1 fs)
_ -> (b ~> SUB (Tabulated t lm rm)) -> r
forall (c :: SHEAVES t j k). (b ~> c) -> r
k (Prof b1 (Tabulated t lm rm)
-> Sub Prof (SUB b1) (SUB (Tabulated t lm rm))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((b1 :~> Tabulated t lm rm) -> Prof b1 (Tabulated t lm rm)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \b1 a b
x -> Sheafify t (Reindex Quotient b1 fs) a b -> tab a b
Sheafify t (Reindex Quotient b1 fs) :~> tab
toTab (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify @t (b1 a b -> Reindex Quotient b1 fs a b
b1 :~> Reindex Quotient b1 fs
proj b1 a b
x))))
  factorCoequalizer :: forall (c :: SHEAVES t j k) (x :: SHEAVES t j k)
       (c' :: SHEAVES t j k).
(x ~> c) -> (x ~> c') -> c ~> c'
factorCoequalizer (Sub (Prof a1 :~> b1
proj)) (Sub (Prof a1 :~> b1
h)) = Prof b1 b1 -> Sub Prof (SUB b1) (SUB b1)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((b1 :~> b1) -> Prof b1 b1
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (c :: j +-> k) (x :: j +-> k) (c' :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Finitary c, Finitary x,
 Sheaf t c') =>
(x :~> c) -> (x :~> c') -> c :~> c'
factorThroughLocalEpi @t a1 a b -> b1 a b
a1 :~> b1
proj a1 a b -> b1 a b
a1 :~> b1
h))

-- | Not the default coproduct-then-coequalizer, which would sheafify the coproduct and then
-- sheafify the quotient of that. Each 'Sheafify' pays for the one under it, since the plus
-- construction re-runs on every 'toIndex'. Taking both steps in 'FINITARY' and sheafifying once
-- at the end gives the same object, since sheafification is a left adjoint and preserves the
-- pushout, and it avoids stacking one plus construction on another.
instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasPushouts (SHEAVES t j k) where
  pushout :: forall (o :: SHEAVES t j k) (a :: SHEAVES t j k)
       (b :: SHEAVES t j k) (r :: Coverage).
(o ~> a)
-> (o ~> b)
-> (forall (p :: SHEAVES t j k). (a ~> p) -> (b ~> p) -> r)
-> r
pushout (Sub (Prof @_ @a a1 :~> b1
f)) (Sub (Prof @_ @b a1 :~> b1
g)) forall (p :: SHEAVES t j k). (a ~> p) -> (b ~> p) -> r
k =
    (a1 :~> (b1 :+: b1))
-> (a1 :~> (b1 :+: b1))
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    ((b1 :+: b1) :~> Reindex Quotient (b1 :+: b1) fs) -> r)
-> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k) (r :: Coverage).
(Finitary p, Finitary q, Enumerable j, Enumerable k) =>
(p :~> q)
-> (p :~> q)
-> (forall (fs :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) fs =>
    (q :~> Reindex Quotient q fs) -> r)
-> r
coequalizeNat (\a1 a b
x -> b1 a b -> (:+:) b1 b1 a b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (q :: j +-> k).
p a b -> (:+:) p q a b
InjL (a1 a b -> b1 a b
a1 :~> b1
f a1 a b
x)) (\a1 a b
x -> b1 a b -> (:+:) b1 b1 a b
forall {j :: Coverage} {k :: Coverage} (q :: j +-> k) (a :: k)
       (b :: j) (p :: j +-> k).
q a b -> (:+:) p q a b
InjR (a1 a b -> b1 a b
a1 :~> b1
g a1 a b
x)) \ @fs (b1 :+: b1) :~> Reindex Quotient (b1 :+: b1) fs
proj ->
      forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k) (r :: Coverage).
(Sheaf t p, Finitary p, FiniteCat j, FiniteCat k) =>
(forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
 (tab ~ Tabulated t lm rm, KnownTables j k lm rm, Sheaf t tab) =>
 (p :~> tab) -> (tab :~> p) -> r)
-> r
withSheafTables @t @(Sheafify t (Reindex Quotient (a :+: b) fs))
        \Sheafify t (Reindex Quotient (b1 :+: b1) fs) :~> tab
toTab tab :~> Sheafify t (Reindex Quotient (b1 :+: b1) fs)
_ ->
          (a ~> SUB (Tabulated t lm rm))
-> (b ~> SUB (Tabulated t lm rm)) -> r
forall (p :: SHEAVES t j k). (a ~> p) -> (b ~> p) -> r
k
            (Prof b1 (Tabulated t lm rm)
-> Sub Prof (SUB b1) (SUB (Tabulated t lm rm))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((b1 :~> Tabulated t lm rm) -> Prof b1 (Tabulated t lm rm)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \b1 a b
x -> Sheafify t (Reindex Quotient (b1 :+: b1) fs) a b -> tab a b
Sheafify t (Reindex Quotient (b1 :+: b1) fs) :~> tab
toTab (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify @t ((:+:) b1 b1 a b -> Reindex Quotient (b1 :+: b1) fs a b
(b1 :+: b1) :~> Reindex Quotient (b1 :+: b1) fs
proj (b1 a b -> (:+:) b1 b1 a b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (q :: j +-> k).
p a b -> (:+:) p q a b
InjL b1 a b
x)))))
            (Prof b1 (Tabulated t lm rm)
-> Sub Prof (SUB b1) (SUB (Tabulated t lm rm))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((b1 :~> Tabulated t lm rm) -> Prof b1 (Tabulated t lm rm)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \b1 a b
y -> Sheafify t (Reindex Quotient (b1 :+: b1) fs) a b -> tab a b
Sheafify t (Reindex Quotient (b1 :+: b1) fs) :~> tab
toTab (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (p :: j +-> k).
Profunctor p =>
p :~> Sheafify t p
unitSheafify @t ((:+:) b1 b1 a b -> Reindex Quotient (b1 :+: b1) fs a b
(b1 :+: b1) :~> Reindex Quotient (b1 :+: b1) fs
proj (b1 a b -> (:+:) b1 b1 a b
forall {j :: Coverage} {k :: Coverage} (q :: j +-> k) (a :: k)
       (b :: j) (p :: j +-> k).
q a b -> (:+:) p q a b
InjR b1 a b
y)))))
  factorPushout :: forall (a :: SHEAVES t j k) (b :: SHEAVES t j k)
       (p :: SHEAVES t j k) (q :: SHEAVES t j k).
(a ~> p) -> (b ~> p) -> (a ~> q) -> (b ~> q) -> p ~> q
factorPushout (Sub (Prof a1 :~> b1
p1)) (Sub (Prof a1 :~> b1
p2)) (Sub (Prof a1 :~> b1
k1)) (Sub (Prof a1 :~> b1
k2)) =
    Prof b1 b1 -> Sub Prof (SUB b1) (SUB b1)
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((b1 :~> b1) -> Prof b1 b1
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof (forall (t :: Coverage) {j :: Coverage} {k :: Coverage}
       (c :: j +-> k) (x :: j +-> k) (c' :: j +-> k).
(HasFiniteCovers t k, CategoryOf j, Finitary c, Finitary x,
 Sheaf t c') =>
(x :~> c) -> (x :~> c') -> c :~> c'
factorThroughLocalEpi @t (\case InjL a1 a b
x -> a1 a b -> b1 a b
a1 :~> b1
p1 a1 a b
x; InjR a1 a b
y -> a1 a b -> b1 a b
a1 :~> b1
p2 a1 a b
y) (\case InjL a1 a b
x -> a1 a b -> b1 a b
a1 :~> b1
k1 a1 a b
x; InjR a1 a b
y -> a1 a b -> b1 a b
a1 :~> b1
k2 a1 a b
y)))

-- | The image of an arrow of sheaves, by the same cokernel-pair construction as in 'FINITARY': the
-- pushout is a colimit and so sheafified, the equalizer that follows it is not.
instance (HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasEpiMonoFactorization (SHEAVES t j k)

-- | The presheaf internal hom into a sheaf is already a sheaf: a matching family of maps @p -> q@
-- over a cover glues pointwise, because the values glue in @q@. @p@ needs no condition.
--
-- The glued map, at an arrow @g@ into @a@, pulls the cover back along @g@ ('StableSite'). Each
-- pulled-back leg factors through an original leg, whose map is asked, and the answers are glued
-- in @q@. Neither @p@ nor @q@ has to be 'Finitary'. The generic
-- 'Proarrow.Category.Enriched.Finitary.Topos.glueBySearch' would be exponential in the size of @p@.
instance (StableSite t k, Sheaf t q, Profunctor p, CategoryOf j) => Sheaf t (p :~>: q :: j +-> k) where
  glue :: forall (a :: k) (c :: Coverage) (b :: j).
(Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> (:~>:) p q x b)
-> (:~>:) p q a b
glue Cover t k a c
c forall (x :: k). Leg t k a c x -> (:~>:) p q x b
m = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> p c d -> q c d)
-> (:~>:) p q a b
forall {k :: Coverage} {k1 :: Coverage} (a :: k) (b :: k1)
       (p :: k -> k1 -> Coverage) (q :: k -> k1 -> Coverage).
(Ob a, Ob b) =>
(forall (c :: k) (d :: k1). (c ~> a) -> (b ~> d) -> p c d -> q c d)
-> (:~>:) p q a b
Exp \c ~> a
g b ~> d
h p c d
x ->
    c ~> a
g (c ~> a) -> ((Ob c, Ob a) => q c d) -> q c d
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
h (b ~> d) -> ((Ob b, Ob d) => q c d) -> q c d
forall {k1 :: Coverage} {k2 :: Coverage} (p :: k1 +-> k2) (a :: k2)
       (b :: k1) (r :: Coverage).
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// case Cover t k a c -> (c ~> a) -> PulledBack t k a c c
forall (b :: k) (a :: k) (c :: Coverage).
Ob b =>
Cover t k a c -> (b ~> a) -> PulledBack t k a c b
forall (t :: Coverage) (k :: Coverage) (b :: k) (a :: k)
       (c :: Coverage).
(StableSite t k, Ob b) =>
Cover t k a c -> (b ~> a) -> PulledBack t k a c b
pullbackCover Cover t k a c
c c ~> a
g of
      AlreadyFactors (Factors Leg t k a c y
l c ~> y
u) -> case Leg t k a c y -> (:~>:) p q y b
forall (x :: k). Leg t k a c x -> (:~>:) p q x b
m Leg t k a c y
l of Exp forall (c :: k) (d :: j). (c ~> y) -> (b ~> d) -> p c d -> q c d
f -> (c ~> y) -> (b ~> d) -> p c d -> q c d
forall (c :: k) (d :: j). (c ~> y) -> (b ~> d) -> p c d -> q c d
f c ~> y
u b ~> d
h p c d
x
      PulledBack Cover t k c c'
c' forall (x :: k). Leg t k c c' x -> Factors t k a c x
factorsThroughLeg -> forall {j :: Coverage} {k :: Coverage} (t :: Coverage)
       (p :: j +-> k) (a :: k) (c :: Coverage) (b :: j).
(Sheaf t p, Ob a, Ob b) =>
Cover t k a c -> (forall (x :: k). Leg t k a c x -> p x b) -> p a b
forall (t :: Coverage) (p :: j +-> k) (a :: k) (c :: Coverage)
       (b :: j).
(Sheaf t p, Ob a, Ob b) =>
Cover t k a c -> (forall (x :: k). Leg t k a c x -> p x b) -> p a b
glue @t Cover t k c c'
c' \Leg t k c c' x
l' ->
        case Leg t k c c' x -> Factors t k a c x
forall (x :: k). Leg t k c c' x -> Factors t k a c x
factorsThroughLeg Leg t k c c' x
l' of
          Factors Leg t k a c y
l x ~> y
u -> case Leg t k a c y -> (:~>:) p q y b
forall (x :: k). Leg t k a c x -> (:~>:) p q x b
m Leg t k a c y
l of Exp forall (c :: k) (d :: j). (c ~> y) -> (b ~> d) -> p c d -> q c d
f -> (x ~> y) -> (b ~> d) -> p x d -> q x d
forall (c :: k) (d :: j). (c ~> y) -> (b ~> d) -> p c d -> q c d
f x ~> y
u b ~> d
h ((x ~> c) -> p c d -> p x d
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (c :: k)
       (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap (Leg t k c c' x -> x ~> c
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k c c' x
l') p c d
x) ((Ob x, Ob c) => q x d) -> (x ~> c) -> q x d
forall (a :: k) (b :: k) (r :: Coverage).
((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a :: k)
       (b :: j) (r :: Coverage).
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ Leg t k c c' x -> x ~> c
forall (a :: k) (c :: Coverage) (x :: k). Leg t k a c x -> x ~> a
forall (t :: Coverage) (k :: Coverage) (a :: k) (c :: Coverage)
       (x :: k).
Site t k =>
Leg t k a c x -> x ~> a
legArrow Leg t k c c' x
l'

-- | The classifier is the closed sieves, and an arrow is classified by 'FINITARY'\'s graph sieve,
-- closed. For an arrow of sheaves that sieve is already closed, since a sheaf is separated. The
-- 'closedSieve' call guards against a 'Sheaf' instance that was asserted instead of decided, which
-- would otherwise fail later in 'familyIndex' as \"not a closed sieve\".
instance (StableSite t k, HasFiniteCovers t k, FiniteCat j, FiniteCat k) => HasSubobjectClassifier (PROD (SHEAVES t j k)) where
  type Omega @(PROD (SHEAVES t j k)) = PR (SUB (ClosedSieve t))
  true :: TerminalObject ~> Omega
true = Sub Prof (SUB TerminalProfunctor) (SUB (ClosedSieve t))
-> Prod
     (Sub Prof) (PR (SUB TerminalProfunctor)) (PR (SUB (ClosedSieve t)))
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a1 :: k)
       (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (Prof TerminalProfunctor (ClosedSieve t)
-> Sub Prof (SUB TerminalProfunctor) (SUB (ClosedSieve t))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub ((TerminalProfunctor :~> ClosedSieve t)
-> Prof TerminalProfunctor (ClosedSieve t)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \TerminalProfunctor a b
TerminalProfunctor -> Sieve a b -> ClosedSieve t a b
forall {j :: Coverage} {k :: Coverage} (t :: Coverage) (a :: k)
       (b :: j).
Sieve a b -> ClosedSieve t a b
ClosedSieve Sieve a b
forall {j :: Coverage} {k :: Coverage} (a :: k) (b :: j).
(CategoryOf j, CategoryOf k, Ob a, Ob b) =>
Sieve a b
maximalSieve))
  classifyGraph :: forall (a :: PROD (SHEAVES t j k)) (b :: PROD (SHEAVES t j k)).
(a ~> b) -> (a && b) ~> Omega
classifyGraph (Prod (Sub (Prof a1 :~> b1
n))) = Sub Prof (SUB (a1 :*: b1)) (SUB (ClosedSieve t))
-> Prod
     (Sub Prof) (PR (SUB (a1 :*: b1))) (PR (SUB (ClosedSieve t)))
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k) (a1 :: k)
       (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (Prof (a1 :*: b1) (ClosedSieve t)
-> Sub Prof (SUB (a1 :*: b1)) (SUB (ClosedSieve t))
forall {k :: Coverage} (ob :: OB k) (a1 :: k) (b1 :: k)
       (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub (((a1 :*: b1) :~> ClosedSieve t) -> Prof (a1 :*: b1) (ClosedSieve t)
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof (forall (t :: Coverage) {j :: Coverage} {k :: Coverage} (a :: k)
       (b :: j).
(HasFiniteCovers t k, FiniteCat j, FiniteCat k) =>
Sieve a b -> ClosedSieve t a b
closedSieve @t (Sieve a b -> ClosedSieve t a b)
-> ((:*:) a1 b1 a b -> Sieve a b)
-> (:*:) a1 b1 a b
-> ClosedSieve t a b
forall (b :: Coverage) (c :: Coverage) (a :: Coverage).
(b -> c) -> (a -> b) -> a -> c
forall {k :: Coverage} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (a1 :~> b1) -> (a1 :*: b1) :~> Sieve
forall {j :: Coverage} {k :: Coverage} (p :: j +-> k)
       (q :: j +-> k).
(Profunctor p, Finitary q) =>
(p :~> q) -> (p :*: q) :~> Sieve
graphSieve a1 a b -> b1 a b
a1 :~> b1
n)))

-- | __The topos of sheaves.__ Finite limits and colimits, cartesian closed, a subobject
-- classifier, and image factorization, all defined above and none of them postulated.
--
-- The exponential needs 'StableSite'. A full subcategory is closed when it contains its internal
-- homs, and an internal hom is a sheaf by gluing pointwise into the codomain, which needs the
-- cover pulled back along the argument.
instance (StableSite t k, HasFiniteCovers t k, FiniteCat j, FiniteCat k) => ElementaryTopos (PROD (SHEAVES t j k))