proarrow
Safe HaskellNone
LanguageGHC2024

Proarrow.Category.Enriched.Finitary.Topos

Description

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.

Synopsis

Documentation

type FINITARY j k = SUBCAT (Finitary :: (j +-> k) -> Constraint) Source Github #

The subcategory of finitary profunctors, as Proarrow.Category.Instance.Rep does for representable ones.

type FIN (p :: j +-> k) = 'SUB p :: SUBCAT (Finitary :: (j +-> k) -> Constraint) Source Github #

Tables of fibres

type KnownNats = KnownListOf SNatI Source Github #

A type-level list of naturals, reflected.

natsVal :: forall (ns :: [Nat]). KnownNats ns => [Natural] Source Github #

type KnownFibres = KnownListOf KnownNats Source Github #

A type-level list of lists of naturals, reflected: the fibres of a partial surjection out of one hom-set.

fibresVal :: forall (fs :: [[Nat]]). KnownFibres fs => [[Natural]] Source Github #

fibres :: [[Natural]] -> (forall (fs :: [[Nat]]). KnownFibres fs => r) -> r Source Github #

Reify a list of lists of naturals.

type KnownTable (bs :: [y]) (as :: [y1]) (t :: [[[[Nat]]]]) = KnownList (KnownList KnownFibres bs) as t Source Github #

A table: a row for each object of k, and in each row the fibres at each object of j.

buildTable :: (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 Source Github #

Build a table by visiting every pair of objects, reifying each cell.

Reindexing along a table of fibres

data Retabulation Source Github #

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.

Constructors

Subobject 
Quotient 

newtype Reindex (r :: Retabulation) (p :: j +-> k) (fs :: [[[[Nat]]]]) (a :: k) (b :: j) Source Github #

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.

Constructors

Reindex (p a b) 

Instances

Instances details
Sheaf t p => Sheaf t (Reindex 'Subobject p fs :: k -> j -> Type) Source Github #

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 details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

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 Source Github #

(Finitary p, Enumerable j, Enumerable k, KnownTable (Objects j) (Objects k) fs) => Finitary (Reindex r p fs :: k -> j -> Type) Source Github # 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Reindex r p fs a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Reindex r p fs a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Reindex r p fs a b] Source Github #

Profunctor p => Profunctor (Reindex r p fs :: k -> j -> Type) Source Github # 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

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 Source Github #

lmap :: forall (c :: k) (a :: k) (b :: j). (c ~> a) -> Reindex r p fs a b -> Reindex r p fs c b Source Github #

rmap :: forall (b :: j) (d :: j) (a :: k). (b ~> d) -> Reindex r p fs a b -> Reindex r p fs a d Source Github #

(\\) :: forall (a :: k) (b :: j) r0. ((Ob a, Ob b) => r0) -> Reindex r p fs a b -> r0 Source Github #

type Cell (fs :: [[k]]) (a :: k1) (b :: j) = Entry (Entry fs (Index a)) (Index b) Source Github #

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]] Source Github #

The fibres at a pair of objects, found by walking the table to the objects' positions.

closedUnder :: (Finitary p, FiniteCat j, FiniteCat k) => (forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> Bool) -> Bool Source Github #

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.

withSubobject :: (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 Source Github #

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.

Finitary profunctors presented by their tables

type KnownTables j k (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) = (KnownTable (Objects j) (Objects k) lm, KnownTable (Objects j) (Objects k) rm) Source Github #

Both tables of a Tabulated profunctor over the objects of j and k.

data Tabulated t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (a :: k) (b :: j) where Source Github #

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 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 withTabulatedSheaf decides the condition first.

Constructors

Tabulated :: forall {k} {j} (a :: k) (b :: j) t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]). (Ob a, Ob b) => Natural -> Tabulated t lm rm a b 

Instances

Instances details
(Site t k, FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Sheaf t (Tabulated t lm rm :: k -> j -> Type) Source Github #

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 details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

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 Source Github #

(FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Finitary (Tabulated t lm rm :: k -> j -> Type) Source Github #

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 details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Tabulated t lm rm a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Tabulated t lm rm a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Tabulated t lm rm a b] Source Github #

(FiniteCat j, FiniteCat k, KnownTables j k lm rm) => Profunctor (Tabulated t lm rm :: k -> j -> Type) Source Github #

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 details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

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 Source Github #

lmap :: forall (c :: k) (a :: k) (b :: j). (c ~> a) -> Tabulated t lm rm a b -> Tabulated t lm rm c b Source Github #

rmap :: forall (b :: j) (d :: j) (a :: k). (b ~> d) -> Tabulated t lm rm a b -> Tabulated t lm rm a d Source Github #

(\\) :: forall (a :: k) (b :: j) r. ((Ob a, Ob b) => r) -> Tabulated t lm rm a b -> r Source Github #

arrowSlot :: forall {k} (c :: k) (a :: k). (FiniteCat k, Ob c, Ob a) => (c ~> a) -> Natural Source Github #

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.

coarrowSlot :: forall {j} (b :: j) (d :: j). (FiniteCat j, Ob b, Ob d) => (b ~> d) -> Natural Source Github #

Where an arrow sits among all the arrows out of its source: the row order of an rm table.

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 Source Github #

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 withTabulatedSheaf, which lives over there because deciding the sheaf condition needs what is built on this module.

toTabulated :: forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k). Finitary p => p :~> (Tabulated t lm rm :: k -> j -> Type) Source Github #

An element of p as the index that stands for it in a presentation of p.

fromTabulated :: forall {j} {k} t (lm :: [[[[Nat]]]]) (rm :: [[[[Nat]]]]) (p :: j +-> k). Finitary p => (Tabulated t lm rm :: k -> j -> Type) :~> p Source Github #

An index in a presentation of p as the element of p it stands for.

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 :: k -> j -> Type), KnownTables j k lm rm) => (p :~> tab) -> (tab :~> p) -> r) -> r Source Github #

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 withTabulatedSheaf.

glueBySearch :: forall t {j} {k} p (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 Source Github #

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 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.

Equalizers and coequalizers

preimageMaybe :: forall {j} {k} p 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) Source Github #

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.

preimage :: forall {j} {k} p q (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 Source Github #

preimageMaybe where the element has to be in the image. Both factorizations below need this, in opposite directions.

classes :: [(Natural, Natural)] -> [Natural] -> [[Natural]] Source Github #

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.

classIndex :: String -> [[Natural]] -> Natural -> Natural Source Github #

The position of the class an index lies in.

classRep :: String -> [[Natural]] -> Natural -> Natural Source Github #

The first member of the class at a position, which stands for the class.

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 Source Github #

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.

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 Source Github #

Factor through an equalizer's inclusion, by preimage: the arrow must land in the image.

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 Source Github #

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.

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' Source Github #

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 factorThroughLocalEpi instead.

Pullbacks, pushouts and images

Natural transformations, enumerated

familiesSatisfying :: [[v]] -> [(Int, Int, v -> v -> Bool)] -> [[v]] Source Github #

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 sequence choices would give them, with the earliest point varying slowest.

familyIndex :: Eq v => String -> [[v]] -> [v] -> Natural Source Github #

Which of the enumerated families a tabulated one is.

type NatKey = (Natural, Natural, Natural) Source Github #

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.

natDomain :: (Finitary p, FiniteCat j, FiniteCat k) => (forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> r) -> [r] Source Github #

Visit every point of that domain, in one fixed order.

natKey :: forall {j} {k} (a :: k) (b :: j) p. (FiniteCat j, FiniteCat k, Finitary p, Ob a, Ob b) => p a b -> NatKey Source Github #

natPositions :: forall {j} {k} (p :: j +-> k). (Finitary p, FiniteCat j, FiniteCat k) => Map NatKey Int Source Github #

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.

natPositionsBy :: (Finitary p, FiniteCat j, FiniteCat k) => (forall (a :: k) (b :: j). (Ob a, Ob b) => p a b -> NatKey) -> Map NatKey Int Source Github #

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.

atNatKey :: Map NatKey Int -> [v] -> NatKey -> v Source Github #

Read a tabulated family back as a function on the points, given those positions.

natElements :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => [[Natural]] Source Github #

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.

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)] Source Github #

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.

natLaws :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => [(NatKey, NatKey, [Natural])] Source Github #

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.

natTable :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => (p :~> q) -> [Natural] Source Github #

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.

natIndex :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => String -> (p :~> q) -> Natural Source Github #

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.

natTransformations :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => [p ~> q] Source Github #

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.

natAt :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Finitary p, Finitary q, FiniteCat j, FiniteCat k) => Map NatKey Int -> [Natural] -> p ~> q Source Github #

A tabulated transformation, as an arrow of j +-> k.

class SubFinitary (p :: j +-> k) where Source Github #

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. 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.

Methods

subFinitary :: (Finitary p => r) -> r Source Github #

Instances

Instances details
Finitary p => SubFinitary (p :: j +-> k) Source Github # 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

subFinitary :: (Finitary p => r) -> r Source Github #

type ExpWeight (p :: j +-> k) (a :: k) (b :: j) = Yo a ('OP b) :*: p Source Github #

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.

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 Source Github #

A tabulated family as an element of the internal hom.

data RiftWeight (w :: k +-> i) (a :: k) (b :: j) (x :: i) (d :: j) where Source Github #

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.

Constructors

RiftWeight :: forall {i} {j} {k} (x :: i) (d :: j) (w :: k +-> i) (a :: k) (b :: j). (Ob x, Ob d) => w x a -> (b ~> d) -> RiftWeight w a b x d 

Instances

Instances details
(Finitary w, LocallyFinite j, Ob a, Ob b) => Finitary (RiftWeight w a b :: k2 -> j -> Type) Source Github # 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

size :: forall (a0 :: k2) (b0 :: j). (Ob a0, Ob b0) => Natural Source Github #

toIndex :: forall (a0 :: k2) (b0 :: j). (Ob a0, Ob b0) => RiftWeight w a b a0 b0 -> Natural Source Github #

fromIndex :: forall (a0 :: k2) (b0 :: j). (Ob a0, Ob b0) => Natural -> RiftWeight w a b a0 b0 Source Github #

elements :: forall (a0 :: k2) (b0 :: j). (Ob a0, Ob b0) => [RiftWeight w a b a0 b0] Source Github #

(Profunctor w, CategoryOf j) => Profunctor (RiftWeight w a b :: k2 -> j -> Type) Source Github # 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

Methods

dimap :: forall (c :: k2) (a0 :: k2) (b0 :: j) (d :: j). (c ~> a0) -> (b0 ~> d) -> RiftWeight w a b a0 b0 -> RiftWeight w a b c d Source Github #

lmap :: forall (c :: k2) (a0 :: k2) (b0 :: j). (c ~> a0) -> RiftWeight w a b a0 b0 -> RiftWeight w a b c b0 Source Github #

rmap :: forall (b0 :: j) (d :: j) (a0 :: k2). (b0 ~> d) -> RiftWeight w a b a0 b0 -> RiftWeight w a b a0 d Source Github #

(\\) :: forall (a0 :: k2) (b0 :: j) r. ((Ob a0, Ob b0) => r) -> RiftWeight w a b a0 b0 -> r Source Github #

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] Source Github #

Every pair (u, v) over every middle object, numbered as compIndex numbers them.

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] Source Github #

Where each middle object's pairs start in the numbering of compPairs.

compIndex :: forall {i} {j} {k} w s (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 Source Github #

The position of a pair over x in compPairs.

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]] Source Github #

The classes of pairs under the identifications along the middle arrows.

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 Source Github #

A tabulated family as an element of the right Kan lift.

The subobject classifier

sieveElements :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k, Ob a, Ob b) => [[Bool]] Source Github #

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.

sieveTable :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k) => Sieve a b -> [Bool] Source Github #

A sieve as the tabulation of its membership, in natDomain order. The inverse of sieveAt.

sieveAt :: forall {j} {k} (a :: k) (b :: j). (FiniteCat j, FiniteCat k, Ob a, Ob b) => Map NatKey Int -> [Bool] -> Sieve a b Source Github #

A tabulated sieve as a sieve.

graphSieve :: forall {j} {k} (p :: j +-> k) (q :: j +-> k). (Profunctor p, Finitary q) => (p :~> q) -> (p :*: q) :~> (Sieve :: k -> j -> Type) Source Github #

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.

Orphan instances

(FiniteCat j, FiniteCat k) => Finitary (Sieve :: k -> j -> Type) Source Github # 
Instance details

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Sieve a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Sieve a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Sieve a b] Source Github #

(Finitary p, Finitary q, FiniteCat j, FiniteCat k) => Finitary (p :~>: q :: k -> j -> Type) Source Github #

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 details

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => (p :~>: q) a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> (p :~>: q) a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [(p :~>: q) a b] Source Github #

(Finitary w, Finitary s, FiniteCat j) => Finitary (w :.: s :: k -> i -> Type) Source Github #

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 details

Methods

size :: forall (a :: k) (b :: i). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: i). (Ob a, Ob b) => (w :.: s) a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: i). (Ob a, Ob b) => Natural -> (w :.: s) a b Source Github #

elements :: forall (a :: k) (b :: i). (Ob a, Ob b) => [(w :.: s) a b] Source Github #

(Finitary v, Finitary p, FiniteCat i, FiniteCat k) => Finitary (Ran ('OP v) p :: k -> j -> Type) Source Github #

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 details

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Ran ('OP v) p a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Ran ('OP v) p a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Ran ('OP v) p a b] Source Github #

(Finitary w, Finitary p, FiniteCat i, FiniteCat j) => Finitary (Rift ('OP w) p :: k -> j -> Type) Source Github #

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 details

Methods

size :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Rift ('OP w) p a b -> Natural Source Github #

fromIndex :: forall (a :: k) (b :: j). (Ob a, Ob b) => Natural -> Rift ('OP w) p a b Source Github #

elements :: forall (a :: k) (b :: j). (Ob a, Ob b) => [Rift ('OP w) p a b] Source Github #

(FiniteCat j, FiniteCat k) => ElementaryTopos (PROD (FINITARY j k)) Source Github #

Finitary profunctors between finite categories form an elementary topos: finite limits and colimits, cartesian closed, a subobject classifier, and image factorization.

Instance details

(FiniteCat j, FiniteCat k) => HasSubobjectClassifier (PROD (FINITARY j k)) Source Github #

The subobject classifier is the profunctor of sieves, and an arrow classifies its graph.

Instance details

Associated Types

type Omega 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

type Omega = 'PR ('SUB (Sieve :: k -> j -> Type) :: SUBCAT (Finitary :: (j +-> k) -> Constraint))

Methods

true :: (TerminalObject :: PROD (FINITARY j k)) ~> (Omega :: PROD (FINITARY j k)) Source Github #

classifyGraph :: forall (a :: PROD (FINITARY j k)) (b :: PROD (FINITARY j k)). (a ~> b) -> (a && b) ~> (Omega :: PROD (FINITARY j k)) Source Github #

(Enumerable j, Enumerable k) => HasEpiMonoFactorization (FINITARY j k) Source Github #

The image of a natural transformation is the equalizer of its cokernel pair.

Instance details

Methods

factorize :: forall (a :: FINITARY j k) (b :: FINITARY j k). (a ~> b) -> (Hom (FINITARY j k) :.: Hom (FINITARY j k)) a b Source Github #

(CategoryOf j, CategoryOf k) => HasBinaryCoproducts (FINITARY j k) Source Github # 
Instance details

Methods

withObCoprod :: forall (a :: FINITARY j k) (b :: FINITARY j k) r. (Ob a, Ob b) => (Ob (a || b) => r) -> r Source Github #

lft :: forall (a :: FINITARY j k) (b :: FINITARY j k). (Ob a, Ob b) => a ~> (a || b) Source Github #

rgt :: forall (a :: FINITARY j k) (b :: FINITARY j k). (Ob a, Ob b) => b ~> (a || b) Source Github #

(|||) :: forall (x :: FINITARY j k) (a :: FINITARY j k) (y :: FINITARY j k). (x ~> a) -> (y ~> a) -> (x || y) ~> a Source Github #

(+++) :: forall (a :: FINITARY j k) (b :: FINITARY j k) (x :: FINITARY j k) (y :: FINITARY j k). (a ~> x) -> (b ~> y) -> (a || b) ~> (x || y) Source Github #

(Enumerable j, Enumerable k) => HasCoequalizers (FINITARY j k) Source Github #

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 details

Methods

coequalize :: forall (a :: FINITARY j k) (b :: FINITARY j k) r. (a ~> b) -> (a ~> b) -> (forall (c :: FINITARY j k). (b ~> c) -> r) -> r Source Github #

factorCoequalizer :: forall (c :: FINITARY j k) (x :: FINITARY j k) (c' :: FINITARY j k). (x ~> c) -> (x ~> c') -> c ~> c' Source Github #

(CategoryOf j, CategoryOf k) => HasInitialObject (FINITARY j k) Source Github # 
Instance details

Associated Types

type InitialObject 
Instance details

Defined in Proarrow.Category.Enriched.Finitary.Topos

type InitialObject = FIN (InitialProfunctor :: k -> j -> Type)

Methods

initiate :: forall (a :: FINITARY j k). Ob a => (InitialObject :: FINITARY j k) ~> a Source Github #

(Enumerable j, Enumerable k) => HasPushouts (FINITARY j k) Source Github # 
Instance details

Methods

pushout :: forall (o :: FINITARY j k) (a :: FINITARY j k) (b :: FINITARY j k) r. (o ~> a) -> (o ~> b) -> (forall (p :: FINITARY j k). (a ~> p) -> (b ~> p) -> r) -> r Source Github #

factorPushout :: forall (a :: FINITARY j k) (b :: FINITARY j k) (p :: FINITARY j k) (q :: FINITARY j k). (a ~> p) -> (b ~> p) -> (a ~> q) -> (b ~> q) -> p ~> q Source Github #

(Enumerable j, Enumerable k) => HasEqualizers (FINITARY j k) Source Github #

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 details

Methods

equalize :: forall (a :: FINITARY j k) (b :: FINITARY j k) r. (a ~> b) -> (a ~> b) -> (forall (e :: FINITARY j k). (e ~> a) -> r) -> r Source Github #

factorEqualizer :: forall (e :: FINITARY j k) (x :: FINITARY j k) (e' :: FINITARY j k). (e ~> x) -> (e' ~> x) -> e' ~> e Source Github #

(Enumerable j, Enumerable k) => HasPullbacks (FINITARY j k) Source Github #

Pullbacks are equalizers of products, and pushouts coequalizers of coproducts, all of which finitary profunctors have.

Instance details

Methods

pullback :: forall (o :: FINITARY j k) (a :: FINITARY j k) (b :: FINITARY j k) r. (a ~> o) -> (b ~> o) -> (forall (p :: FINITARY j k). (p ~> a) -> (p ~> b) -> r) -> r Source Github #

factorPullback :: forall (a :: FINITARY j k) (b :: FINITARY j k) (p :: FINITARY j k) (q :: FINITARY j k). (p ~> a) -> (p ~> b) -> (q ~> a) -> (q ~> b) -> q ~> p Source Github #

(FiniteCat j, FiniteCat k, forall (p :: j +-> k). ob p => SubFinitary p) => Finitary (Sub (Prof :: (j +-> k) -> (j +-> k) -> Type) :: SUBCAT ob -> SUBCAT ob -> Type) Source Github #

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 details

Methods

size :: forall (a :: SUBCAT ob) (b :: SUBCAT ob). (Ob a, Ob b) => Natural Source Github #

toIndex :: forall (a :: SUBCAT ob) (b :: SUBCAT ob). (Ob a, Ob b) => Sub (Prof :: (j +-> k) -> (j +-> k) -> Type) a b -> Natural Source Github #

fromIndex :: forall (a :: SUBCAT ob) (b :: SUBCAT ob). (Ob a, Ob b) => Natural -> Sub (Prof :: (j +-> k) -> (j +-> k) -> Type) a b Source Github #

elements :: forall (a :: SUBCAT ob) (b :: SUBCAT ob). (Ob a, Ob b) => [Sub (Prof :: (j +-> k) -> (j +-> k) -> Type) a b] Source Github #