{-# LANGUAGE AllowAmbiguousTypes #-}
-- Orphans throughout, and unavoidably: every instance here is on either 'SUBCAT' 'Finitary' (the
-- kind synonym 'FINITARY' expands to it, and both halves of that come from other modules) or on a
-- profunctor defined elsewhere. Both the class and the category it carves out have to sit below the
-- enrichment machinery; everything computed in that category needs things sitting above it.
{-# OPTIONS_GHC -Wno-orphans #-}

-- | __The topos of finitary profunctors.__ Everything built on the numbering in
-- "Proarrow.Category.Enriched.Finitary": a hom-set is an initial segment of the naturals, so a
-- subobject or a quotient of one is a table of indices, and a computation can produce such a table
-- and reify it into a fresh object. This is 'Reindex', and it gives equalizers, coequalizers,
-- pullbacks, pushouts and epi-mono factorization.
--
-- The internal hom and the subobject classifier are the same construction one level up. Both are
-- ends, enumerated by choosing a value at every point of a domain and keeping the choices that
-- commute with the action. Neither count is a formula in the sizes it is built from, since they
-- depend on how the arrows of @j@ and @k@ compose. That is why the numbering is a value.
--
-- The module ends with @'ElementaryTopos' ('PROD' ('FINITARY' j k))@. With 'PROD' the tensor is the
-- product instead of Day convolution, as it is for @j '+->' k@ itself.
module Proarrow.Category.Enriched.Finitary.Topos where

import Data.IntMap.Strict qualified as IM
import Data.Kind (Constraint, Type)
import Data.List (elemIndex, find, findIndex, genericIndex, genericLength, genericReplicate, partition, sort)
import Data.Map.Strict qualified as M
import Data.Maybe (fromMaybe)
import Data.Proxy (Proxy (..))
import Data.Type.Equality ((:~:) (..))
import Data.Type.Nat (Nat (..), SNatI, reify, snat)
import Data.Type.Nat qualified as N
import Numeric.Natural (Natural)
import Prelude (Maybe (..), ($), (==), (||), type (~))
import Prelude qualified as P

import Proarrow.Category.Enriched.Finitary
import Proarrow.Category.Enriched.Thin
  ( Entry
  , Enumerable (..)
  , Finite (..)
  , Indexed (..)
  , IndexedList
  , KnownList (..)
  )
import Proarrow.Category.Instance.Opposite (OPPOSITE (..), Op (..))
import Proarrow.Category.Instance.Prof (Prof (..))
import Proarrow.Category.Instance.Sub (SUBCAT (..), Sub (..))
import Proarrow.Category.Sheaf (Coverage, Sheaf (..), Site (..), SomeLeg (..), Trivial)
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
  ( CAT
  , CategoryOf (..)
  , Hom
  , OB
  , Profunctor (..)
  , Promonad (..)
  , UN
  , lmap
  , obj
  , rmap
  , (//)
  , type (+->)
  , type (:~>)
  )
import Proarrow.Limit.BinaryProduct (PROD (..), Prod (..))
import Proarrow.Limit.Equalizer (HasEqualizers (..))
import Proarrow.Limit.Pullback (HasPullbacks)
import Proarrow.Object (KnownListOf (..), ListOf (..), mapListOf)
import Proarrow.Profunctor.Instance.Composition ((:.:) (..))
import Proarrow.Profunctor.Instance.Coproduct ((:+:) (..))
import Proarrow.Profunctor.Instance.Exponential ((:~>:) (..))
import Proarrow.Profunctor.Instance.Initial (InitialProfunctor)
import Proarrow.Profunctor.Instance.Product ((:*:) (..))
import Proarrow.Profunctor.Instance.Ran (Ran (..))
import Proarrow.Profunctor.Instance.Rift (Rift (..))
import Proarrow.Profunctor.Instance.Sieve (Sieve (..), maximalSieve)
import Proarrow.Profunctor.Instance.Terminal (TerminalProfunctor (..))
import Proarrow.Profunctor.Instance.Yoneda (Yo (..))

-- | The subcategory of finitary profunctors, as "Proarrow.Category.Instance.Rep" does for
-- representable ones.
type FINITARY j k = SUBCAT (Finitary :: (j +-> k) -> Constraint)

type FIN (p :: j +-> k) = SUB p :: FINITARY j k

-- The finite products of 'FINITARY' (and of the sheaves) are the generic ones for a full
-- subcategory in "Proarrow.Category.Instance.Sub", pointwise under 'Sub'; the predicate only has to
-- hold of ':*:' and 'TerminalProfunctor'. The coproducts are defined here, from ':+:' and
-- 'InitialProfunctor': a full subcategory has no generic coproducts, since the sheaves, a full
-- subcategory too, have sheafified ones.

instance (CategoryOf j, CategoryOf k) => HasInitialObject (FINITARY j k) where
  type InitialObject = FIN InitialProfunctor
  initiate :: forall (a :: FINITARY j k). Ob a => InitialObject ~> a
initiate = Prof InitialProfunctor (UN SUB a)
-> Sub Prof (FIN InitialProfunctor) (SUB (UN SUB a))
forall {k} (ob :: OB k) (a1 :: k) (b1 :: k) (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub InitialObject ~> UN SUB a
Prof InitialProfunctor (UN SUB a)
forall k (a :: k). (HasInitialObject k, Ob a) => InitialObject ~> a
forall (a :: k -> j -> Type). Ob a => InitialObject ~> a
initiate

instance (CategoryOf j, CategoryOf k) => HasBinaryCoproducts (FINITARY j k) where
  type a || b = SUB (UN SUB a :+: UN SUB b)
  withObCoprod :: forall (a :: FINITARY j k) (b :: FINITARY j k) r.
(Ob a, Ob b) =>
(Ob (a || b) => r) -> r
withObCoprod Ob (a || b) => r
r = r
Ob (a || b) => r
r
  lft :: forall (a :: FINITARY j k) (b :: FINITARY j k).
(Ob a, Ob b) =>
a ~> (a || b)
lft @(SUB p) @(SUB q) = Prof (UN SUB a) (UN SUB a :+: UN SUB b)
-> Sub Prof (SUB (UN SUB a)) (SUB (UN SUB a :+: UN SUB b))
forall {k} (ob :: OB k) (a1 :: k) (b1 :: k) (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub (forall k (a :: k) (b :: k).
(HasBinaryCoproducts k, Ob a, Ob b) =>
a ~> (a || b)
lft @(j +-> k) @p @q)
  rgt :: forall (a :: FINITARY j k) (b :: FINITARY j k).
(Ob a, Ob b) =>
b ~> (a || b)
rgt @(SUB p) @(SUB q) = Prof (UN SUB b) (UN SUB a :+: UN SUB b)
-> Sub Prof (SUB (UN SUB b)) (SUB (UN SUB a :+: UN SUB b))
forall {k} (ob :: OB k) (a1 :: k) (b1 :: k) (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub (forall k (a :: k) (b :: k).
(HasBinaryCoproducts k, Ob a, Ob b) =>
b ~> (a || b)
rgt @(j +-> k) @p @q)
  Sub Prof a1 b1
l ||| :: forall (x :: FINITARY j k) (a :: FINITARY j k) (y :: FINITARY j k).
(x ~> a) -> (y ~> a) -> (x || y) ~> a
||| Sub Prof a1 b1
r = Prof (a1 :+: a1) b1 -> Sub Prof (SUB (a1 :+: a1)) (SUB b1)
forall {k} (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
Prof a1 b1
l (a1 ~> b1) -> (a1 ~> b1) -> (a1 || a1) ~> b1
forall k (x :: k) (a :: k) (y :: k).
HasBinaryCoproducts k =>
(x ~> a) -> (y ~> a) -> (x || y) ~> a
forall (x :: k -> j -> Type) (a :: k -> j -> Type)
       (y :: k -> j -> Type).
(x ~> a) -> (y ~> a) -> (x || y) ~> a
||| a1 ~> b1
Prof a1 b1
r)

-- * Tables of fibres

-- | A type-level list of naturals, reflected.
type KnownNats :: [Nat] -> Constraint
type KnownNats = KnownListOf SNatI

natsVal :: forall ns. (KnownNats ns) => [Natural]
natsVal :: forall (ns :: [Nat]). KnownNats ns => [Natural]
natsVal = forall {k} (c :: OB k) (xs :: [k]) r.
(forall (x :: k). c x => r) -> ListOf c xs -> [r]
forall (c :: OB Nat) (xs :: [Nat]) r.
(forall (x :: Nat). c x => r) -> ListOf c xs -> [r]
mapListOf @SNatI (\ @n -> SNat x -> Natural
forall (n :: Nat). SNat n -> Natural
N.snatToNatural (forall (n :: Nat). SNatI n => SNat n
snat @n)) (forall {k} (c :: OB k) (xs :: [k]). KnownListOf c xs => ListOf c xs
forall (c :: OB Nat) (xs :: [Nat]). KnownListOf c xs => ListOf c xs
listOf @SNatI @ns)

-- | A type-level list of lists of naturals, reflected: the fibres of a partial surjection out of
-- one hom-set.
type KnownFibres :: [[Nat]] -> Constraint
type KnownFibres = KnownListOf KnownNats

fibresVal :: forall fs. (KnownFibres fs) => [[Natural]]
fibresVal :: forall (fs :: [[Nat]]). KnownFibres fs => [[Natural]]
fibresVal = forall {k} (c :: OB k) (xs :: [k]) r.
(forall (x :: k). c x => r) -> ListOf c xs -> [r]
forall (c :: OB [Nat]) (xs :: [[Nat]]) r.
(forall (x :: [Nat]). c x => r) -> ListOf c xs -> [r]
mapListOf @KnownNats (\ @f -> forall (ns :: [Nat]). KnownNats ns => [Natural]
natsVal @f) (forall {k} (c :: OB k) (xs :: [k]). KnownListOf c xs => ListOf c xs
forall (c :: OB [Nat]) (xs :: [[Nat]]).
KnownListOf c xs =>
ListOf c xs
listOf @KnownNats @fs)

-- | Reify a list of lists of naturals.
fibres :: forall r. [[Natural]] -> (forall fs. (KnownFibres fs) => r) -> r
fibres :: forall r.
[[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r) -> r
fibres [] forall (fs :: [[Nat]]). KnownFibres fs => r
k = forall (fs :: [[Nat]]). KnownFibres fs => r
k @'[]
fibres ([Natural]
f : [[Natural]]
fs) forall (fs :: [[Nat]]). KnownFibres fs => r
k = [Natural] -> (forall (ns :: [Nat]). KnownNats ns => r) -> r
forall r'.
[Natural] -> (forall (ns :: [Nat]). KnownNats ns => r') -> r'
nats [Natural]
f \ @f' -> [[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r) -> r
forall r.
[[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r) -> r
fibres [[Natural]]
fs \ @fs' -> forall (fs :: [[Nat]]). KnownFibres fs => r
k @(f' ': fs')
  where
    nats :: forall r'. [Natural] -> (forall ns. (KnownNats ns) => r') -> r'
    nats :: forall r'.
[Natural] -> (forall (ns :: [Nat]). KnownNats ns => r') -> r'
nats [] forall (ns :: [Nat]). KnownNats ns => r'
k' = forall (ns :: [Nat]). KnownNats ns => r'
k' @'[]
    nats (Natural
n : [Natural]
ns) forall (ns :: [Nat]). KnownNats ns => r'
k' = Nat -> (forall (n :: Nat). SNatI n => Proxy n -> r') -> r'
forall r. Nat -> (forall (n :: Nat). SNatI n => Proxy n -> r) -> r
reify (Natural -> Nat
N.fromNatural Natural
n) \(Proxy n
_ :: Proxy n) -> [Natural] -> (forall (ns :: [Nat]). KnownNats ns => r') -> r'
forall r'.
[Natural] -> (forall (ns :: [Nat]). KnownNats ns => r') -> r'
nats [Natural]
ns \ @ns' -> forall (ns :: [Nat]). KnownNats ns => r'
k' @(n ': ns')

-- | A table: a row for each object of @k@, and in each row the fibres at each object of @j@.
type KnownTable bs as t = KnownList (KnownList KnownFibres bs) as t

-- | Build a table by visiting every pair of objects, reifying each cell.
buildTable
  :: forall j k r
   . (Enumerable j, Enumerable k)
  => (forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
  -> (forall (t :: [[[[Nat]]]]). (KnownTable (Objects j) (Objects k) t) => r)
  -> r
buildTable :: forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]]
cell = IndexedList (Objects k)
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
forall (as :: [k]) r'.
IndexedList as
-> (forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r')
-> r'
rows (forall k. Finite k => IndexedList (Objects k)
finite @k)
  where
    rows :: forall (as :: [k]) r'. IndexedList as -> (forall t. (KnownTable (Objects j) as t) => r') -> r'
    rows :: forall (as :: [k]) r'.
IndexedList as
-> (forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r')
-> r'
rows ListOf KnownIndex as
Nil forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r'
k' = forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r'
k' @'[]
    rows (Cons @a ListOf KnownIndex xs1
as) forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r'
k' = forall k (a :: k) r.
(Enumerable k, KnownIndex a) =>
(Ob a => r) -> r
withOb @k @a (forall (a :: k) (bs :: [j]) r'.
Ob a =>
IndexedList bs
-> (forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r')
-> r'
row @a (forall k. Finite k => IndexedList (Objects k)
finite @j) \ @r0 -> ListOf KnownIndex xs1
-> (forall (t :: [[[[Nat]]]]). KnownTable (Objects j) xs1 t => r')
-> r'
forall (as :: [k]) r'.
IndexedList as
-> (forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r')
-> r'
rows ListOf KnownIndex xs1
as \ @t -> forall (t :: [[[[Nat]]]]). KnownTable (Objects j) as t => r'
k' @(r0 ': t))
    row
      :: forall (a :: k) (bs :: [j]) r'. (Ob a) => IndexedList bs -> (forall r0. (KnownList KnownFibres bs r0) => r') -> r'
    row :: forall (a :: k) (bs :: [j]) r'.
Ob a =>
IndexedList bs
-> (forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r')
-> r'
row ListOf KnownIndex bs
Nil forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r'
k' = forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r'
k' @'[]
    row (Cons @b ListOf KnownIndex xs1
bs) forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r'
k' = forall k (a :: k) r.
(Enumerable k, KnownIndex a) =>
(Ob a => r) -> r
withOb @j @b ([[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r') -> r'
forall r.
[[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r) -> r
fibres (forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]]
cell @a @b) \ @fs -> forall (a :: k) (bs :: [j]) r'.
Ob a =>
IndexedList bs
-> (forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r')
-> r'
row @a ListOf KnownIndex xs1
bs \ @r0 -> forall (r0 :: [[[Nat]]]). KnownList KnownFibres bs r0 => r'
k' @(fs ': r0))

-- * Reindexing along a table of fibres

-- | What a table of fibres does to the profunctor it relabels. The relabelling is the same either
-- way. What differs is what may be concluded from it, which is why this is in the type at all (see
-- the 'Sheaf' instance below, which is for 'Subobject' alone).
--
-- ['Subobject'] singleton fibres: the elements kept, renumbered. What 'withSubobject' and
--   'equalizeNat' build.
--
-- ['Quotient'] a partition: one index per class of a congruence. What 'coequalize' builds.
type Retabulation :: Type
type data Retabulation = Subobject | Quotient

-- | @p@ relabelled, at each pair of objects, along a partial surjection onto an initial segment of
-- the naturals, given by its fibres: index @i@ of the new hom-set stands for the elements of @p@ in
-- the @i@-th fibre. Well behaved when and only when the fibres are respected by @p@'s 'dimap', as
-- they are for the tables 'equalize' and 'coequalize' build. 'dimap' delegates to @p@ and relies on
-- it.
type Reindex :: forall {j} {k}. Retabulation -> (j +-> k) -> [[[[Nat]]]] -> j +-> k
newtype Reindex r p fs a b = Reindex (p a b)

type Cell fs (a :: k) (b :: j) = Entry (Entry fs (Index a)) (Index b)

instance (Profunctor p) => Profunctor (Reindex r p fs) where
  dimap :: forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> Reindex r p fs a b -> Reindex r p fs c d
dimap c ~> a
l b ~> d
r (Reindex p a b
x) = p c d -> Reindex r p fs c d
forall {j} {k} (r :: Retabulation) (p :: j +-> k)
       (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
p a b -> Reindex r p fs a b
Reindex ((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} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
l b ~> d
r p a b
x)
  (Ob a, Ob b) => r
r \\ :: forall (a :: k) (b :: j) r.
((Ob a, Ob b) => r) -> Reindex r p fs a b -> r
\\ Reindex p a b
x = r
(Ob a, Ob b) => r
r ((Ob a, Ob b) => r) -> p a b -> r
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a b
x

-- | The fibres at a pair of objects, found by walking the table to the objects' positions.
cellVal
  :: forall {j} {k} fs (a :: k) (b :: j)
   . (Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs, Ob a, Ob b)
  => [[Natural]]
cellVal :: forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal =
  forall k (a :: k) r.
(Enumerable k, Ob a) =>
(KnownIndex a => r) -> r
withIndex @k @a ((KnownIndex a => [[Natural]]) -> [[Natural]])
-> (KnownIndex a => [[Natural]]) -> [[Natural]]
forall a b. (a -> b) -> a -> b
$
    forall k (a :: k) r.
(Enumerable k, Ob a) =>
(KnownIndex a => r) -> r
withIndex @j @b ((KnownIndex b => [[Natural]]) -> [[Natural]])
-> (KnownIndex b => [[Natural]]) -> [[Natural]]
forall a b. (a -> b) -> a -> b
$
      forall k (i :: Nat) r.
Finite k =>
SNat i -> ((Lookup (Objects k) i ~ At k i) => r) -> r
withAtLookup @k (forall (n :: Nat). SNatI n => SNat n
snat @(Index a)) (((Lookup (Objects k) (Index a) ~ At k (Index a)) => [[Natural]])
 -> [[Natural]])
-> ((Lookup (Objects k) (Index a) ~ At k (Index a)) => [[Natural]])
-> [[Natural]]
forall a b. (a -> b) -> a -> b
$
        forall k (i :: Nat) r.
Finite k =>
SNat i -> ((Lookup (Objects k) i ~ At k i) => r) -> r
withAtLookup @j (forall (n :: Nat). SNatI n => SNat n
snat @(Index b)) (((Lookup (Objects j) (Index b) ~ At j (Index b)) => [[Natural]])
 -> [[Natural]])
-> ((Lookup (Objects j) (Index b) ~ At j (Index b)) => [[Natural]])
-> [[Natural]]
forall a b. (a -> b) -> a -> b
$
          forall {x} {y} (c :: x -> Constraint) (shape :: [y]) (xs :: [x])
       (s :: y) (i :: Nat) r.
KnownList c shape xs =>
SNat i
-> (Lookup shape i :~: 'Just s) -> (c (Entry xs i) => r) -> r
forall (c :: [[[Nat]]] -> Constraint) (shape :: [k])
       (xs :: [[[[Nat]]]]) (s :: k) (i :: Nat) r.
KnownList c shape xs =>
SNat i
-> (Lookup shape i :~: 'Just s) -> (c (Entry xs i) => r) -> r
withEntry @(KnownList KnownFibres (Objects j)) @(Objects k) @fs (forall (n :: Nat). SNatI n => SNat n
snat @(Index a)) 'Just a :~: 'Just a
Lookup (Objects k) (Index a) :~: 'Just a
forall {k} (a :: k). a :~: a
Refl ((KnownList KnownFibres (Objects j) (Entry fs (Index a)) =>
  [[Natural]])
 -> [[Natural]])
-> (KnownList KnownFibres (Objects j) (Entry fs (Index a)) =>
    [[Natural]])
-> [[Natural]]
forall a b. (a -> b) -> a -> b
$
            forall {x} {y} (c :: x -> Constraint) (shape :: [y]) (xs :: [x])
       (s :: y) (i :: Nat) r.
KnownList c shape xs =>
SNat i
-> (Lookup shape i :~: 'Just s) -> (c (Entry xs i) => r) -> r
forall (c :: [[Nat]] -> Constraint) (shape :: [j])
       (xs :: [[[Nat]]]) (s :: j) (i :: Nat) r.
KnownList c shape xs =>
SNat i
-> (Lookup shape i :~: 'Just s) -> (c (Entry xs i) => r) -> r
withEntry @KnownFibres @(Objects j) @(Entry fs (Index a)) (forall (n :: Nat). SNatI n => SNat n
snat @(Index b)) 'Just b :~: 'Just b
Lookup (Objects j) (Index b) :~: 'Just b
forall {k} (a :: k). a :~: a
Refl ((KnownFibres (Entry (Entry fs (Index a)) (Index b)) =>
  [[Natural]])
 -> [[Natural]])
-> (KnownFibres (Entry (Entry fs (Index a)) (Index b)) =>
    [[Natural]])
-> [[Natural]]
forall a b. (a -> b) -> a -> b
$
              forall (fs :: [[Nat]]). KnownFibres fs => [[Natural]]
fibresVal @(Cell fs a b)

instance
  (Finitary p, Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs)
  => Finitary (Reindex r (p :: j +-> k) fs)
  where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [[Natural]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @fs @a @b)
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Reindex r p fs a b -> Natural
toIndex @a @b (Reindex p a b
x) = String -> [[Natural]] -> Natural -> Natural
classIndex String
"Reindex: element outside every fibre" (forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @fs @a @b) (p a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex p a b
x) ((Ob a, Ob b) => Natural) -> p a b -> Natural
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a b
x
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> Reindex r p fs a b
fromIndex @a @b Natural
i = p a b -> Reindex r p fs a b
forall {j} {k} (r :: Retabulation) (p :: j +-> k)
       (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
p a b -> Reindex r p fs a b
Reindex (forall {j} {k} (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 (String -> [[Natural]] -> Natural -> Natural
classRep String
"Reindex: empty fibre" (forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @fs @a @b) Natural
i))

-- | Restricting a sheaf to a subobject gives a sheaf, provided the subobject is a /subsheaf/: the
-- element glued from a family of kept elements must be kept too. The tables of 'equalize' and the
-- pullbacks are subsheaves. This is a precondition, and a violation fails loudly: 'toIndex' finds
-- the glued element in no fibre.
--
-- There is no instance for 'Quotient'. A quotient of a sheaf is no sheaf in general ('glue' would
-- depend on which representative of each class it was handed), so colimits of sheaves go through
-- sheafification.
instance (Sheaf t p) => Sheaf t (Reindex Subobject p fs) where
  glue :: forall (a :: k) c (b :: j).
(Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> Reindex Subobject p fs x b)
-> Reindex Subobject p fs a b
glue Cover t k a c
c forall (x :: k). Leg t k a c x -> Reindex Subobject p fs x b
m = p a b -> Reindex Subobject p fs a b
forall {j} {k} (r :: Retabulation) (p :: j +-> k)
       (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
p a b -> Reindex r p fs a b
Reindex (forall {j} {k} t (p :: j +-> k) (a :: k) c (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 (p :: j +-> k) (a :: k) c (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 -> case Leg t k a c x -> Reindex Subobject p fs x b
forall (x :: k). Leg t k a c x -> Reindex Subobject p fs x b
m Leg t k a c x
l of Reindex p x b
x -> p x b
x)

-- | Whether a predicate on @p@\'s elements picks out a /subprofunctor/: the elements it keeps must
-- be closed under the action, since @'Reindex'@ inherits its 'dimap' from @p@ and so can only carve
-- out a set that is.
--
-- @'dimap' l r@ is @'lmap' l . 'rmap' r@, so closure under the two whiskerings separately is closure
-- under the action. That takes two walks over three objects instead of one over four.
closedUnder
  :: forall {j} {k} (p :: j +-> k)
   . (Finitary p, FiniteCat j, FiniteCat k)
  => (forall a b. (Ob a, Ob b) => p a b -> P.Bool)
  -> P.Bool
closedUnder :: forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool) -> Bool
closedUnder forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep =
  [Bool] -> Bool
forall (t :: Type -> Type). Foldable t => t Bool -> Bool
P.and
    ( forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @a -> forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @b ->
        let kept :: [p a a]
kept = [p a a
z | p a a
z <- forall {j} {k} (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, p a a -> Bool
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep p a a
z]
        in forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k @P.Bool (\ @c -> [p a a -> Bool
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep ((a ~> a) -> p a a -> p a a
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> a
g p a a
z) | a ~> a
g <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom k) @c @a, p a a
z <- [p a a]
kept])
             [Bool] -> [Bool] -> [Bool]
forall a. [a] -> [a] -> [a]
P.++ forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j @P.Bool (\ @d -> [p a a -> Bool
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep ((a ~> a) -> p a a -> p a a
forall (b :: j) (d :: j) (a :: k). (b ~> d) -> p a b -> p a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap a ~> a
h p a a
z) | a ~> a
h <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom j) @b @d, p a a
z <- [p a a]
kept])
    )

-- | Carve a subprofunctor out of @p@, the caller choosing which elements to keep, and receiving the
-- new object\'s inclusion. 'equalize' does this with the elements two transformations agree on.
-- Exposed so that a caller can pick out a subobject of its own. This is how a value (a graph read
-- off a file, say) becomes an object of @'FINITARY' j k@, as a subobject of a big enough ambient
-- one. The failure continuation is taken when the kept set is not 'closedUnder' the action, and so
-- is no subobject.
withSubobject
  :: forall {j} {k} (p :: j +-> k) r
   . (Finitary p, FiniteCat j, FiniteCat k)
  => (forall a b. (Ob a, Ob b) => p a b -> P.Bool)
  -> (forall q. (Finitary q) => FIN q ~> FIN p -> r)
  -> r
  -> r
withSubobject :: forall {j} {k} (p :: j +-> k) r.
(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 forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep forall (q :: j +-> k). Finitary q => (FIN q ~> FIN p) -> r
ok r
notClosed =
  if forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool) -> Bool
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool) -> Bool
closedUnder @p p a b -> Bool
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep
    then forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable @j @k (\ @a @b -> [[p a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex p a b
x] | p a b
x <- forall {j} {k} (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, p a b -> Bool
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool
keep p a b
x]) \ @fs ->
      forall (q :: j +-> k). Finitary q => (FIN q ~> FIN p) -> r
ok @(Reindex Subobject p fs) (Prof (Reindex Subobject p t) p
-> Sub Prof (FIN (Reindex Subobject p t)) (FIN p)
forall {k} (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 p t :~> p) -> Prof (Reindex Subobject p t) p
forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \(Reindex p a b
x) -> p a b
x))
    else r
notClosed

-- * Finitary profunctors presented by their tables

-- | Both tables of a 'Tabulated' profunctor over the objects of @j@ and @k@.
type KnownTables :: Type -> Type -> [[[[Nat]]]] -> [[[[Nat]]]] -> Constraint
type KnownTables j k lm rm = (KnownTable (Objects j) (Objects k) lm, KnownTable (Objects j) (Objects k) rm)

-- | A finitary profunctor given by nothing but its tables: at each pair of objects, for each arrow
-- into @a@ and each arrow out of @b@, the function the arrow induces on element indices. A value is
-- its index, and 'dimap' is two lookups.
--
-- Unlike 'Reindex', a view that delegates to @p@, this is the skeleton: 'withTabulated' pays one
-- full enumeration to build it and nothing afterwards. Use it in place of a costly profunctor that
-- is used often, such as 'Proarrow.Category.Enriched.Finitary.Sheaf.Sheafify', whose 'toIndex'
-- re-runs its whole enumeration since a 'Finitary' instance cannot memoise.
--
-- The @lm@ table has, at @(a, b)@, one row per arrow @g :: c '~>' a@ in 'arrowSlot' order, listing
-- @'toIndex' ('lmap' g x)@ for each element @x@ in index order. @rm@ has one row per @h :: b '~>' d@
-- in 'coarrowSlot' order for 'rmap'. A row's length is the size at @(a, b)@.
--
-- @t@ is the coverage the tables have been checked to be a sheaf for, which the tables cannot say.
-- Only the builders apply it: 'withTabulated' uses 'Trivial', which has no covers, and
-- 'Proarrow.Category.Enriched.Finitary.Sheaf.withTabulatedSheaf' decides the condition first.
type Tabulated :: forall {j} {k}. Coverage -> [[[[Nat]]]] -> [[[[Nat]]]] -> j +-> k
data Tabulated t lm rm a b where
  Tabulated :: (Ob a, Ob b) => Natural -> Tabulated t lm rm a b

-- | Where an arrow sits among all the arrows into its target: by source object first, then by the
-- arrow's own index. The row order of a 'Tabulated' @lm@ table.
arrowSlot :: forall {k} (c :: k) a. (FiniteCat k, Ob c, Ob a) => c ~> a -> Natural
arrowSlot :: forall {k} (c :: k) (a :: k).
(FiniteCat k, Ob c, Ob a) =>
(c ~> a) -> Natural
arrowSlot c ~> a
g = [Natural] -> Natural
forall a. Num a => [a] -> a
forall (t :: Type -> Type) a. (Foldable t, Num a) => t a -> a
P.sum (forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @c' -> [forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Hom k) @c' @a | forall (a :: k). (Enumerable k, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @c' Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
P.< forall (a :: k). (Enumerable k, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @c]) Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.+ (c ~> a) -> Natural
forall (a :: k) (b :: k). (Ob a, Ob b) => (a ~> b) -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex c ~> a
g

-- | Where an arrow sits among all the arrows out of its source: the row order of an @rm@ table.
coarrowSlot :: forall {j} (b :: j) d. (FiniteCat j, Ob b, Ob d) => b ~> d -> Natural
coarrowSlot :: forall {k} (c :: k) (a :: k).
(FiniteCat k, Ob c, Ob a) =>
(c ~> a) -> Natural
coarrowSlot b ~> d
h = [Natural] -> Natural
forall a. Num a => [a] -> a
forall (t :: Type -> Type) a. (Foldable t, Num a) => t a -> a
P.sum (forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @d' -> [forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Hom j) @b @d' | forall (a :: j). (Enumerable j, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @d' Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
P.< forall (a :: j). (Enumerable j, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @d]) Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.+ (b ~> d) -> Natural
forall (a :: j) (b :: j). (Ob a, Ob b) => (a ~> b) -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex b ~> d
h

-- | 'lmap' reads the arrow's row in the @lm@ cell at the value's index; 'rmap' then reads the @rm@
-- cell at the new source object.
instance (FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Profunctor (Tabulated t lm rm :: j +-> k) where
  dimap :: forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a)
-> (b ~> d) -> Tabulated t lm rm a b -> Tabulated t lm rm c d
dimap @c @a @b @_ c ~> a
l b ~> d
r (Tabulated Natural
i) =
    c ~> a
l (c ~> a)
-> ((Ob c, Ob a) => Tabulated t lm rm c d) -> Tabulated t lm rm c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
r (b ~> d)
-> ((Ob b, Ob d) => Tabulated t lm rm c d) -> Tabulated t lm rm c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// Natural -> Tabulated t lm rm c d
forall {k} {j} (a :: k) (b :: j) t (lm :: [[[[Nat]]]])
       (rm :: [[[[Nat]]]]).
(Ob a, Ob b) =>
Natural -> Tabulated t lm rm a b
Tabulated ([[Natural]] -> Natural -> Natural -> Natural
forall {i} {i} {a}.
(Integral i, Integral i) =>
[[a]] -> i -> i -> a
look (forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @rm @c @b) ((b ~> d) -> Natural
forall {k} (c :: k) (a :: k).
(FiniteCat k, Ob c, Ob a) =>
(c ~> a) -> Natural
coarrowSlot b ~> d
r) ([[Natural]] -> Natural -> Natural -> Natural
forall {i} {i} {a}.
(Integral i, Integral i) =>
[[a]] -> i -> i -> a
look (forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @lm @a @b) ((c ~> a) -> Natural
forall {k} (c :: k) (a :: k).
(FiniteCat k, Ob c, Ob a) =>
(c ~> a) -> Natural
arrowSlot c ~> a
l) Natural
i))
    where
      look :: [[a]] -> i -> i -> a
look [[a]]
cell i
slot = [a] -> i -> a
forall i a. Integral i => [a] -> i -> a
genericIndex ([[a]] -> i -> [a]
forall i a. Integral i => [a] -> i -> a
genericIndex [[a]]
cell i
slot)
  (Ob a, Ob b) => r
r \\ :: forall (a :: k) (b :: j) r.
((Ob a, Ob b) => r) -> Tabulated t lm rm a b -> r
\\ Tabulated{} = r
(Ob a, Ob b) => r
r

-- | The numbering is the value. 'size' is a row's length and the rest is the identity, except for
-- the range check. An index that /is/ the value has nowhere else to fail. Stored unchecked, it
-- would surface much later, as 'genericIndex' running off a row inside 'dimap'.
instance (FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Finitary (Tabulated t lm rm :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = case forall (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
forall {j} {k} (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
(Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs,
 Ob a, Ob b) =>
[[Natural]]
cellVal @lm @a @b of
    [Natural]
row : [[Natural]]
_ -> [Natural] -> Natural
forall i a. Num i => [a] -> i
genericLength [Natural]
row
    [] -> String -> Natural
forall a. HasCallStack => String -> a
P.error String
"Tabulated: empty cell"
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Tabulated t lm rm a b -> Natural
toIndex (Tabulated Natural
i) = Natural
i
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> Tabulated t lm rm a b
fromIndex @a @b Natural
i
    | Natural
i Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
P.< forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Tabulated t lm rm) @a @b = Natural -> Tabulated t lm rm a b
forall {k} {j} (a :: k) (b :: j) t (lm :: [[[[Nat]]]])
       (rm :: [[[[Nat]]]]).
(Ob a, Ob b) =>
Natural -> Tabulated t lm rm a b
Tabulated Natural
i
    | Bool
P.otherwise = String -> Tabulated t lm rm a b
forall a. HasCallStack => String -> a
P.error String
"Tabulated: index out of range"

-- | The two tables of @p@, reified, with nothing said about what they present. The enumeration
-- (every element, every arrow, one 'toIndex' per pair) is paid here and never again. The two
-- builders differ only in the tag they hand the tables to, so the enumeration is written once,
-- here. The other builder is 'Proarrow.Category.Enriched.Finitary.Sheaf.withTabulatedSheaf', which
-- lives over there because deciding the sheaf condition needs what is built on this module.
withTables
  :: forall {j} {k} (p :: j +-> k) r
   . (Finitary p, FiniteCat j, FiniteCat k)
  => (forall lm rm. (KnownTables j k lm rm) => r)
  -> r
withTables :: forall {j} {k} (p :: j +-> k) r.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
withTables forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
KnownTables j k lm rm =>
r
k =
  forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable @j @k
    ( \ @a @b -> let xs :: [p a b]
xs = forall {j} {k} (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 in forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @c -> [(p a b -> Natural) -> [p a b] -> [Natural]
forall a b. (a -> b) -> [a] -> [b]
P.map (p a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex (p a b -> Natural) -> (p a b -> p a b) -> p a b -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (a ~> a) -> p a b -> p a b
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> a
g) [p a b]
xs | a ~> a
g <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom k) @c @a]
    )
    \ @lm ->
      forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable @j @k
        ( \ @a @b -> let xs :: [p a b]
xs = forall {j} {k} (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 in forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @d -> [(p a b -> Natural) -> [p a b] -> [Natural]
forall a b. (a -> b) -> [a] -> [b]
P.map (p a a -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex (p a a -> Natural) -> (p a b -> p a a) -> p a b -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (b ~> a) -> p a b -> p a a
forall (b :: j) (d :: j) (a :: k). (b ~> d) -> p a b -> p a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap b ~> a
h) [p a b]
xs | b ~> a
h <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom j) @b @d]
        )
        \ @rm -> forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
KnownTables j k lm rm =>
r
k @lm @rm

-- | An element of @p@ as the index that stands for it in a presentation of @p@.
toTabulated :: forall {j} {k} t lm rm (p :: j +-> k). (Finitary p) => p :~> Tabulated t lm rm
toTabulated :: forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]])
       (p :: j +-> k).
Finitary p =>
p :~> Tabulated t lm rm
toTabulated p a b
x = Natural -> Tabulated t lm rm a b
forall {k} {j} (a :: k) (b :: j) t (lm :: [[[[Nat]]]])
       (rm :: [[[[Nat]]]]).
(Ob a, Ob b) =>
Natural -> Tabulated t lm rm a b
Tabulated (p a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex p a b
x) ((Ob a, Ob b) => Tabulated t lm rm a b)
-> p a b -> Tabulated t lm rm a b
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> p a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ p a b
x

-- | An index in a presentation of @p@ as the element of @p@ it stands for.
fromTabulated :: forall {j} {k} t lm rm (p :: j +-> k). (Finitary p) => Tabulated t lm rm :~> p
fromTabulated :: forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]])
       (p :: j +-> k).
Finitary p =>
Tabulated t lm rm :~> p
fromTabulated (Tabulated Natural
i) = Natural -> p a b
forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> p a b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex Natural
i

-- | Present a finitary profunctor by its tables, once, with the isomorphism both ways.
--
-- The continuation receives the presentation as a named @tab ~ 'Tabulated' 'Trivial' lm rm@, since
-- the tables alone do not fix @j@ and @k@. Bind it as @\\ \@tab toTab fromTab -> ...@.
--
-- The presentation is a sheaf only for 'Trivial'. To present a sheaf /as/ one, use
-- 'Proarrow.Category.Enriched.Finitary.Sheaf.withTabulatedSheaf'.
withTabulated
  :: forall {j} {k} (p :: j +-> k) r
   . (Finitary p, FiniteCat j, FiniteCat k)
  => ( forall {lm} {rm} (tab :: j +-> k)
        . (tab ~ Tabulated Trivial lm rm, KnownTables j k lm rm)
       => (p :~> tab)
       -> (tab :~> p)
       -> r
     )
  -> r
withTabulated :: forall {j} {k} (p :: j +-> k) r.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
 (tab ~ Tabulated Trivial lm rm, KnownTables j k lm rm) =>
 (p :~> tab) -> (tab :~> p) -> r)
-> r
withTabulated forall {lm :: [[[[Nat]]]]} {rm :: [[[[Nat]]]]} (tab :: j +-> k).
(tab ~ Tabulated Trivial lm rm, KnownTables j k lm rm) =>
(p :~> tab) -> (tab :~> p) -> r
k = forall {j} {k} (p :: j +-> k) r.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]).
 KnownTables j k lm rm =>
 r)
-> r
forall (p :: j +-> k) r.
(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 Trivial lm rm, KnownTables j k lm rm) =>
(p :~> tab) -> (tab :~> p) -> r
forall (tab :: j +-> k).
(tab ~ Tabulated Trivial lm rm, KnownTables j k lm rm) =>
(p :~> tab) -> (tab :~> p) -> r
k @(Tabulated Trivial lm rm) p a b -> Tabulated Trivial lm rm a b
p :~> Tabulated Trivial lm rm
forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]])
       (p :: j +-> k).
Finitary p =>
p :~> Tabulated t lm rm
toTabulated Tabulated Trivial lm rm a b -> p a b
Tabulated Trivial lm rm :~> p
forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]])
       (p :: j +-> k).
Finitary p =>
Tabulated t lm rm :~> p
fromTabulated

-- | Glue by search: find the element whose restrictions along the legs are the family. This gives a
-- 'Sheaf' instance to a sheaf with no 'glue' of its own, such as a 'Tabulated' one or a subsheaf of
-- a profunctor that is no sheaf (like the closed sieves). Lawful iff @p@ is a sheaf, which
-- 'Proarrow.Category.Enriched.Finitary.Sheaf.isSheaf' decides.
--
-- Errors if no element matches, and also if more than one does: over a cover with no legs every
-- element matches, so an unseparated @p@ would otherwise glue silently to the first one.
glueBySearch
  :: forall t {j} {k} (p :: j +-> k) (a :: k) c (b :: j)
   . (Site t k, Finitary p, Ob a, Ob b)
  => Cover t k a c
  -> (forall x. Leg t k a c x -> p x b)
  -> p a b
glueBySearch :: forall t {j} {k} (p :: j +-> k) (a :: k) c (b :: j).
(Site t k, Finitary 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
glueBySearch Cover t k a c
c forall (x :: k). Leg t k a c x -> p x b
m = case (p a b -> Bool) -> [p a b] -> [p a b]
forall a. (a -> Bool) -> [a] -> [a]
P.filter (\p a b
x -> ((p a b -> Bool) -> Bool) -> [p a b -> Bool] -> Bool
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Bool
P.all ((p a b -> Bool) -> p a b -> Bool
forall a b. (a -> b) -> a -> b
$ p a b
x) [p a b -> Bool]
family) (forall {j} {k} (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) of
  [p a b
x] -> p a b
x
  [] -> String -> p a b
forall a. HasCallStack => String -> a
P.error String
"glue: no element restricts to the family -- not a sheaf"
  [p a b]
_ -> String -> p a b
forall a. HasCallStack => String -> a
P.error String
"glue: more than one element restricts to the family -- not a sheaf"
  where
    -- One test per leg, not one per leg and element. @ix@ is the leg source\'s 'toIndex', bound
    -- before the element arrives, so an instance that searches for an index searches once per leg
    -- instead of once for every element it is asked about.
    family :: [p a b -> P.Bool]
    family :: [p a b -> Bool]
family = [(let ix :: p x b -> Natural
ix = p x b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex; i :: Natural
i = p x b -> Natural
ix (Leg t k a c x -> p x b
forall (x :: k). Leg t k a c x -> p x b
m Leg t k a c x
l) in \p a b
x -> p x b -> Natural
ix ((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} {k} (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 (x :: k). Leg t k a c x -> x ~> a
forall t k (a :: k) c (x :: k). Site t k => Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l) p a b
x) Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
i) ((Ob x, Ob a) => p a b -> Bool) -> (x ~> a) -> p a b -> Bool
forall (a :: k) (b :: k) r. ((Ob a, Ob b) => r) -> (a ~> b) -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ Leg t k a c x -> x ~> a
forall (a :: k) c (x :: k). Leg t k a c x -> x ~> a
forall t k (a :: k) c (x :: k). Site t k => Leg t k a c x -> x ~> a
legArrow Leg t k a c x
l | SomeLeg Leg t k a c x
l <- Cover t k a c -> [SomeLeg t k a c]
forall (a :: k) c. Cover t k a c -> [SomeLeg t k a c]
forall t k (a :: k) c.
Site t k =>
Cover t k a c -> [SomeLeg t k a c]
legs Cover t k a c
c]

-- | A tabulated profunctor glues by search, since it knows nothing of the profunctor it presents.
-- Only for the coverage its tag names. The tag is the only evidence that the search will
-- find its element, so a presentation may be used as a sheaf for the coverage it was checked
-- against and for no other. At 'Trivial', which 'withTabulated' applies and which has no covers,
-- the instance is vacuous and 'glueBySearch' is unreachable.
instance (Site t k, FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Sheaf t (Tabulated t lm rm :: j +-> k) where
  glue :: forall (a :: k) c (b :: j).
(Ob a, Ob b) =>
Cover t k a c
-> (forall (x :: k). Leg t k a c x -> Tabulated t lm rm x b)
-> Tabulated t lm rm a b
glue = forall t {j} {k} (p :: j +-> k) (a :: k) c (b :: j).
(Site t k, Finitary 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
glueBySearch @t

-- * Equalizers and coequalizers

-- | The element of @p@ that @f@ sends to a given element of @q@, if the element is in @f@\'s
-- image. The first one found. For an injective @f@ (an equalizer\'s inclusion) it is the only one.
-- For a projection it is a choice of representative, and the caller is then relying on what it does
-- with it not depending on which.
preimageMaybe
  :: forall {j} {k} (p :: j +-> k) q (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 :: forall {j} {k} (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 p a b -> q a b
f q a b
y =
  let toIndexQ :: q a b -> Natural
toIndexQ = forall {j} {k} (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 @q @a @b
      iy :: Natural
iy = q a b -> Natural
toIndexQ q a b
y
  in (p a b -> Bool) -> [p a b] -> Maybe (p a b)
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Maybe a
find (\p a b
x -> q a b -> Natural
toIndexQ (p a b -> q a b
f p a b
x) Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
iy) (forall {j} {k} (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)

-- | 'preimageMaybe' where the element has to be in the image. Both factorizations below need this,
-- in opposite directions.
preimage
  :: forall {j} {k} (p :: j +-> k) q (a :: k) (b :: j)
   . (Finitary p, Finitary q, Ob a, Ob b)
  => P.String -> (p a b -> q a b) -> q a b -> p a b
preimage :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, Ob a, Ob b) =>
String -> (p a b -> q a b) -> q a b -> p a b
preimage String
msg p a b -> q a b
f q a b
y = p a b -> Maybe (p a b) -> p a b
forall a. a -> Maybe a -> a
fromMaybe (String -> p a b
forall a. HasCallStack => String -> a
P.error String
msg) ((p a b -> q a b) -> q a b -> Maybe (p a b)
forall {j} {k} (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 p a b -> q a b
f q a b
y)

-- | Partition a list of indices into the equivalence classes generated by a list of pairs. Both
-- levels are sorted, so the classes come out ordered by their least member and the table is canonical.
classes :: [(Natural, Natural)] -> [Natural] -> [[Natural]]
classes :: [(Natural, Natural)] -> [Natural] -> [[Natural]]
classes [(Natural, Natural)]
pairs [Natural]
is = [[Natural]] -> [[Natural]]
forall a. Ord a => [a] -> [a]
sort (([Natural] -> [Natural]) -> [[Natural]] -> [[Natural]]
forall a b. (a -> b) -> [a] -> [b]
P.map [Natural] -> [Natural]
forall a. Ord a => [a] -> [a]
sort (((Natural, Natural) -> [[Natural]] -> [[Natural]])
-> [[Natural]] -> [(Natural, Natural)] -> [[Natural]]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
P.foldr (Natural, Natural) -> [[Natural]] -> [[Natural]]
forall {a}. Eq a => (a, a) -> [[a]] -> [[a]]
merge ((Natural -> [Natural]) -> [Natural] -> [[Natural]]
forall a b. (a -> b) -> [a] -> [b]
P.map (Natural -> [Natural] -> [Natural]
forall a. a -> [a] -> [a]
: []) [Natural]
is) [(Natural, Natural)]
pairs))
  where
    merge :: (a, a) -> [[a]] -> [[a]]
merge (a
i, a
j) [[a]]
cs = case ([a] -> Bool) -> [[a]] -> ([[a]], [[a]])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (\[a]
c -> a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: Type -> Type) a.
(Foldable t, Eq a) =>
a -> t a -> Bool
P.elem a
i [a]
c Bool -> Bool -> Bool
|| a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: Type -> Type) a.
(Foldable t, Eq a) =>
a -> t a -> Bool
P.elem a
j [a]
c) [[a]]
cs of
      ([], [[a]]
_) -> String -> [[a]]
forall a. HasCallStack => String -> a
P.error String
"classes: an index outside the set being partitioned"
      ([[a]]
hit, [[a]]
miss) -> [[a]] -> [a]
forall (t :: Type -> Type) a. Foldable t => t [a] -> [a]
P.concat [[a]]
hit [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [[a]]
miss

-- | The position of the class an index lies in.
classIndex :: P.String -> [[Natural]] -> Natural -> Natural
classIndex :: String -> [[Natural]] -> Natural -> Natural
classIndex String
msg [[Natural]]
cls Natural
n = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral (Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe (String -> Int
forall a. HasCallStack => String -> a
P.error String
msg) (([Natural] -> Bool) -> [[Natural]] -> Maybe Int
forall a. (a -> Bool) -> [a] -> Maybe Int
findIndex (Natural -> [Natural] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: Type -> Type) a.
(Foldable t, Eq a) =>
a -> t a -> Bool
P.elem Natural
n) [[Natural]]
cls))

-- | The first member of the class at a position, which stands for the class.
classRep :: P.String -> [[Natural]] -> Natural -> Natural
classRep :: String -> [[Natural]] -> Natural -> Natural
classRep String
msg [[Natural]]
cls Natural
i = case [[Natural]] -> Natural -> [Natural]
forall i a. Integral i => [a] -> i -> a
genericIndex [[Natural]]
cls Natural
i of
  Natural
n : [Natural]
_ -> Natural
n
  [] -> String -> Natural
forall a. HasCallStack => String -> a
P.error String
msg

-- | Equalizers of finitary profunctors between finite categories: at each pair of objects, keep the
-- indices on which the two natural transformations agree, and reify the table.
instance (Enumerable j, Enumerable k) => HasEqualizers (FINITARY j k) where
  equalize :: forall (a :: FINITARY j k) (b :: FINITARY j k) r.
(a ~> b)
-> (a ~> b) -> (forall (e :: FINITARY j k). (e ~> a) -> r) -> r
equalize (Sub (Prof a1 :~> b1
f)) (Sub (Prof a1 :~> b1
g)) forall (e :: FINITARY 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} {k} (p :: j +-> k) (q :: j +-> k) r.
(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 :: FINITARY j k). (e ~> a) -> r
k (Prof (Reindex Subobject a1 fs) a1
-> Sub Prof (SUB (Reindex Subobject a1 fs)) (SUB a1)
forall {k} (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} {k} (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 :: FINITARY j k) (x :: FINITARY j k)
       (e' :: FINITARY 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} (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} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof ((a1 :~> b1) -> (a1 :~> b1) -> a1 :~> a1
forall {j} {k} (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))

-- | The equalizer of two natural transformations: the source retabulated along the points where
-- they agree, handed on with its inclusion. 'FINITARY' and its subcategories of sheaves equalize
-- alike. Only the wrapper around the result differs, so the construction lives here once.
equalizeNat
  :: forall {j} {k} (p :: j +-> k) q r
   . (Finitary p, Finitary q, Enumerable j, Enumerable k)
  => (p :~> q)
  -> (p :~> q)
  -> (forall fs. (KnownTable (Objects j) (Objects k) fs) => (Reindex Subobject p fs :~> p) -> r)
  -> r
equalizeNat :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) r.
(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 p :~> q
f p :~> q
g forall (fs :: [[[[Nat]]]]).
KnownTable (Objects j) (Objects k) fs =>
(Reindex Subobject p fs :~> p) -> r
k =
  forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable @j @k
    ( \ @a @b ->
        let toIndexP :: p a b -> Natural
toIndexP = forall {j} {k} (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 @a @b; toIndexQ :: q a b -> Natural
toIndexQ = forall {j} {k} (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 @q @a @b
        in [[p a b -> Natural
toIndexP p a b
x] | p a b
x <- forall {j} {k} (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, q a b -> Natural
toIndexQ (p a b -> q a b
p :~> q
f p a b
x) Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== q a b -> Natural
toIndexQ (p a b -> q a b
p :~> q
g p a b
x)]
    )
    \ @fs -> forall (fs :: [[[[Nat]]]]).
KnownTable (Objects j) (Objects k) fs =>
(Reindex Subobject p fs :~> p) -> r
k @fs \(Reindex p a b
x) -> p a b
x

-- | Factor through an equalizer's inclusion, by 'preimage': the arrow must land in the image.
factorThroughEqualizer
  :: forall {j} {k} (e :: j +-> k) x e'
   . (Finitary e, Finitary x, Profunctor e')
  => (e :~> x)
  -> (e' :~> x)
  -> e' :~> e
factorThroughEqualizer :: forall {j} {k} (e :: j +-> k) (x :: j +-> k) (e' :: j +-> k).
(Finitary e, Finitary x, Profunctor e') =>
(e :~> x) -> (e' :~> x) -> e' :~> e
factorThroughEqualizer e :~> x
incl e' :~> x
h e' a b
y = String -> (e a b -> x a b) -> x a b -> e a b
forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, Ob a, Ob b) =>
String -> (p a b -> q a b) -> q a b -> p a b
preimage String
"factorEqualizer: h's image must lie within incl's image" e a b -> x a b
e :~> x
incl (e' a b -> x a b
e' :~> x
h e' a b
y) ((Ob a, Ob b) => e a b) -> e' a b -> e a b
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> e' a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ e' a b
y

-- | Coequalizers: at each pair of objects, partition the indices by the equivalence relation the two
-- natural transformations generate, and reify the table. Naturality makes the partition a
-- congruence, so the quotient is again a profunctor.
instance (Enumerable j, Enumerable k) => HasCoequalizers (FINITARY j k) where
  coequalize :: forall (a :: FINITARY j k) (b :: FINITARY j k) r.
(a ~> b)
-> (a ~> b) -> (forall (c :: FINITARY j k). (b ~> c) -> r) -> r
coequalize (Sub (Prof a1 :~> b1
f)) (Sub (Prof a1 :~> b1
g)) forall (c :: FINITARY 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} {k} (p :: j +-> k) (q :: j +-> k) r.
(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 \b1 :~> Reindex Quotient b1 fs
proj -> (b ~> SUB (Reindex Quotient b1 fs)) -> r
forall (c :: FINITARY j k). (b ~> c) -> r
k (Prof b1 (Reindex Quotient b1 fs)
-> Sub Prof (SUB b1) (SUB (Reindex Quotient b1 fs))
forall {k} (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 :~> Reindex Quotient b1 fs) -> Prof b1 (Reindex Quotient b1 fs)
forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof b1 a b -> Reindex Quotient b1 fs a b
b1 :~> Reindex Quotient b1 fs
proj))
  factorCoequalizer :: forall (c :: FINITARY j k) (x :: FINITARY j k)
       (c' :: FINITARY 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} (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} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof ((a1 :~> b1) -> (a1 :~> b1) -> b1 :~> b1
forall {j} {k} (c :: j +-> k) (x :: j +-> k) (c' :: j +-> k).
(Finitary c, Finitary x, Profunctor c') =>
(x :~> c) -> (x :~> c') -> c :~> c'
factorThroughCoequalizer a1 a b -> b1 a b
a1 :~> b1
proj a1 a b -> b1 a b
a1 :~> b1
h))

-- | The coequalizer of two natural transformations: the target retabulated along the classes the
-- two generate, handed on with its projection. The dual of 'equalizeNat', and shared the same way,
-- though the sheaves take only half of it. A quotient of sheaves is no sheaf and has to be
-- sheafified before it is the coequalizer /there/.
coequalizeNat
  :: forall {j} {k} (p :: j +-> k) q r
   . (Finitary p, Finitary q, Enumerable j, Enumerable k)
  => (p :~> q)
  -> (p :~> q)
  -> (forall fs. (KnownTable (Objects j) (Objects k) fs) => (q :~> Reindex Quotient q fs) -> r)
  -> r
coequalizeNat :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) r.
(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 p :~> q
f p :~> q
g forall (fs :: [[[[Nat]]]]).
KnownTable (Objects j) (Objects k) fs =>
(q :~> Reindex Quotient q fs) -> r
k =
  forall j k r.
(Enumerable j, Enumerable k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => [[Natural]])
-> (forall (t :: [[[[Nat]]]]).
    KnownTable (Objects j) (Objects k) t =>
    r)
-> r
buildTable @j @k
    ( \ @a @b ->
        let toIndexQ :: q a b -> Natural
toIndexQ = forall {j} {k} (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 @q @a @b
        in [(Natural, Natural)] -> [Natural] -> [[Natural]]
classes [(q a b -> Natural
toIndexQ (p a b -> q a b
p :~> q
f p a b
x), q a b -> Natural
toIndexQ (p a b -> q a b
p :~> q
g p a b
x)) | p a b
x <- forall {j} {k} (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] ((q a b -> Natural) -> [q a b] -> [Natural]
forall a b. (a -> b) -> [a] -> [b]
P.map q a b -> Natural
toIndexQ (forall {j} {k} (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 @q @a @b))
    )
    \ @fs -> forall (fs :: [[[[Nat]]]]).
KnownTable (Objects j) (Objects k) fs =>
(q :~> Reindex Quotient q fs) -> r
k @fs q a b -> Reindex Quotient q t a b
q :~> Reindex Quotient q t
forall {j} {k} (r :: Retabulation) (p :: j +-> k)
       (fs :: [[[[Nat]]]]) (a :: k) (b :: j).
p a b -> Reindex r p fs a b
Reindex

-- | Factor through a coequalizer's projection, by 'preimage': the projection must be onto. The
-- dual of 'factorThroughEqualizer', and stated apart from the instance for the same reason. Unlike
-- the dual it is not shared with the sheaves. A projection there is epi without being onto, and
-- they use 'Proarrow.Category.Enriched.Finitary.Sheaf.factorThroughLocalEpi' instead.
factorThroughCoequalizer
  :: forall {j} {k} (c :: j +-> k) x c'
   . (Finitary c, Finitary x, Profunctor c')
  => (x :~> c)
  -> (x :~> c')
  -> c :~> c'
factorThroughCoequalizer :: forall {j} {k} (c :: j +-> k) (x :: j +-> k) (c' :: j +-> k).
(Finitary c, Finitary x, Profunctor c') =>
(x :~> c) -> (x :~> c') -> c :~> c'
factorThroughCoequalizer x :~> c
proj x :~> c'
h c a b
y = x a b -> c' a b
x :~> c'
h (String -> (x a b -> c a b) -> c a b -> x a b
forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, Ob a, Ob b) =>
String -> (p a b -> q a b) -> q a b -> p a b
preimage String
"factorCoequalizer: proj must be onto" x a b -> c a b
x :~> c
proj c a b
y) ((Ob a, Ob b) => c' a b) -> c a b -> c' a b
forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> c a b -> r
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) r.
Profunctor p =>
((Ob a, Ob b) => r) -> p a b -> r
\\ c a b
y

-- * Pullbacks, pushouts and images

-- | Pullbacks are equalizers of products, and pushouts coequalizers of coproducts, all of which
-- finitary profunctors have.
instance (Enumerable j, Enumerable k) => HasPullbacks (FINITARY j k)

instance (Enumerable j, Enumerable k) => HasPushouts (FINITARY j k)

-- | The image of a natural transformation is the equalizer of its cokernel pair.
instance (Enumerable j, Enumerable k) => HasEpiMonoFactorization (FINITARY j k)

-- * Natural transformations, enumerated

-- | Enumerate a set of families by brute force: every way of choosing a value at each point of the
-- domain, kept when it satisfies every condition. A condition is checked as soon as both of its
-- points have been chosen, so a violation prunes the whole subtree of completions instead of
-- rejecting each of them in turn. This keeps the candidate space from being the full product.
-- Families come out in the same order as @'P.sequence' choices@ would give them, with the earliest
-- point varying slowest.
familiesSatisfying :: [[v]] -> [(P.Int, P.Int, v -> v -> P.Bool)] -> [[v]]
familiesSatisfying :: forall v. [[v]] -> [(Int, Int, v -> v -> Bool)] -> [[v]]
familiesSatisfying [[v]]
choices [(Int, Int, v -> v -> Bool)]
laws = Int -> [v] -> [[v]] -> [[v]]
go Int
0 [] [[v]]
choices
  where
    -- a condition can first be tested at the later of its two points
    byDepth :: IntMap [(Int, Int, v -> v -> Bool)]
byDepth = ([(Int, Int, v -> v -> Bool)]
 -> [(Int, Int, v -> v -> Bool)] -> [(Int, Int, v -> v -> Bool)])
-> [(Int, [(Int, Int, v -> v -> Bool)])]
-> IntMap [(Int, Int, v -> v -> Bool)]
forall a. (a -> a -> a) -> [(Int, a)] -> IntMap a
IM.fromListWith [(Int, Int, v -> v -> Bool)]
-> [(Int, Int, v -> v -> Bool)] -> [(Int, Int, v -> v -> Bool)]
forall a. [a] -> [a] -> [a]
(P.++) [(Int -> Int -> Int
forall a. Ord a => a -> a -> a
P.max Int
src Int
tgt, [(Int
src, Int
tgt, v -> v -> Bool
rel)]) | (Int
src, Int
tgt, v -> v -> Bool
rel) <- [(Int, Int, v -> v -> Bool)]
laws]
    go :: Int -> [v] -> [[v]] -> [[v]]
go Int
_ [v]
chosen [] = [[v] -> [v]
forall a. [a] -> [a]
P.reverse [v]
chosen]
    go Int
i [v]
chosen ([v]
cs : [[v]]
rest) =
      [ [v]
row
      | v
v <- [v]
cs
      , let chosen' :: [v]
chosen' = v
v v -> [v] -> [v]
forall a. a -> [a] -> [a]
: [v]
chosen
      , let at :: Int -> v
at Int
n = [v]
chosen' [v] -> Int -> v
forall a. HasCallStack => [a] -> Int -> a
P.!! (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
P.- Int
n) -- @chosen'@ holds points @0..i@ in reverse
      , ((Int, Int, v -> v -> Bool) -> Bool)
-> [(Int, Int, v -> v -> Bool)] -> Bool
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Bool
P.all (\(Int
src, Int
tgt, v -> v -> Bool
rel) -> v -> v -> Bool
rel (Int -> v
at Int
src) (Int -> v
at Int
tgt)) ([(Int, Int, v -> v -> Bool)]
-> Int
-> IntMap [(Int, Int, v -> v -> Bool)]
-> [(Int, Int, v -> v -> Bool)]
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault [] Int
i IntMap [(Int, Int, v -> v -> Bool)]
byDepth)
      , [v]
row <- Int -> [v] -> [[v]] -> [[v]]
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
P.+ Int
1) [v]
chosen' [[v]]
rest
      ]

-- | Which of the enumerated families a tabulated one is.
familyIndex :: (P.Eq v) => P.String -> [[v]] -> [v] -> Natural
familyIndex :: forall v. Eq v => String -> [[v]] -> [v] -> Natural
familyIndex String
msg [[v]]
fams [v]
row = case [v] -> [[v]] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
elemIndex [v]
row [[v]]
fams of
  Just Int
i -> Int -> Natural
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Int
i
  Maybe Int
Nothing -> String -> Natural
forall a. HasCallStack => String -> a
P.error String
msg

-- | One point of the domain of the end @∫ Set(p c d, q c d)@ whose elements are the natural
-- transformations @p -> q@: an object pair and an element of @p@ there. Every end below is one of
-- these. The internal hom only changes the weight @p@, and the subobject classifier also changes
-- what the conditions are read as. So the whole topos is built on this one enumeration.
type NatKey = (Natural, Natural, Natural)

-- | Visit every point of that domain, in one fixed order.
natDomain
  :: forall {j} {k} (p :: j +-> k) r
   . (Finitary p, FiniteCat j, FiniteCat k)
  => (forall a b. (Ob a, Ob b) => p a b -> r)
  -> [r]
natDomain :: forall {j} {k} (p :: j +-> k) r.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r
f = forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @a -> forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @b -> (p a a -> r) -> [p a a] -> [r]
forall a b. (a -> b) -> [a] -> [b]
P.map p a a -> r
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r
f (forall {j} {k} (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)

natKey
  :: forall {j} {k} (a :: k) (b :: j) (p :: j +-> k). (FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) => p a b -> NatKey
natKey :: forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey p a b
x = (forall (a :: k). (Enumerable k, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @a, forall (a :: j). (Enumerable j, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @b, p a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex p a b
x)

-- | Where each point of the domain sits in a tabulated family. This is the same for every family
-- over a given weight, so bind it once outside a loop over them.
natPositions
  :: forall {j} {k} (p :: j +-> k). (Finitary p, FiniteCat j, FiniteCat k) => M.Map NatKey P.Int
natPositions :: forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions = forall {j} {k} (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 @p p a b -> NatKey
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey

-- | 'natPositions' with the key chosen by the caller, for a weight whose points are addressed by
-- another object's keys. For example a subobject carved out by 'withSubobject', whose inclusion
-- says which point of the ambient object each of its own points is.
natPositionsBy
  :: forall {j} {k} (p :: j +-> k)
   . (Finitary p, FiniteCat j, FiniteCat k)
  => (forall a b. (Ob a, Ob b) => p a b -> NatKey)
  -> M.Map NatKey P.Int
natPositionsBy :: forall {j} {k} (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 forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey
key = [(NatKey, Int)] -> Map NatKey Int
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([NatKey] -> [Int] -> [(NatKey, Int)]
forall a b. [a] -> [b] -> [(a, b)]
P.zip (forall {j} {k} (p :: j +-> k) r.
(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.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain @p @NatKey p a b -> NatKey
forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey
key) [Int
0 ..])

-- | Read a tabulated family back as a function on the points, given those positions.
atNatKey :: M.Map NatKey P.Int -> [v] -> NatKey -> v
atNatKey :: forall v. Map NatKey Int -> [v] -> NatKey -> v
atNatKey Map NatKey Int
pos [v]
row NatKey
k = [v]
row [v] -> Int -> v
forall a. HasCallStack => [a] -> Int -> a
P.!! (Map NatKey Int
pos Map NatKey Int -> NatKey -> Int
forall k a. Ord k => Map k a -> k -> a
M.! NatKey
k)

-- | Every natural transformation @p -> q@, as its list of @q@-indices in 'natDomain' order.
-- Naturality is the only condition: the value at @x@ and the value at @'dimap' g h x@ must agree
-- after transport.
natElements
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => [[Natural]]
natElements :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
natElements =
  [[Natural]]
-> [(Int, Int, Natural -> Natural -> Bool)] -> [[Natural]]
forall v. [[v]] -> [(Int, Int, v -> v -> Bool)] -> [[v]]
familiesSatisfying
    -- the same choice list at every point over one object pair, so @q@\'s size is asked once per pair
    (forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @a -> forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @b -> Natural -> [Natural] -> [[Natural]]
forall i a. Integral i => i -> a -> [a]
genericReplicate (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @p @a @b) (Natural -> [Natural]
indices (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a @b)))
    (forall {j} {k} (p :: j +-> k) (q :: j +-> k) v.
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
([Natural] -> v -> v -> Bool) -> [(Int, Int, v -> v -> Bool)]
forall (p :: j +-> k) (q :: j +-> k) v.
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
([Natural] -> v -> v -> Bool) -> [(Int, Int, v -> v -> Bool)]
natConditions @p @q \[Natural]
tr Natural
i Natural
j -> Natural
j Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== [Natural] -> Natural -> Natural
forall i a. Integral i => [a] -> i -> a
genericIndex [Natural]
tr Natural
i)

-- | The conditions as positions in a tabulated family, with @q@\'s transport handed to the
-- relation. Only the internal hom reads that transport. The sieves below ignore it, and pass
-- 'TerminalProfunctor' for @q@ so that computing it costs nothing.
natConditions
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) v
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => ([Natural] -> v -> v -> P.Bool)
  -> [(P.Int, P.Int, v -> v -> P.Bool)]
natConditions :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) v.
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
([Natural] -> v -> v -> Bool) -> [(Int, Int, v -> v -> Bool)]
natConditions [Natural] -> v -> v -> Bool
rel = [(NatKey -> Int
at NatKey
src, NatKey -> Int
at NatKey
tgt, [Natural] -> v -> v -> Bool
rel [Natural]
tr) | (NatKey
src, NatKey
tgt, [Natural]
tr) <- forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[(NatKey, NatKey, [Natural])]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[(NatKey, NatKey, [Natural])]
natLaws @p @q]
  where
    at :: NatKey -> Int
at = (forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @p Map NatKey Int -> NatKey -> Int
forall k a. Ord k => Map k a -> k -> a
M.!)

-- | The naturality conditions on a transformation. As in 'closedUnder', @'dimap' g h@ is
-- @'lmap' g . 'rmap' h@, so commuting with the two whiskerings separately is commuting with the
-- action. That takes two walks over three objects instead of one over four, and the transport
-- table depends on the arrow alone, not on each element.
natLaws
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => [(NatKey, NatKey, [Natural])]
natLaws :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[(NatKey, NatKey, [Natural])]
natLaws =
  forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k \ @a -> forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @b ->
    let xs :: [p a a]
xs = forall {j} {k} (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; qs :: [q a a]
qs = forall {j} {k} (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 @q @a @b
    in forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @k @(NatKey, NatKey, [Natural])
         ( \ @c -> [(p a a -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey p a a
x, p a a -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey ((a ~> a) -> p a a -> p a a
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> a
g p a a
x), [Natural]
tr) | a ~> a
g <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom k) @c @a, let tr :: [Natural]
tr = (q a a -> Natural) -> [q a a] -> [Natural]
forall a b. (a -> b) -> [a] -> [b]
P.map (q a a -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => q a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex (q a a -> Natural) -> (q a a -> q a a) -> q a a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (a ~> a) -> q a a -> q a a
forall (c :: k) (a :: k) (b :: j). (c ~> a) -> q a b -> q c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> a
g) [q a a]
qs, p a a
x <- [p a a]
xs]
         )
         [(NatKey, NatKey, [Natural])]
-> [(NatKey, NatKey, [Natural])] -> [(NatKey, NatKey, [Natural])]
forall a. [a] -> [a] -> [a]
P.++ forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j @(NatKey, NatKey, [Natural])
           ( \ @d -> [(p a a -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey p a a
x, p a a -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey ((a ~> a) -> p a a -> p a a
forall (b :: j) (d :: j) (a :: k). (b ~> d) -> p a b -> p a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap a ~> a
h p a a
x), [Natural]
tr) | a ~> a
h <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom j) @b @d, let tr :: [Natural]
tr = (q a a -> Natural) -> [q a a] -> [Natural]
forall a b. (a -> b) -> [a] -> [b]
P.map (q a a -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => q a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex (q a a -> Natural) -> (q a a -> q a a) -> q a a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (a ~> a) -> q a a -> q a a
forall (b :: j) (d :: j) (a :: k). (b ~> d) -> q a b -> q a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap a ~> a
h) [q a a]
qs, p a a
x <- [p a a]
xs]
           )

-- | A natural transformation as its table of @q@-indices, in 'natDomain' order. There is nothing
-- else to see of one, so it serves for both comparing and showing.
natTable
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => (p :~> q)
  -> [Natural]
natTable :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
(p :~> q) -> [Natural]
natTable p :~> q
f = forall {j} {k} (p :: j +-> k) r.
(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.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain @p (q a b -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => q a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex (q a b -> Natural) -> (p a b -> q a b) -> p a b -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
P.. p a b -> q a b
p :~> q
f)

-- | Which of the natural transformations @p -> q@ a given one is: 'familyIndex' of its 'natTable' in
-- 'natElements'. The enumeration is bound before the transformation arrives, so a partial
-- application shares it across a hom-set. Every 'toIndex' that numbers transformations uses this.
natIndex
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => P.String
  -> (p :~> q)
  -> Natural
natIndex :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
natIndex String
msg = \p :~> q
f -> String -> [[Natural]] -> [Natural] -> Natural
forall v. Eq v => String -> [[v]] -> [v] -> Natural
familyIndex String
msg [[Natural]]
es (forall {j} {k} (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 @p @q p a b -> q a b
p :~> q
f)
  where
    es :: [[Natural]]
es = forall {j} {k} (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 @p @q

-- | Every natural transformation @p -> q@, as an arrow of @j '+->' k@. With this the category of
-- finitary profunctors, and each of its full subcategories, is testable. Its hom-sets are
-- enumerable, so a generator can pick from them, where in general a natural transformation is not
-- something one can generate.
natTransformations
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => [p ~> q]
natTransformations :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[p ~> q]
natTransformations = let pos :: Map NatKey Int
pos = forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @p in ([Natural] -> Prof p q) -> [[Natural]] -> [Prof p q]
forall a b. (a -> b) -> [a] -> [b]
P.map (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
Map NatKey Int -> [Natural] -> p ~> q
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
Map NatKey Int -> [Natural] -> p ~> q
natAt @p @q Map NatKey Int
pos) (forall {j} {k} (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 @p @q)

-- | A tabulated transformation, as an arrow of @j '+->' k@.
natAt
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k)
  => M.Map NatKey P.Int
  -> [Natural]
  -> p ~> q
natAt :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
Map NatKey Int -> [Natural] -> p ~> q
natAt Map NatKey Int
pos [Natural]
row = (p :~> q) -> Prof p q
forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \p a b
x -> p a b
x p a b -> ((Ob a, Ob b) => q a b) -> q a b
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// forall {j} {k} (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 @q (Map NatKey Int -> [Natural] -> NatKey -> Natural
forall v. Map NatKey Int -> [v] -> NatKey -> v
atNatKey Map NatKey Int
pos [Natural]
row (p a b -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey p a b
x))

-- | @'Finitary' p@ as a class with a single instance, so that a quantified constraint can ask for
-- it without 'Finitary' being the head. 'subFinitary' hands it back as an ordinary given. The
-- instance below says what this is for. 'Proarrow.Optic.Sub' is the same device for flavors, and
-- documents the GHC restriction behind it at more length, including why neither of them carries
-- the constraint it wraps as a superclass.
type SubFinitary :: forall {j} {k}. (j +-> k) -> Constraint
class SubFinitary p where
  subFinitary :: ((Finitary p) => r) -> r

instance (Finitary p) => SubFinitary p where
  subFinitary :: forall r. (Finitary p => r) -> r
subFinitary Finitary p => r
r = r
Finitary p => r
r

-- | @'FINITARY' j k@ is locally finite: its own hom-profunctor is finitary, by 'natTransformations',
-- so the numbering is the skeleton of each hom-set and the 'Finitary' laws apply to it. (It is not
-- a 'FiniteCat': there are unboundedly many finitary profunctors.)
--
-- The same holds for any full subcategory whose predicate implies 'Finitary', such as the sheaves
-- of "Proarrow.Category.Enriched.Finitary.Sheaf". The premise goes through 'SubFinitary' because a
-- bare @forall p. ob p => 'Finitary' p@ cannot be discharged for a conjunction such as
-- @'Finitary' :&&: 'Sheaf' t@: GHC will not solve the head from a superclass that is not smaller.
instance
  (FiniteCat j, FiniteCat k, forall p. (ob p) => SubFinitary p)
  => Finitary (Sub Prof :: CAT (SUBCAT (ob :: OB (j +-> k))))
  where
  size :: forall (a :: SUBCAT ob) (b :: SUBCAT ob). (Ob a, Ob b) => Natural
size @f @g = forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB f) ((Finitary (UN SUB a) => Natural) -> Natural)
-> (Finitary (UN SUB a) => Natural) -> Natural
forall a b. (a -> b) -> a -> b
$ forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB g) ((Finitary (UN SUB b) => Natural) -> Natural)
-> (Finitary (UN SUB b) => Natural) -> Natural
forall a b. (a -> b) -> a -> b
$ [[Natural]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall {j} {k} (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 @(UN SUB f) @(UN SUB g))
  toIndex :: forall (a :: SUBCAT ob) (b :: SUBCAT ob).
(Ob a, Ob b) =>
Sub Prof a b -> Natural
toIndex @f @g =
    forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB f) ((Finitary (UN SUB a) => Sub Prof a b -> Natural)
 -> Sub Prof a b -> Natural)
-> (Finitary (UN SUB a) => Sub Prof a b -> Natural)
-> Sub Prof a b
-> Natural
forall a b. (a -> b) -> a -> b
$
      forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB g) ((Finitary (UN SUB b) => Sub Prof a b -> Natural)
 -> Sub Prof a b -> Natural)
-> (Finitary (UN SUB b) => Sub Prof a b -> Natural)
-> Sub Prof a b
-> Natural
forall a b. (a -> b) -> a -> b
$
        -- bound before the argument lambda, so a partial application shares the enumeration
        let ix :: (UN SUB a :~> UN SUB b) -> Natural
ix = forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
natIndex @(UN SUB f) @(UN SUB g) String
"toIndex: the transformation is not natural"
        in \(Sub (Prof a1 :~> b1
n)) -> (UN SUB a :~> UN SUB b) -> Natural
ix a1 a b -> b1 a b
UN SUB a a b -> UN SUB b a b
a1 :~> b1
UN SUB a :~> UN SUB b
n
  fromIndex :: forall (a :: SUBCAT ob) (b :: SUBCAT ob).
(Ob a, Ob b) =>
Natural -> Sub Prof a b
fromIndex @f @g Natural
i =
    forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB f) ((Finitary (UN SUB a) => Sub Prof a b) -> Sub Prof a b)
-> (Finitary (UN SUB a) => Sub Prof a b) -> Sub Prof a b
forall a b. (a -> b) -> a -> b
$
      forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB g) ((Finitary (UN SUB b) => Sub Prof a b) -> Sub Prof a b)
-> (Finitary (UN SUB b) => Sub Prof a b) -> Sub Prof a b
forall a b. (a -> b) -> a -> b
$
        Prof (UN SUB a) (UN SUB b)
-> Sub Prof (SUB (UN SUB a)) (SUB (UN SUB b))
forall {k} (ob :: OB k) (a1 :: k) (b1 :: k) (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
Map NatKey Int -> [Natural] -> p ~> q
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
Map NatKey Int -> [Natural] -> p ~> q
natAt @(UN SUB f) @(UN SUB g) (forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @(UN SUB f)) ([[Natural]] -> Natural -> [Natural]
forall i a. Integral i => [a] -> i -> a
genericIndex (forall {j} {k} (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 @(UN SUB f) @(UN SUB g)) Natural
i))
  elements :: forall (a :: SUBCAT ob) (b :: SUBCAT ob).
(Ob a, Ob b) =>
[Sub Prof a b]
elements @f @g = forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB f) ((Finitary (UN SUB a) => [Sub Prof a b]) -> [Sub Prof a b])
-> (Finitary (UN SUB a) => [Sub Prof a b]) -> [Sub Prof a b]
forall a b. (a -> b) -> a -> b
$ forall {j} {k} (p :: j +-> k) r.
SubFinitary p =>
(Finitary p => r) -> r
forall (p :: j +-> k) r. SubFinitary p => (Finitary p => r) -> r
subFinitary @(UN SUB g) ((Finitary (UN SUB b) => [Sub Prof a b]) -> [Sub Prof a b])
-> (Finitary (UN SUB b) => [Sub Prof a b]) -> [Sub Prof a b]
forall a b. (a -> b) -> a -> b
$ (Prof (UN SUB a) (UN SUB b) -> Sub Prof a b)
-> [Prof (UN SUB a) (UN SUB b)] -> [Sub Prof a b]
forall a b. (a -> b) -> [a] -> [b]
P.map Prof (UN SUB a) (UN SUB b) -> Sub Prof a b
Prof (UN SUB a) (UN SUB b)
-> Sub Prof (SUB (UN SUB a)) (SUB (UN SUB b))
forall {k} (ob :: OB k) (a1 :: k) (b1 :: k) (p :: CAT k).
(ob a1, ob b1) =>
p a1 b1 -> Sub p (SUB a1) (SUB b1)
Sub (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[p ~> q]
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[p ~> q]
natTransformations @(UN SUB f) @(UN SUB g))

-- | What the internal hom at @a@\/@b@ is a set of natural transformations /out of/. An element of
-- it over @c@\/@d@ is an arrow into @a@, an arrow out of @b@ and an element of @p@, the three
-- arguments an 'Exp' takes.
type ExpWeight :: forall {j} {k}. (j +-> k) -> k -> j -> j +-> k
type ExpWeight p a b = Yo a (OP b) :*: p

-- | The internal hom of finitary profunctors is finitary: its elements are the natural
-- transformations out of 'ExpWeight', enumerated. The count is not a formula in the sizes of @p@
-- and @q@, since it depends on how the arrows of @j@ and @k@ compose. So 'size' is a value and
-- not a type family.
instance (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => Finitary (p :~>: q :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [[Natural]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall {j} {k} (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 @(ExpWeight p a b) @q)

  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => (:~>:) p q a b -> Natural
toIndex @a @b = \(Exp forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> p c d -> q c d
f) -> (ExpWeight p a b :~> q) -> Natural
ix \(Yo a ~> a
ca b1 ~> b
bd :*: p a b
x) -> (a ~> a) -> (b ~> b) -> p a b -> q a b
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> p c d -> q c d
f a ~> a
ca b ~> b
b1 ~> b
bd p a b
x
    where
      ix :: (ExpWeight p a b :~> q) -> Natural
ix = forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
forall (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
natIndex @(ExpWeight p a b) @q String
"toIndex: the family is not natural"
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> (:~>:) p q a b
fromIndex @a @b Natural
i = forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> (:~>:) p q a b
forall (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> (:~>:) p q a b
expAt @p @q (forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @(ExpWeight p a b)) ([[Natural]] -> Natural -> [Natural]
forall i a. Integral i => [a] -> i -> a
genericIndex (forall {j} {k} (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 @(ExpWeight p a b) @q) Natural
i)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [(:~>:) p q a b]
elements @a @b =
    let pos :: Map NatKey Int
pos = forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @(ExpWeight p a b) in ([Natural] -> (:~>:) p q a b) -> [[Natural]] -> [(:~>:) p q a b]
forall a b. (a -> b) -> [a] -> [b]
P.map (forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> (:~>:) p q a b
forall (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> (:~>:) p q a b
expAt @p @q Map NatKey Int
pos) (forall {j} {k} (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 @(ExpWeight p a b) @q)

-- | A tabulated family as an element of the internal hom.
expAt
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j)
   . (Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b)
  => M.Map NatKey P.Int
  -> [Natural]
  -> (p :~>: q) a b
expAt :: forall {j} {k} (p :: j +-> k) (q :: j +-> k) (a :: k) (b :: j).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> (:~>:) p q a b
expAt Map NatKey Int
pos [Natural]
row = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> p c d -> q c d)
-> (:~>:) p q a b
forall {k} {k1} (a :: k) (b :: k1) (p :: k -> k1 -> Type)
       (q :: k -> k1 -> Type).
(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
ca b ~> d
bd p c d
x -> c ~> a
ca (c ~> a) -> ((Ob c, Ob a) => q c d) -> q c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
bd (b ~> d) -> ((Ob b, Ob d) => q c d) -> q c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// forall {j} {k} (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 @q (Map NatKey Int -> [Natural] -> NatKey -> Natural
forall v. Map NatKey Int -> [v] -> NatKey -> v
atNatKey Map NatKey Int
pos [Natural]
row ((:*:) (Yo a (OP b)) p c d -> NatKey
forall {j} {k} (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} {j} (c :: k) (a :: k) (b1 :: j) (d :: j).
(c ~> a) -> (b1 ~> d) -> Yo a (OP b1) c d
Yo c ~> a
ca b ~> d
bd Yo a (OP b) c d -> p c d -> (:*:) (Yo a (OP b)) p c d
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) (q :: j +-> k).
p a b -> q a b -> (:*:) p q a b
:*: p c d
x)))

-- | What the right Kan lift @'Rift' ('OP' j) p@ at @a@\/@b@ is a set of natural transformations out
-- of. An element of @'Rift' ('OP' j) p a b@ is a function @forall x. j x a -> p x b@, and by Yoneda
-- that is a natural transformation from @j (-) a × (b ~> -)@ to @p@.
type RiftWeight :: forall {i} {j} {k}. (k +-> i) -> k -> j -> j +-> i
data RiftWeight w a b x d where
  RiftWeight :: (Ob x, Ob d) => w x a -> b ~> d -> RiftWeight w a b x d

instance (Profunctor w, CategoryOf j) => Profunctor (RiftWeight w a (b :: j)) where
  dimap :: forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a)
-> (b ~> d) -> RiftWeight w a b a b -> RiftWeight w a b c d
dimap c ~> a
f b ~> d
g (RiftWeight w a a
u b ~> b
h) = c ~> a
f (c ~> a)
-> ((Ob c, Ob a) => RiftWeight w a b c d) -> RiftWeight w a b c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
g (b ~> d)
-> ((Ob b, Ob d) => RiftWeight w a b c d) -> RiftWeight w a b c d
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// w c a -> (b ~> d) -> RiftWeight w a b c d
forall {i} {k} {k} (x :: i) (d :: k) (w :: k +-> i) (a :: k)
       (b :: k).
(Ob x, Ob d) =>
w x a -> (b ~> d) -> RiftWeight w a b x d
RiftWeight ((c ~> a) -> w a a -> w c a
forall (c :: k) (a :: k) (b :: k). (c ~> a) -> w a b -> w c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap c ~> a
f w a a
u) (b ~> d
g (b ~> d) -> (b ~> b) -> b ~> d
forall (b :: j) (c :: j) (a :: j). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. b ~> b
h)
  (Ob a, Ob b) => r
r \\ :: forall (a :: k) (b :: j) r.
((Ob a, Ob b) => r) -> RiftWeight w a b a b -> r
\\ RiftWeight{} = r
(Ob a, Ob b) => r
r

instance (Finitary w, LocallyFinite j, Ob a, Ob b) => Finitary (RiftWeight w a (b :: j)) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @x @d = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
Natural
size @w @x @a Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.* forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Hom j) @b @d
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
RiftWeight w a b a b -> Natural
toIndex @_ @d (RiftWeight w a a
u b ~> b
h) = Natural -> Natural -> Natural -> Natural
pairIndex (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Hom j) @b @d) (w a a -> Natural
forall (a :: k) (b :: k). (Ob a, Ob b) => w a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex w a a
u) ((b ~> b) -> Natural
forall (a :: j) (b :: j). (Ob a, Ob b) => (a ~> b) -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex b ~> b
h)
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> RiftWeight w a b a b
fromIndex @_ @d Natural
i = let (Natural
l, Natural
r) = Natural -> Natural -> (Natural, Natural)
unpairIndex (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Hom j) @b @d) Natural
i in w a a -> (b ~> b) -> RiftWeight w a b a b
forall {i} {k} {k} (x :: i) (d :: k) (w :: k +-> i) (a :: k)
       (b :: k).
(Ob x, Ob d) =>
w x a -> (b ~> d) -> RiftWeight w a b x d
RiftWeight (Natural -> w a a
forall (a :: k) (b :: k). (Ob a, Ob b) => Natural -> w a b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex Natural
l) (Natural -> b ~> b
forall (a :: j) (b :: j). (Ob a, Ob b) => Natural -> a ~> b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex Natural
r)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [RiftWeight w a b a b]
elements @x @d = [w a a -> (b ~> b) -> RiftWeight w a b a b
forall {i} {k} {k} (x :: i) (d :: k) (w :: k +-> i) (a :: k)
       (b :: k).
(Ob x, Ob d) =>
w x a -> (b ~> d) -> RiftWeight w a b x d
RiftWeight w a a
u b ~> b
h | w a a
u <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @w @x @a, b ~> b
h <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom j) @b @d]

-- | The right Kan lift of finitary profunctors is finitary: its elements are the natural
-- transformations out of 'RiftWeight', enumerated, as for the internal hom.
instance
  (Finitary w, Finitary p, FiniteCat i, FiniteCat j)
  => Finitary (Rift (OP (w :: k +-> i)) p :: j +-> k)
  where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [[Natural]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
forall (p :: j +-> i) (q :: j +-> i).
(Finitary p, Finitary q, FiniteCat j, FiniteCat i) =>
[[Natural]]
natElements @(RiftWeight w a b) @p)
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Rift (OP w) p a b -> Natural
toIndex @a @b = \(Rift forall (x :: i). j2 x a -> p x b
f) -> (RiftWeight w a b :~> p) -> Natural
ix \(RiftWeight w a a
u b ~> b
h) -> (b ~> b) -> p a b -> p a b
forall (b :: j) (d :: j) (a :: i). (b ~> d) -> p a b -> p a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap b ~> b
h (j2 a a -> p a b
forall (x :: i). j2 x a -> p x b
f w a a
j2 a a
u)
    where
      ix :: (RiftWeight w a b :~> p) -> Natural
ix = forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
String -> (p :~> q) -> Natural
forall (p :: j +-> i) (q :: j +-> i).
(Finitary p, Finitary q, FiniteCat j, FiniteCat i) =>
String -> (p :~> q) -> Natural
natIndex @(RiftWeight w a b) @p String
"toIndex: the family is not natural"
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> Rift (OP w) p a b
fromIndex @a @b Natural
i = forall {i} {j} {k} (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j).
(Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> Rift (OP w) p a b
forall (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j).
(Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> Rift (OP w) p a b
riftAt @w @p (forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> i).
(Finitary p, FiniteCat j, FiniteCat i) =>
Map NatKey Int
natPositions @(RiftWeight w a b)) ([[Natural]] -> Natural -> [Natural]
forall i a. Integral i => [a] -> i -> a
genericIndex (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
forall (p :: j +-> i) (q :: j +-> i).
(Finitary p, Finitary q, FiniteCat j, FiniteCat i) =>
[[Natural]]
natElements @(RiftWeight w a b) @p) Natural
i)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Rift (OP w) p a b]
elements @a @b =
    let pos :: Map NatKey Int
pos = forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> i).
(Finitary p, FiniteCat j, FiniteCat i) =>
Map NatKey Int
natPositions @(RiftWeight w a b) in ([Natural] -> Rift (OP w) p a b)
-> [[Natural]] -> [Rift (OP w) p a b]
forall a b. (a -> b) -> [a] -> [b]
P.map (forall {i} {j} {k} (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j).
(Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> Rift (OP w) p a b
forall (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j).
(Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> Rift (OP w) p a b
riftAt @w @p Map NatKey Int
pos) (forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
[[Natural]]
forall (p :: j +-> i) (q :: j +-> i).
(Finitary p, Finitary q, FiniteCat j, FiniteCat i) =>
[[Natural]]
natElements @(RiftWeight w a b) @p)

-- | The composite of finitary profunctors over a finite middle category is finitary. An element
-- at @a@\/@c@ is a pair @(u, v)@ over some middle object @x@, and pairs are identified along the
-- arrows of the middle category: @(rmap f u, v) = (u, lmap f v)@, the coend
-- @∫^x w a x × s x c@. The classes are computed by 'classes' and numbered in order, each shown by
-- its first pair.
instance (Finitary w, Finitary s, FiniteCat j) => Finitary ((w :: j +-> k) :.: (s :: i +-> j)) where
  size :: forall (a :: k) (b :: i). (Ob a, Ob b) => Natural
size @a @c = [[Natural]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
compClasses @w @s @a @c)
  toIndex :: forall (a :: k) (b :: i). (Ob a, Ob b) => (:.:) w s a b -> Natural
toIndex @a @c = \(w a b
u :.: s b b
v) -> w a b
u w a b -> ((Ob a, Ob b) => Natural) -> Natural
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// String -> [[Natural]] -> Natural -> Natural
classIndex String
"toIndex: a pair in no class" [[Natural]]
cls (forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
       (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i) (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
compIndex @w @s @a @c [Natural]
offs w a b
u s b b
v)
    where
      offs :: [Natural]
offs = forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[Natural]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[Natural]
compOffsets @w @s @a @c
      cls :: [[Natural]]
cls = forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
compClasses @w @s @a @c
  fromIndex :: forall (a :: k) (b :: i). (Ob a, Ob b) => Natural -> (:.:) w s a b
fromIndex @a @c Natural
n = [(:.:) w s a b] -> Natural -> (:.:) w s a b
forall i a. Integral i => [a] -> i -> a
genericIndex (forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[(:.:) w s a c]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[(:.:) w s a c]
compPairs @w @s @a @c) (String -> [[Natural]] -> Natural -> Natural
classRep String
"fromIndex: an empty class" (forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
compClasses @w @s @a @c) Natural
n)
  elements :: forall (a :: k) (b :: i). (Ob a, Ob b) => [(:.:) w s a b]
elements @a @c = let ps :: [(:.:) w s a b]
ps = forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[(:.:) w s a c]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[(:.:) w s a c]
compPairs @w @s @a @c in [[(:.:) w s a b] -> Natural -> (:.:) w s a b
forall i a. Integral i => [a] -> i -> a
genericIndex [(:.:) w s a b]
ps Natural
n | Natural
n : [Natural]
_ <- forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
compClasses @w @s @a @c]

-- | Every pair @(u, v)@ over every middle object, numbered as 'compIndex' numbers them.
compPairs
  :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
   . (Finitary w, Finitary s, FiniteCat j, Ob a, Ob c)
  => [(w :.: s) a c]
compPairs :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[(:.:) w s a c]
compPairs = forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @x -> [w a a
u w a a -> s a c -> (:.:) w s a c
forall {j} {k} {i} (b :: j) (a :: k) (c :: i) (p :: j +-> k)
       (q :: i +-> j).
p a b -> q b c -> (:.:) p q a c
:.: s a c
v | w a a
u <- forall {j} {k} (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 @w @a @x, s a c
v <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: i +-> j) (a :: j) (b :: i).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @s @x @c]

-- | Where each middle object's pairs start in the numbering of 'compPairs'.
compOffsets
  :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
   . (Finitary w, Finitary s, FiniteCat j, Ob a, Ob c)
  => [Natural]
compOffsets :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[Natural]
compOffsets = (Natural -> Natural -> Natural)
-> Natural -> [Natural] -> [Natural]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
P.scanl Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
(P.+) Natural
0 (forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @x -> [forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @w @a @x Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.* forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: i +-> j) (a :: j) (b :: i).
(Finitary p, Ob a, Ob b) =>
Natural
size @s @x @c])

-- | The position of a pair over @x@ in 'compPairs'.
compIndex
  :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i) (x :: j)
   . (Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x)
  => [Natural]
  -> w a x
  -> s x c
  -> Natural
compIndex :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
       (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
compIndex [Natural]
offs w a x
u s x c
v = [Natural] -> Natural -> Natural
forall i a. Integral i => [a] -> i -> a
genericIndex [Natural]
offs (forall (a :: j). (Enumerable j, Ob a) => Natural
forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex @x) Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.+ Natural -> Natural -> Natural -> Natural
pairIndex (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: i +-> j) (a :: j) (b :: i).
(Finitary p, Ob a, Ob b) =>
Natural
size @s @x @c) (w a x -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => w a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex w a x
u) (s x c -> Natural
forall (a :: j) (b :: i). (Ob a, Ob b) => s a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex s x c
v)

-- | The classes of pairs under the identifications along the middle arrows.
compClasses
  :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
   . (Finitary w, Finitary s, FiniteCat j, Ob a, Ob c)
  => [[Natural]]
compClasses :: forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[[Natural]]
compClasses =
  [(Natural, Natural)] -> [Natural] -> [[Natural]]
classes
    ( forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @x -> forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb @j \ @x' ->
        [ (forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
       (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i) (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
compIndex @w @s @a @c [Natural]
offs ((a ~> a) -> w a a -> w a a
forall (b :: j) (d :: j) (a :: k). (b ~> d) -> w a b -> w a d
forall {j} {k} (p :: j +-> k) (b :: j) (d :: j) (a :: k).
Profunctor p =>
(b ~> d) -> p a b -> p a d
rmap a ~> a
f w a a
u) s a c
v, forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i)
       (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i) (x :: j).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c, Ob x) =>
[Natural] -> w a x -> s x c -> Natural
compIndex @w @s @a @c [Natural]
offs w a a
u ((a ~> a) -> s a c -> s a c
forall (c :: j) (a :: j) (b :: i). (c ~> a) -> s a b -> s c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap a ~> a
f s a c
v))
        | a ~> a
f <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j +-> j) (a :: j) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Hom j) @x @x'
        , w a a
u <- forall {j} {k} (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 @w @a @x
        , s a c
v <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: i +-> j) (a :: j) (b :: i).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @s @x' @c
        ]
    )
    (Natural -> [Natural]
indices ([Natural] -> Natural
forall a. HasCallStack => [a] -> a
P.last [Natural]
offs))
  where
    offs :: [Natural]
offs = forall {i} {j} {k} (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[Natural]
forall (w :: j +-> k) (s :: i +-> j) (a :: k) (c :: i).
(Finitary w, Finitary s, FiniteCat j, Ob a, Ob c) =>
[Natural]
compOffsets @w @s @a @c

-- | The right Kan extension of finitary profunctors is finitary. It is the right Kan lift in the
-- opposite categories, @'Ran' ('OP' v) p a b ≅ 'Rift' ('OP' ('Op' v)) ('Op' p) ('OP' b) ('OP' a)@,
-- and is numbered as that is.
instance
  (Finitary v, Finitary p, FiniteCat i, FiniteCat k)
  => Finitary (Ran (OP (v :: i +-> j)) p :: j +-> k)
  where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: OPPOSITE k +-> OPPOSITE j) (a :: OPPOSITE j)
       (b :: OPPOSITE k).
(Finitary p, Ob a, Ob b) =>
Natural
size @(Rift (OP (Op v)) (Op p)) @(OP b) @(OP a)
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Ran (OP v) p a b -> Natural
toIndex @a @b (Ran forall (x :: i). j2 b x -> p a x
f) = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
forall (p :: OPPOSITE k +-> OPPOSITE j) (a :: OPPOSITE j)
       (b :: OPPOSITE k).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex @(Rift (OP (Op v)) (Op p)) @(OP b) @(OP a) ((forall (x :: OPPOSITE i). Op v x (OP b) -> Op p x (OP a))
-> Rift (OP (Op v)) (Op p) (OP b) (OP a)
forall {k} {j} {i} (a :: k) (b :: j) (j2 :: k +-> i)
       (p :: j +-> i).
(Ob a, Ob b) =>
(forall (x :: i). j2 x a -> p x b) -> Rift (OP j2) p a b
Rift \(Op v b1 a1
u) -> p a a1 -> Op p (OP a1) (OP a)
forall {j} {k} (p :: j +-> k) (b1 :: k) (a1 :: j).
p b1 a1 -> Op p (OP a1) (OP b1)
Op (j2 b a1 -> p a a1
forall (x :: i). j2 b x -> p a x
f v b1 a1
j2 b a1
u))
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> Ran (OP v) p a b
fromIndex @a @b Natural
i = case forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
forall (p :: OPPOSITE k +-> OPPOSITE j) (a :: OPPOSITE j)
       (b :: OPPOSITE k).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex @(Rift (OP (Op v)) (Op p)) @(OP b) @(OP a) Natural
i of Rift forall (x :: OPPOSITE i). j2 x (OP b) -> Op p x (OP a)
k -> (forall (x :: i). v b x -> p a x) -> Ran (OP v) p a b
forall {k} {j} {i} (a :: k) (b :: j) (j2 :: i +-> j)
       (p :: i +-> k).
(Ob a, Ob b) =>
(forall (x :: i). j2 b x -> p a x) -> Ran (OP j2) p a b
Ran \v b x
u -> Op p (OP x) (OP a) -> p a x
forall {j} {k} (p :: j +-> k) (b :: k) (a :: j).
Op p (OP a) (OP b) -> p b a
unOp (j2 (OP x) (OP b) -> Op p (OP x) (OP a)
forall (x :: OPPOSITE i). j2 x (OP b) -> Op p x (OP a)
k (v b x -> Op v (OP x) (OP b)
forall {j} {k} (p :: j +-> k) (b1 :: k) (a1 :: j).
p b1 a1 -> Op p (OP a1) (OP b1)
Op v b x
u))
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Ran (OP v) p a b]
elements @a @b = [(forall (x :: i). v b x -> p a x) -> Ran (OP v) p a b
forall {k} {j} {i} (a :: k) (b :: j) (j2 :: i +-> j)
       (p :: i +-> k).
(Ob a, Ob b) =>
(forall (x :: i). j2 b x -> p a x) -> Ran (OP j2) p a b
Ran \v b x
u -> Op p (OP x) (OP a) -> p a x
forall {j} {k} (p :: j +-> k) (b :: k) (a :: j).
Op p (OP a) (OP b) -> p b a
unOp (j2 (OP x) (OP b) -> Op p (OP x) (OP a)
forall (x :: OPPOSITE i). j2 x (OP b) -> Op p x (OP a)
k (v b x -> Op v (OP x) (OP b)
forall {j} {k} (p :: j +-> k) (b1 :: k) (a1 :: j).
p b1 a1 -> Op p (OP a1) (OP b1)
Op v b x
u)) | Rift forall (x :: OPPOSITE i). j2 x (OP b) -> Op p x (OP a)
k <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: OPPOSITE k +-> OPPOSITE j) (a :: OPPOSITE j)
       (b :: OPPOSITE k).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @(Rift (OP (Op v)) (Op p)) @(OP b) @(OP a)]

-- | A tabulated family as an element of the right Kan lift.
riftAt
  :: forall {i} {j} {k} (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j)
   . (Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b)
  => M.Map NatKey P.Int
  -> [Natural]
  -> Rift (OP w) p a b
riftAt :: forall {i} {j} {k} (w :: k +-> i) (p :: j +-> i) (a :: k) (b :: j).
(Finitary w, Finitary p, FiniteCat i, FiniteCat j, Ob a, Ob b) =>
Map NatKey Int -> [Natural] -> Rift (OP w) p a b
riftAt Map NatKey Int
pos [Natural]
row = (forall (x :: i). w x a -> p x b) -> Rift (OP w) p a b
forall {k} {j} {i} (a :: k) (b :: j) (j2 :: k +-> i)
       (p :: j +-> i).
(Ob a, Ob b) =>
(forall (x :: i). j2 x a -> p x b) -> Rift (OP j2) p a b
Rift \w x a
u -> w x a
u w x a -> ((Ob x, Ob a) => p x b) -> p x b
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
forall (p :: j +-> i) (a :: i) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural -> p a b
fromIndex @p (Map NatKey Int -> [Natural] -> NatKey -> Natural
forall v. Map NatKey Int -> [v] -> NatKey -> v
atNatKey Map NatKey Int
pos [Natural]
row (RiftWeight w a b x b -> NatKey
forall {j} {k} (a :: k) (b :: j) (p :: j +-> k).
(FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) =>
p a b -> NatKey
natKey (w x a -> (b ~> b) -> RiftWeight w a b x b
forall {i} {k} {k} (x :: i) (d :: k) (w :: k +-> i) (a :: k)
       (b :: k).
(Ob x, Ob d) =>
w x a -> (b ~> d) -> RiftWeight w a b x d
RiftWeight w x a
u (forall (a :: j). (CategoryOf j, Ob a) => Obj a
forall {k} (a :: k). (CategoryOf k, Ob a) => Obj a
obj @b))))

-- Finitary profunctors are cartesian closed, and the sheaves are too, by the instance for any
-- full subcategory closed under the internal hom in "Proarrow.Profunctor.Instance.Exponential".
-- Here that is @'Finitary' (p ':~>:' q)@ just above, where the hom-set is the natural
-- transformations, enumerated.

-- * The subobject classifier

-- | Every sieve at @a@\/@b@, as the points of @'Yo' a ('OP' b)@ it contains, in 'natDomain' order:
-- all subsets, kept when closed. This is the same end again, at the weight @'Yo' a ('OP' b)@ and
-- valued in booleans, with the naturality conditions read as implications instead of equations.
sieveElements :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k, Ob a, Ob b) => [[P.Bool]]
sieveElements :: forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
sieveElements =
  [[Bool]] -> [(Int, Int, Bool -> Bool -> Bool)] -> [[Bool]]
forall v. [[v]] -> [(Int, Int, v -> v -> Bool)] -> [[v]]
familiesSatisfying
    (forall {j} {k} (p :: j +-> k) r.
(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.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain @(Yo a (OP b)) ([Bool] -> Yo a (OP b) a b -> [Bool]
forall a b. a -> b -> a
P.const [Bool
P.False, Bool
P.True]))
    (forall {j} {k} (p :: j +-> k) (q :: j +-> k) v.
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
([Natural] -> v -> v -> Bool) -> [(Int, Int, v -> v -> Bool)]
forall (p :: j +-> k) (q :: j +-> k) v.
(Finitary p, Finitary q, FiniteCat j, FiniteCat k) =>
([Natural] -> v -> v -> Bool) -> [(Int, Int, v -> v -> Bool)]
natConditions @(Yo a (OP b)) @TerminalProfunctor \[Natural]
_ Bool
s Bool
t -> Bool -> Bool
P.not Bool
s Bool -> Bool -> Bool
P.|| Bool
t)

-- | A sieve as the tabulation of its membership, in 'natDomain' order. The inverse of 'sieveAt'.
sieveTable :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k) => Sieve a b -> [P.Bool]
sieveTable :: forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable (Sieve forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s) = forall {j} {k} (p :: j +-> k) r.
(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.
(Finitary p, FiniteCat j, FiniteCat k) =>
(forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r]
natDomain @(Yo a (OP b)) \(Yo a ~> a
ca b1 ~> b
bd) -> (a ~> a) -> (b ~> b) -> Bool
forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool
s a ~> a
ca b ~> b
b1 ~> b
bd

instance (FiniteCat j, FiniteCat k) => Finitary (Sieve :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = [[Bool]] -> Natural
forall i a. Num i => [a] -> i
genericLength (forall (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
sieveElements @a @b)
  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Sieve a b -> Natural
toIndex @a @b = String -> [[Bool]] -> [Bool] -> Natural
forall v. Eq v => String -> [[v]] -> [v] -> Natural
familyIndex String
"toIndex: not a sieve" (forall (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
sieveElements @a @b) ([Bool] -> Natural)
-> (Sieve a b -> [Bool]) -> Sieve a b -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. Sieve a b -> [Bool]
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k) =>
Sieve a b -> [Bool]
sieveTable
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Sieve a b
fromIndex @a @b Natural
i = Map NatKey Int -> [Bool] -> Sieve a b
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Bool] -> Sieve a b
sieveAt (forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @(Yo a (OP b))) ([[Bool]] -> Natural -> [Bool]
forall i a. Integral i => [a] -> i -> a
genericIndex (forall (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
sieveElements @a @b) Natural
i)
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Sieve a b]
elements @a @b = let pos :: Map NatKey Int
pos = forall {j} {k} (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
forall (p :: j +-> k).
(Finitary p, FiniteCat j, FiniteCat k) =>
Map NatKey Int
natPositions @(Yo a (OP b)) in ([Bool] -> Sieve a b) -> [[Bool]] -> [Sieve a b]
forall a b. (a -> b) -> [a] -> [b]
P.map (Map NatKey Int -> [Bool] -> Sieve a b
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Bool] -> Sieve a b
sieveAt Map NatKey Int
pos) (forall (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
[[Bool]]
sieveElements @a @b)

-- | A tabulated sieve as a sieve.
sieveAt
  :: forall {j} {k} (a :: k) (b :: j)
   . (FiniteCat j, FiniteCat k, Ob a, Ob b)
  => M.Map NatKey P.Int
  -> [P.Bool]
  -> Sieve a b
sieveAt :: forall {j} {k} (a :: k) (b :: j).
(FiniteCat j, FiniteCat k, Ob a, Ob b) =>
Map NatKey Int -> [Bool] -> Sieve a b
sieveAt Map NatKey Int
pos [Bool]
row = (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k} {j} (a :: k) (b :: j).
(Ob a, Ob b) =>
(forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
Sieve \c ~> a
ca b ~> d
bd -> c ~> a
ca (c ~> a) -> ((Ob c, Ob a) => Bool) -> Bool
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
bd (b ~> d) -> ((Ob b, Ob d) => Bool) -> Bool
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// Map NatKey Int -> [Bool] -> NatKey -> Bool
forall v. Map NatKey Int -> [v] -> NatKey -> v
atNatKey Map NatKey Int
pos [Bool]
row (Yo a (OP b) c d -> NatKey
forall {j} {k} (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} {j} (c :: k) (a :: k) (b1 :: j) (d :: j).
(c ~> a) -> (b1 ~> d) -> Yo a (OP b1) c d
Yo c ~> a
ca b ~> d
bd))

-- | All the ways an element of @p@ and one of @q@ can be carried to a matching pair: the sieve an
-- arrow's graph is classified by. Shared with the sheaves, whose classifier is this closed.
graphSieve
  :: forall {j} {k} (p :: j +-> k) (q :: j +-> k)
   . (Profunctor p, Finitary q)
  => (p :~> q) -> (p :*: q) :~> Sieve
graphSieve :: forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Finitary q) =>
(p :~> q) -> (p :*: q) :~> Sieve
graphSieve p :~> q
n (p a b
x :*: q a b
y) = p a b
x p a b -> ((Ob a, Ob b) => Sieve a b) -> Sieve a b
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// (forall (c :: k) (d :: j). (c ~> a) -> (b ~> d) -> Bool)
-> Sieve a b
forall {k} {j} (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} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// b ~> d
h (b ~> d) -> ((Ob b, Ob d) => Bool) -> Bool
forall {k1} {k2} (p :: k1 +-> k2) (a :: k2) (b :: k1) r.
Profunctor p =>
p a b -> ((Ob a, Ob b) => r) -> r
// forall {j} {k} (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 @q (p c d -> q c d
p :~> q
n ((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} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
g b ~> d
h p a b
x)) Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== q c d -> Natural
forall (a :: k) (b :: j). (Ob a, Ob b) => q a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex ((c ~> a) -> (b ~> d) -> q a b -> q c d
forall (c :: k) (a :: k) (b :: j) (d :: j).
(c ~> a) -> (b ~> d) -> q a b -> q c d
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap c ~> a
g b ~> d
h q a b
y)

-- | The subobject classifier is the profunctor of sieves, and an arrow classifies its graph.
instance (FiniteCat j, FiniteCat k) => HasSubobjectClassifier (PROD (FINITARY j k)) where
  type Omega = PR (SUB Sieve)
  true :: TerminalObject ~> Omega
true = Sub Prof (SUB TerminalProfunctor) (SUB Sieve)
-> Prod (Sub Prof) (PR (SUB TerminalProfunctor)) (PR (SUB Sieve))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (Prof TerminalProfunctor Sieve
-> Sub Prof (SUB TerminalProfunctor) (SUB Sieve)
forall {k} (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 :~> Sieve) -> Prof TerminalProfunctor Sieve
forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof \TerminalProfunctor a b
TerminalProfunctor -> Sieve a b
forall {j} {k} (a :: k) (b :: j).
(CategoryOf j, CategoryOf k, Ob a, Ob b) =>
Sieve a b
maximalSieve))
  classifyGraph :: forall (a :: PROD (FINITARY j k)) (b :: PROD (FINITARY j k)).
(a ~> b) -> (a && b) ~> Omega
classifyGraph (Prod (Sub (Prof a1 :~> b1
n))) = Sub Prof (SUB (a1 :*: b1)) (SUB Sieve)
-> Prod (Sub Prof) (PR (SUB (a1 :*: b1))) (PR (SUB Sieve))
forall {j} {k} (p :: j +-> k) (a1 :: k) (b1 :: j).
p a1 b1 -> Prod p (PR a1) (PR b1)
Prod (Prof (a1 :*: b1) Sieve -> Sub Prof (SUB (a1 :*: b1)) (SUB Sieve)
forall {k} (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) :~> Sieve) -> Prof (a1 :*: b1) Sieve
forall {j} {k} (p :: j +-> k) (q :: j +-> k).
(Profunctor p, Profunctor q) =>
(p :~> q) -> Prof p q
Prof ((a1 :~> b1) -> (a1 :*: b1) :~> Sieve
forall {j} {k} (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)))

-- | Finitary profunctors between finite categories form an elementary topos: finite limits and
-- colimits, cartesian closed, a subobject classifier, and image factorization.
instance (FiniteCat j, FiniteCat k) => ElementaryTopos (PROD (FINITARY j k))