{-# LANGUAGE AllowAmbiguousTypes #-}

-- | Profunctors whose hom-sets are finite and numbered: @p a b@ is in bijection with an initial
-- segment of the naturals. This makes limits and colimits computable: an element is an index, so a
-- subset or quotient of a hom-set is a table of indices, which can be reified into a fresh object.
--
-- The numbering is a /value/, as in "Proarrow.Category.Instance.FinHask". A type-level size could
-- only be a formula in the sizes it is built from, which rules out constructions whose count
-- depends on how arrows compose, such as the exponential and the subobject classifier.
--
-- A 'Proarrow.Category.Enriched.Thin.DecidableProfunctor' is the special case where every size is
-- zero or one; 'decidableSize' and 'decidableFromIndex' build that instance.
--
-- This module is only the vocabulary. The category @'Proarrow.Category.Enriched.Finitary.Topos.FINITARY' j k@
-- and everything computed in it live in "Proarrow.Category.Enriched.Finitary.Topos". The class
-- and 'Elt' are needed by 'Proarrow.Limit.Power.Powered', "Proarrow.Category.Enriched" and
-- others that the topos half itself depends on.
module Proarrow.Category.Enriched.Finitary where

import Data.Kind (Constraint)
import Data.List (elemIndex, find, genericIndex, genericTake)
import Data.Maybe (isJust)
import Data.Type.Nat (snat)
import Data.Type.Nat qualified as N
import Data.Universe.Class qualified as U
import Data.Universe.Helpers qualified as U
import Numeric.Natural (Natural)
import Prelude (Maybe (..), compare, show, (+), (-), (<), (==))
import Prelude qualified as P

import Proarrow.Category.Enriched.Thin
  ( DecidableProfunctor (..)
  , Decision (..)
  , Enumerable (..)
  , Finite (..)
  , Indexed (..)
  )
import Proarrow.Category.Instance.Bool (Booleans)
import Proarrow.Category.Instance.Opposite (OPPOSITE (..), Op (..))
import Proarrow.Category.Instance.Ordinal (LTE)
import Proarrow.Category.Instance.Product ((:**:) (..))
import Proarrow.Category.Instance.Unit (Unit (..))
import Proarrow.Core (CategoryOf (..), Hom, Profunctor (..), Promonad (..), type (+->))
import Proarrow.Functor (FunctorForRep (..), withMappedOb)
import Proarrow.Object (mapListOf)
import Proarrow.Profunctor.Corepresentable (Corep (..))
import Proarrow.Profunctor.Instance.Coproduct ((:+:) (..))
import Proarrow.Profunctor.Instance.Initial (InitialProfunctor)
import Proarrow.Profunctor.Instance.Product ((:*:) (..))
import Proarrow.Profunctor.Instance.Terminal (TerminalProfunctor (..))
import Proarrow.Tools.Laws (ProLaw (..), ProLaws (..), (=:=))

-- | A profunctor with finite, numbered hom-sets. 'toIndex' and 'fromIndex' are inverse for indices
-- below 'size'; @fromIndex@ of anything else is an error, as is 'toIndex' of an element that is not
-- one the instance can produce (which only an unlawfully built value can be).
--
-- An instance whose elements are found by searching should define 'elements' and read 'size' off
-- it, rather than let the default call 'fromIndex' once per element and repeat the search each time.
type Finitary :: forall {j} {k}. j +-> k -> Constraint
class (Profunctor p) => Finitary (p :: j +-> k) where
  -- | How many elements the hom-set has.
  size :: (Ob (a :: k), Ob (b :: j)) => Natural

  -- | Where an element sits in 'elements'. Takes its objects like the others do, so that an
  -- instance that has to search can bind the search outside the argument lambda and a caller can
  -- share it with @let toIndexP = 'toIndex' \@p \@a \@b@.
  toIndex :: (Ob (a :: k), Ob (b :: j)) => p a b -> Natural

  -- | The element at a position.
  fromIndex :: (Ob (a :: k), Ob (b :: j)) => Natural -> p a b

  -- | All elements of a hom-set, in index order.
  elements :: (Ob (a :: k), Ob (b :: j)) => [p a b]
  elements @a @b = (Natural -> p a b) -> [Natural] -> [p a b]
forall a b. (a -> b) -> [a] -> [b]
P.map (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) (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 @p @a @b))

-- | 'fromIndex' recovers an element from its index. The other laws, that 'elements' has 'size'
-- entries numbered in order, are not equations between elements.
instance ProLaws Finitary where
  proLaws :: [ProLaw Finitary]
proLaws = [String -> ProLawBody Finitary -> ProLaw Finitary
forall {j} {k} (c :: (j +-> k) -> Constraint).
String -> ProLawBody c -> ProLaw c
ProLaw String
"fromIndex . toIndex" \ @p @a @b p a b
p forall (x :: k) (y :: k). (Ob x, Ob y) => String -> m (x ~> y)
_ forall (x :: j) (y :: j). (Ob x, Ob y) => String -> m (x ~> y)
_ -> p a b
p p a b -> p a b -> m (ProEquation p)
forall {j} {k} (m :: Type -> Type) (p :: j +-> k) (a :: k)
       (b :: j).
Applicative m =>
p a b -> p a b -> m (ProEquation p)
=:= 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 @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
p)]

-- | @[0 .. n-1]@, which @n@ being a 'Natural' rules out writing directly.
indices :: Natural -> [Natural]
indices :: Natural -> [Natural]
indices Natural
n = Natural -> [Natural] -> [Natural]
forall i a. Integral i => i -> [a] -> [a]
genericTake Natural
n [Natural
0 ..]

-- | A finitary profunctor's hom-set sizes, one per pair of objects, the outer index running over
-- @k@ and the inner over @j@. Cheap enough to display an object by: a presheaf on the graph
-- schema, say, shows as @[2,4,2,4]@.
sizes :: forall {j} {k} (p :: j +-> k). (Finitary p, Enumerable j, Enumerable k) => [Natural]
sizes :: forall {j} {k} (p :: j +-> k).
(Finitary p, Enumerable j, Enumerable k) =>
[Natural]
sizes = 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 -> [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]

-- | The position of an object in its kind's object list.
objIndex :: forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex :: forall {k} (a :: k). (Enumerable k, Ob a) => Natural
objIndex = forall k (a :: k) r.
(Enumerable k, Ob a) =>
(KnownIndex a => r) -> r
withIndex @k @a (SNat (Index a) -> Natural
forall (n :: Nat). SNat n -> Natural
N.snatToNatural (forall (n :: Nat). SNatI n => SNat n
snat @(Index a)))

-- | Everything an enumeration of a kind's objects can do at each of them, concatenated.
foreachOb :: forall k r. (Enumerable k) => (forall (a :: k). (Ob a) => [r]) -> [r]
foreachOb :: forall k r. Enumerable k => (forall (a :: k). Ob a => [r]) -> [r]
foreachOb forall (a :: k). Ob a => [r]
f = [[r]] -> [r]
forall (t :: Type -> Type) a. Foldable t => t [a] -> [a]
P.concat ((forall (x :: k). KnownIndex x => [r])
-> ListOf KnownIndex (Objects k) -> [[r]]
forall {k} (c :: OB k) (xs :: [k]) r.
(forall (x :: k). c x => r) -> ListOf c xs -> [r]
mapListOf (\ @a -> forall k (a :: k) r.
(Enumerable k, KnownIndex a) =>
(Ob a => r) -> r
withOb @k @a (forall (a :: k). Ob a => [r]
f @a)) (forall k. Finite k => IndexedList (Objects k)
finite @k))

-- * Thin profunctors

-- | A decidable profunctor has one element where it holds and none where it does not. These cannot
-- be @default@ method bodies: 'size' and 'fromIndex' do not mention their objects except in a
-- constraint, so GHC cannot tie a default body's objects to the instance's.
decidableSize :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j). (DecidableProfunctor p, Ob a, Ob b) => Natural
decidableSize :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural
decidableSize = case forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Decision p a b (Holds p a b)
forall (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Decision p a b (Holds p a b)
decide @p @a @b of
  Yes p a b
_ -> Natural
1
  Decision p a b (Holds p a b)
No -> Natural
0

decidableFromIndex
  :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j). (DecidableProfunctor p, Ob a, Ob b) => Natural -> p a b
decidableFromIndex :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural -> p a b
decidableFromIndex Natural
_ = case forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Decision p a b (Holds p a b)
forall (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Decision p a b (Holds p a b)
decide @p @a @b of
  Yes p a b
x -> p a b
x
  Decision p a b (Holds p a b)
No -> String -> p a b
forall a. HasCallStack => String -> a
P.error String
"fromIndex: the profunctor does not hold here"

-- * Hom-sets as finite sets

-- | An element of a hom-set of @p@, viewed as an element of a /finite set/: every instance the
-- @universe@ package asks for is supplied by the numbering, with 'toIndex' standing in for equality
-- and ordering. So a finitary profunctor is a profunctor enriched in
-- 'Proarrow.Category.Instance.FinHask.FINHASK'.
newtype Elt (p :: j +-> k) (a :: k) (b :: j) = Elt {forall j k (p :: j +-> k) (a :: k) (b :: j). Elt p a b -> p a b
unElt :: p a b}

instance (Finitary p, Ob a, Ob b) => U.Universe (Elt (p :: j +-> k) a b) where
  universe :: [Elt p a b]
universe = (p a b -> Elt p a b) -> [p a b] -> [Elt p a b]
forall a b. (a -> b) -> [a] -> [b]
P.map p a b -> Elt p a b
forall j k (p :: j +-> k) (a :: k) (b :: j). p a b -> Elt p a b
Elt (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)

instance (Finitary p, Ob a, Ob b) => U.Finite (Elt (p :: j +-> k) a b) where
  cardinality :: Tagged (Elt p a b) Natural
cardinality = Natural -> Tagged (Elt p a b) Natural
forall {k} (s :: k) b. b -> Tagged s b
U.Tagged (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)

instance (Finitary p) => P.Eq (Elt (p :: j +-> k) a b) where
  Elt p a b
x == :: Elt p a b -> Elt p a b -> Bool
== Elt p a b
y = (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 Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== 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
y) ((Ob a, Ob b) => Bool) -> p a b -> Bool
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

instance (Finitary p) => P.Ord (Elt (p :: j +-> k) a b) where
  compare :: Elt p a b -> Elt p a b -> Ordering
compare (Elt p a b
x) (Elt p a b
y) = Natural -> Natural -> Ordering
forall a. Ord a => a -> a -> Ordering
P.compare (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 -> 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
y) ((Ob a, Ob b) => Ordering) -> p a b -> Ordering
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

instance (Finitary p) => P.Show (Elt (p :: j +-> k) a b) where
  show :: Elt p a b -> String
show (Elt p a b
x) = Natural -> String
forall a. Show a => a -> String
P.show (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) => String) -> p a b -> String
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

-- | A category whose hom-sets are finite: the 'Finitary' counterpart of
-- 'Proarrow.Category.Enriched.Thin.Decidable', and one half of 'FiniteCat'.
class (CategoryOf k, Finitary (Hom k)) => LocallyFinite k

instance (CategoryOf k, Finitary (Hom k)) => LocallyFinite k

-- | How an arrow factors through another into the same object: @'factorThrough' g f@ is an @h@
-- with @g = f '.' h@, if there is one. Only the hom-set @x '~>' y@ is searched, so only the
-- hom-sets need to be finite. An element is in the image of @f@ iff it factors through @f@.
factorThrough
  :: forall {k} (x :: k) y a. (LocallyFinite k, Ob x, Ob y, Ob a) => x ~> a -> y ~> a -> Maybe (x ~> y)
factorThrough :: forall {k} (x :: k) (y :: k) (a :: k).
(LocallyFinite k, Ob x, Ob y, Ob a) =>
(x ~> a) -> (y ~> a) -> Maybe (x ~> y)
factorThrough x ~> a
g y ~> a
f = ((x ~> y) -> Bool) -> [x ~> y] -> Maybe (x ~> y)
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Maybe a
find (\x ~> y
h -> forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
forall (p :: k +-> k) (a :: k) (b :: k).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex @(Hom k) @x @a (y ~> a
f (y ~> a) -> (x ~> y) -> x ~> a
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. x ~> y
h) Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
gi) (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) @x @y)
  where
    -- hoisted out of the lambda, as 'toIndex' asks: an instance that searches only searches once
    gi :: Natural
gi = (x ~> a) -> Natural
forall (a :: k) (b :: k). (Ob a, Ob b) => Hom k a b -> Natural
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
p a b -> Natural
toIndex x ~> a
g

-- | Whether an arrow factors through another, which is 'factorThrough' with the witness dropped.
-- 'Proarrow.Category.Enriched.Finitary.Sheaf.generatedSieve' is the caller: a cover's sieve is the
-- arrows that factor through one of its legs.
factorsThrough :: forall {k} (x :: k) y a. (LocallyFinite k, Ob x, Ob y, Ob a) => x ~> a -> y ~> a -> P.Bool
factorsThrough :: forall {k} (x :: k) (y :: k) (a :: k).
(LocallyFinite k, Ob x, Ob y, Ob a) =>
(x ~> a) -> (y ~> a) -> Bool
factorsThrough x ~> a
g y ~> a
f = Maybe (x ~> y) -> Bool
forall a. Maybe a -> Bool
isJust ((x ~> a) -> (y ~> a) -> Maybe (x ~> y)
forall {k} (x :: k) (y :: k) (a :: k).
(LocallyFinite k, Ob x, Ob y, Ob a) =>
(x ~> a) -> (y ~> a) -> Maybe (x ~> y)
factorThrough x ~> a
g y ~> a
f)

-- | A finite category: finitely many objects, and finitely many arrows between them. The first is
-- 'Enumerable', the second does not follow from it, and the enumeration below needs both.
class (Enumerable k, Finitary (Hom k)) => FiniteCat k

instance (Enumerable k, Finitary (Hom k)) => FiniteCat k

-- | A profunctor between categories with finite hom-sets is finitary iff it is enriched in finite
-- sets. These build a 'Finitary' instance from 'U.Finite' hom-sets, the counterparts of
-- 'decidableSize' and 'decidableFromIndex' one level up.
--
-- 'finiteToIndex' and 'finiteFromIndex' search 'U.universeF', which is fine for small hom-sets.
-- For large ones compute the index arithmetically, as
-- 'Proarrow.Category.Instance.FinHask.FinHask' does.
finiteSize :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j). (U.Finite (p a b)) => Natural
finiteSize :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
Finite (p a b) =>
Natural
finiteSize = Tagged (p a b) Natural -> Natural
forall {k} (s :: k) b. Tagged s b -> b
U.unTagged (forall a. Finite a => Tagged a Natural
U.cardinality @(p a b))

finiteToIndex :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j). (U.Finite (p a b), P.Eq (p a b)) => p a b -> Natural
finiteToIndex :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finite (p a b), Eq (p a b)) =>
p a b -> Natural
finiteToIndex p a b
x = case p a b -> [p a b] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
elemIndex p a b
x [p a b]
forall a. Finite a => [a]
U.universeF 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
"toIndex: not in the universe of the hom-set"

finiteFromIndex :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j). (U.Finite (p a b)) => Natural -> p a b
finiteFromIndex :: forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
Finite (p a b) =>
Natural -> p a b
finiteFromIndex Natural
i = [p a b] -> Natural -> p a b
forall i a. Integral i => [a] -> i -> a
genericIndex (forall a. Finite a => [a]
U.universeF @(p a b)) Natural
i

-- | The one-object category has one arrow.
instance Finitary Unit where
  size :: forall (a :: ()) (b :: ()). (Ob a, Ob b) => Natural
size = Natural
1
  toIndex :: forall (a :: ()) (b :: ()). (Ob a, Ob b) => Unit a b -> Natural
toIndex Unit a b
Unit = Natural
0
  fromIndex :: forall (a :: ()) (b :: ()). (Ob a, Ob b) => Natural -> Unit a b
fromIndex Natural
_ = Unit a b
Unit '() '()
Unit

-- | @'Proarrow.Category.Instance.Bool.BOOL'@ is thin, so each hom-set holds at most the one arrow.
instance Finitary Booleans where
  size :: forall (a :: BOOL) (b :: BOOL). (Ob a, Ob b) => Natural
size @a @b = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural
forall (p :: BOOL +-> BOOL) (a :: BOOL) (b :: BOOL).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural
decidableSize @Booleans @a @b
  toIndex :: forall (a :: BOOL) (b :: BOOL).
(Ob a, Ob b) =>
Booleans a b -> Natural
toIndex Booleans a b
_ = Natural
0
  fromIndex :: forall (a :: BOOL) (b :: BOOL).
(Ob a, Ob b) =>
Natural -> Booleans a b
fromIndex @a @b = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural -> p a b
forall (p :: BOOL +-> BOOL) (a :: BOOL) (b :: BOOL).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural -> p a b
decidableFromIndex @Booleans @a @b

-- | The ordinals are thin too, so the same three lines serve. So a chain can be used as a site: a
-- cover there can have a leg that is itself covered, which no coverage on a two-object category
-- can arrange.
instance Finitary LTE where
  size :: forall (a :: ORDINAL n) (b :: ORDINAL n). (Ob a, Ob b) => Natural
size @a @b = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural
forall (p :: ORDINAL n +-> ORDINAL n) (a :: ORDINAL n)
       (b :: ORDINAL n).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural
decidableSize @LTE @a @b
  toIndex :: forall (a :: ORDINAL n) (b :: ORDINAL n).
(Ob a, Ob b) =>
LTE a b -> Natural
toIndex LTE a b
_ = Natural
0
  fromIndex :: forall (a :: ORDINAL n) (b :: ORDINAL n).
(Ob a, Ob b) =>
Natural -> LTE a b
fromIndex @a @b = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural -> p a b
forall (p :: ORDINAL n +-> ORDINAL n) (a :: ORDINAL n)
       (b :: ORDINAL n).
(DecidableProfunctor p, Ob a, Ob b) =>
Natural -> p a b
decidableFromIndex @LTE @a @b

-- * Products and coproducts

-- | The terminal profunctor has one element everywhere.
instance (CategoryOf j, CategoryOf k) => Finitary (TerminalProfunctor :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size = Natural
1
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
TerminalProfunctor a b -> Natural
toIndex TerminalProfunctor a b
TerminalProfunctor = Natural
0
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> TerminalProfunctor a b
fromIndex Natural
_ = TerminalProfunctor a b
forall {j} {k} (a :: j) (b :: k).
(CategoryOf j, CategoryOf k, Ob a, Ob b) =>
TerminalProfunctor a b
TerminalProfunctor

-- | A pair of indices as one index, row-major: the first factor varies slowest. Shared by the two
-- instances that number a pair of independent choices (the product profunctor and the Yoneda
-- embedding), because 'ExpWeight' nests one inside the other, so they have to agree.
pairIndex :: Natural -> Natural -> Natural -> Natural
pairIndex :: Natural -> Natural -> Natural -> Natural
pairIndex Natural
n Natural
i Natural
j = Natural
i Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.* Natural
n Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
+ Natural
j

-- | The inverse, given the size of the second factor.
unpairIndex :: Natural -> Natural -> (Natural, Natural)
unpairIndex :: Natural -> Natural -> (Natural, Natural)
unpairIndex Natural
0 Natural
_ = String -> (Natural, Natural)
forall a. HasCallStack => String -> a
P.error String
"fromIndex: a factor of the pair has no elements"
unpairIndex Natural
n Natural
i = Natural
i Natural -> Natural -> (Natural, Natural)
forall a. Integral a => a -> a -> (a, a)
`P.divMod` Natural
n

instance (Finitary p, Finitary q) => Finitary (p :*: q) 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 :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @p @a @b 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 +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a @b
  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => (:*:) p q a b -> Natural
toIndex @a @b (p a b
x :*: q a b
y) = 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 +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @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) (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
y)
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> (:*:) p q a b
fromIndex @a @b 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 +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a @b) Natural
i in 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
l p a b -> q a b -> (:*:) p q a b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) (q :: j +-> k).
p a b -> q a b -> (:*:) p q a b
:*: Natural -> q a b
forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> q 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

  -- Spelled out, not left to the default: that would ask @p@ for its size once per element, and
  -- when @p@ is itself an enumeration ('Sieve', or a nested internal hom) a size is a whole search.
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [(:*:) p q a b]
elements @a @b = [p a b
x p a b -> q a b -> (:*:) p q a b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) (q :: j +-> k).
p a b -> q a b -> (:*:) p q a b
:*: q a b
y | 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
y <- 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]

-- | The product of two finitary profunctors on the product of their kinds, numbered as ':*:' is.
instance (Finitary p, Finitary q) => Finitary (p :**: q) where
  size :: forall (a :: (k1, k2)) (b :: (j1, j2)). (Ob a, Ob b) => Natural
size @'(a1, a2) @'(b1, b2) = forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j1 +-> k1) (a :: k1) (b :: j1).
(Finitary p, Ob a, Ob b) =>
Natural
size @p @a1 @b1 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 :: j2 +-> k2) (a :: k2) (b :: j2).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a2 @b2
  toIndex :: forall (a :: (k1, k2)) (b :: (j1, j2)).
(Ob a, Ob b) =>
(:**:) p q a b -> Natural
toIndex @'(_, a2) @'(_, b2) (p a1 b1
x :**: q a2 b2
y) = Natural -> Natural -> Natural -> Natural
pairIndex (forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
forall (p :: j2 +-> k2) (a :: k2) (b :: j2).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a2 @b2) (p a1 b1 -> Natural
forall (a :: k1) (b :: j1). (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 a1 b1
x) (q a2 b2 -> Natural
forall (a :: k2) (b :: j2). (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 a2 b2
y)
  fromIndex :: forall (a :: (k1, k2)) (b :: (j1, j2)).
(Ob a, Ob b) =>
Natural -> (:**:) p q a b
fromIndex @'(_, a2) @'(_, b2) 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 :: j2 +-> k2) (a :: k2) (b :: j2).
(Finitary p, Ob a, Ob b) =>
Natural
size @q @a2 @b2) Natural
i in Natural -> p (Fst @ a) (Fst @ b)
forall (a :: k1) (b :: j1). (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
l p (Fst @ a) (Fst @ b)
-> q (Snd @ a) (Snd @ b)
-> (:**:) p q '(Fst @ a, Snd @ a) '(Fst @ b, Snd @ b)
forall {j1} {k1} {j2} {k2} (c :: j1 +-> k1) (a1 :: k1) (b1 :: j1)
       (d :: j2 +-> k2) (a2 :: k2) (b2 :: j2).
c a1 b1 -> d a2 b2 -> (:**:) c d '(a1, a2) '(b1, b2)
:**: Natural -> q (Snd @ a) (Snd @ b)
forall (a :: k2) (b :: j2). (Ob a, Ob b) => Natural -> q 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 :: (k1, k2)) (b :: (j1, j2)).
(Ob a, Ob b) =>
[(:**:) p q a b]
elements @'(a1, a2) @'(b1, b2) = [p (Fst @ a) (Fst @ b)
x p (Fst @ a) (Fst @ b)
-> q (Snd @ a) (Snd @ b)
-> (:**:) p q '(Fst @ a, Snd @ a) '(Fst @ b, Snd @ b)
forall {j1} {k1} {j2} {k2} (c :: j1 +-> k1) (a1 :: k1) (b1 :: j1)
       (d :: j2 +-> k2) (a2 :: k2) (b2 :: j2).
c a1 b1 -> d a2 b2 -> (:**:) c d '(a1, a2) '(b1, b2)
:**: q (Snd @ a) (Snd @ b)
y | p (Fst @ a) (Fst @ b)
x <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j1 +-> k1) (a :: k1) (b :: j1).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @p @a1 @b1, q (Snd @ a) (Snd @ b)
y <- forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
[p a b]
forall (p :: j2 +-> k2) (a :: k2) (b :: j2).
(Finitary p, Ob a, Ob b) =>
[p a b]
elements @q @a2 @b2]

-- | A corepresentable over finite hom-sets is finitary, numbered as the hom-set @f '@' a ~> b@.
-- (It lives here and not with 'Corep': "Proarrow.Profunctor.Corepresentable" is below this module.)
instance (FunctorForRep f, LocallyFinite j) => Finitary (Corep (f :: k +-> j)) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size @a @b = forall {j} {k} (f :: j +-> k) (a :: j) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
forall (f :: k +-> j) (a :: k) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
withMappedOb @f @a (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) @(f @ a) @b)
  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Corep f a b -> Natural
toIndex (Corep (f @ a) ~> b
g) = ((f @ a) ~> 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 (f @ a) ~> b
g ((Ob (f @ a), Ob b) => Natural) -> ((f @ a) ~> b) -> Natural
forall (a :: j) (b :: j) 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
\\ (f @ a) ~> b
g
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Corep f a b
fromIndex @a @_ Natural
i = forall {j} {k} (f :: j +-> k) (a :: j) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
forall (f :: k +-> j) (a :: k) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
withMappedOb @f @a (((f @ a) ~> b) -> Corep f a b
forall {j} {k} (a :: j) (f :: j +-> k) (b :: k).
Ob a =>
((f @ a) ~> b) -> Corep f a b
Corep (Natural -> (f @ a) ~> 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
i))
  elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Corep f a b]
elements @a @b = forall {j} {k} (f :: j +-> k) (a :: j) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
forall (f :: k +-> j) (a :: k) r.
(FunctorForRep f, Ob a) =>
(Ob (f @ a) => r) -> r
withMappedOb @f @a ((((f @ a) ~> b) -> Corep f a b) -> [(f @ a) ~> b] -> [Corep f a b]
forall a b. (a -> b) -> [a] -> [b]
P.map ((f @ a) ~> b) -> Corep f a b
forall {j} {k} (a :: j) (f :: j +-> k) (b :: k).
Ob a =>
((f @ a) ~> b) -> Corep f a b
Corep (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) @(f @ a) @b))

-- | The opposite of a finitary profunctor is finitary, at the same sizes read the other way round.
-- Taking @p = 'Hom' k@ this makes @'OPPOSITE' k@ a 'FiniteCat' whenever @k@ is one, so everything
-- computed for a finite site is available on the opposite category too. (This instance lives here
-- rather than with 'Op' because "Proarrow.Category.Instance.Opposite" sits below this module in the
-- import graph.)
instance (Finitary p) => Finitary (Op p) where
  size :: forall (a :: OPPOSITE j) (b :: OPPOSITE k). (Ob a, Ob b) => Natural
size @(OP a) @(OP b) = 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 @b @a
  toIndex :: forall (a :: OPPOSITE j) (b :: OPPOSITE k).
(Ob a, Ob b) =>
Op p a b -> Natural
toIndex @(OP a) @(OP b) (Op p b1 a1
x) = 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 @b @a p b1 a1
p (UN OP b) (UN OP a)
x
  fromIndex :: forall (a :: OPPOSITE j) (b :: OPPOSITE k).
(Ob a, Ob b) =>
Natural -> Op p a b
fromIndex @(OP a) @(OP b) Natural
i = p (UN OP b) (UN OP a) -> Op p (OP (UN OP a)) (OP (UN OP b))
forall {j} {k} (p :: j +-> k) (b1 :: k) (a1 :: j).
p b1 a1 -> Op p (OP a1) (OP b1)
Op (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 @b @a Natural
i)
  elements :: forall (a :: OPPOSITE j) (b :: OPPOSITE k).
(Ob a, Ob b) =>
[Op p a b]
elements @(OP a) @(OP b) = (p (UN OP b) (UN OP a) -> Op p a b)
-> [p (UN OP b) (UN OP a)] -> [Op p a b]
forall a b. (a -> b) -> [a] -> [b]
P.map p (UN OP b) (UN OP a) -> Op p a b
p (UN OP b) (UN OP a) -> Op p (OP (UN OP a)) (OP (UN OP b))
forall {j} {k} (p :: j +-> k) (b1 :: k) (a1 :: j).
p b1 a1 -> Op p (OP a1) (OP b1)
Op (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 @b @a)

-- | The initial profunctor has no elements anywhere.
instance (CategoryOf j, CategoryOf k) => Finitary (InitialProfunctor :: j +-> k) where
  size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural
size = Natural
0
  toIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
InitialProfunctor a b -> Natural
toIndex = \case {}
  fromIndex :: forall (a :: k) (b :: j).
(Ob a, Ob b) =>
Natural -> InitialProfunctor a b
fromIndex Natural
_ = String -> InitialProfunctor a b
forall a. HasCallStack => String -> a
P.error String
"fromIndex: the initial profunctor has no elements"

-- | The indices of @p@ first, then those of @q@.
instance (Finitary p, Finitary q) => Finitary (p :+: q) 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 :: j +-> k) (a :: k) (b :: j).
(Finitary p, Ob a, Ob b) =>
Natural
size @p @a @b Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
+ 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
  toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => (:+:) p q a b -> Natural
toIndex @a @b = \case
    InjL p a b
x -> 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
    InjR q a b
y -> 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 -> Natural
forall a. Num a => a -> a -> a
+ 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
y
  fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> (:+:) p q a b
fromIndex @a @b Natural
i = if Natural
i Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 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 then p a b -> (:+:) p q a b
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j) (q :: j +-> k).
p a b -> (:+:) p q a b
InjL (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) else q a b -> (:+:) p q a b
forall {j} {k} (q :: j +-> k) (a :: k) (b :: j) (p :: j +-> k).
q a b -> (:+:) p q a b
InjR (Natural -> q a b
forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> q 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 Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
- 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))