4.2: Enriched Profunctors

In this section we will understand how co-design problems form a category. Along the way we will develop some abstract machinery that will allow us to replace preorder design spaces with other enriched categories.

Feasibility relationships as Bool-profunctors

The theory of co-design is based on preorders: each resource e.g. velocity, torque, or $ is structured as a preorder. The order x ≤ y represents the availability of x given y, i.e. that whenever you have y, you also have x. For example, in our preorder of wattage, if 5W ≤ 10W, it means that whenever we are provided 10W, we implicitly also have 5W. Above we referred to this as an order from less useful to more useful: if x is always available given y, then x is less useful than y.

We know from Section 2.3.2 that a preorder X can be conceived of as a Bool-category. Given x, y \(\in\) X, we have X(x, y) \(\in\) \(\mathbb{B}\); this value responds to the assertion “x is available given y,” marking it either true or false.

Our goal is to see feasibility relations as Bool-profunctors, which are a special case of something called enriched profunctors. Indeed, we hope that this chapter will give you some intuition for profunctors, arising from the table

Because enriched profunctors are a bit abstract, we first concretely discuss Bool-profunctors as feasibility relations.

Recall that if X = (X, ≤) is a preorder, then its opposite X\(^{op}\) = (X, ≥) has x ≥ y iff y ≤ x.

Definition 4.2: Feasibility Relation

Let X = (X, ≤X ) and Y = (Y, ≤Y ) be preorders. A feasibility relation for X given Y is a monotone map

Φ : X\(^{op}\) × Y → Bool. (4.3)

We denote this by Φ : X \(\rightarrow\) Y.

Given x \(\in\) X and y \(\in\) Y, if Φ(x,y) = true we say x can be obtained given y.

As mentioned in the introduction, the requirement that Φ is monotone says that if x′ ≤\(_{X}\) x and y ≤\(_{Y}\) y′ then Φ(x,y) ≤\(_{Bool}\) Φ(x′,y′). In other words, if x can be obtained given y, and if x′ is available given x, then x′ can be obtained given y. And if furthermore y is available given y′, then x′ can also be obtained given y′.

Exercise 4.4.

Suppose we have the preorders

1. Draw the Hasse diagram for the preorder X\(^{op}\) × Y.
2. Write down a profunctor \(\bigwedge\): X\(\rightarrow\) Y and, reading \(\bigwedge\)(x, y) = true as “my aunt can explain an x given y,” give an interpretation of the fact that the preimage of true forms an upper set in X\(^{op}\) × Y. ♦

To generalize the notion of feasibility relation, we must notice that the symmetric monoidal preorder Bool has more structure than just that of a symmetric monoidal preorder: as mentioned in Exercise 2.93, Bool is a quantale. That means it has all joins \(\bigvee\), and a closure operation, which we’ll write ⇒ : \(\mathbb{B}\) × \(\mathbb{B}\) → \(\mathbb{B}\). By definition, this operation satisfies the property that for all b, c, d \(\in\) \(\mathbb{B}\) one has

b \(\bigwedge\) c ≤ d iff b ≤ (c ⇒ d). (4.5)

The operation ⇒ is given by the following table:

Exercise 4.7.

Show that ⇒ as defined in Eq. (4.6) indeed satisfies Eq. (4.5). ♦

On an abstract level, it is the fact that Bool is a quantale which makes everything in this chapter work; any other (unital commutative) quantale also defines a way to interpret co-design diagrams. For example, we could use the quantale Cost, which would describe not whether x is available given y but the cost of obtaining x given y; see Example 2.37 and Definition 2.46.

V-profunctors

We are now ready to recast Eq. (4.3) in abstract terms. Recall the notions of enriched product (Definition 2.74), enriched functor (Definition 2.69), and quantale (Definition 2.79).

Definition: 4.8.

Let V = (V, ≤, I, ⊗) be a (unital commutative) quantale,\(^{1}\) and let X and Y be V-categories.

A V-profunctor from X to Y, denoted Φ : X Y, is a V-functor

Φ: X\(^{op}\) × Y → V.

Note that a V-functor must have V-categories for domain and codomain, so here we are considering V as enriched in itself; see Remark 2.89.

Exercise 4.9.

Show that a V-profunctor (Definition 4.8) is the same as a function Φ: Ob(X) × Ob(Y) → V such that for any x,x′ \(\in\) X and y,y′ \(\in\) Y the following inequality holds in V:

X(x′, x) ⊗ Φ(x, y) ⊗ Y(y, y′) ≤ Φ(x′, y′). ♦

Exercise 4.10.

Is it true that a Bool-profunctor, as in Definition 4.8, is exactly the same as a feasibility relation, as in Definition 4.2, once you peel back all the jargon? Or is there some subtle difference? ♦

We know that Definition 4.8 is quite abstract. But have no fear, we will take you through it in pictures.

Example 4.11 (Bool-profunctors and their interpretation as bridges).

Let’s discuss Defi- nition 4.8 in the case V = Bool. One way to imagine a Bool-profunctor Φ : X → Y is in terms of building bridges between two cities. Recall that a preorder (a Bool-category) can be drawn using a Hasse diagram. We’ll think of the preorder as a city, and each vertex in it as some point of interest. An arrow A → B in the Hasse diagram means that there exists a way to get from point A to point B in the city. So what’s a profunctor?

A profunctor is just a bunch of bridges connecting points in one city to points in another. Let’s see a specific example. Here is a picture of a Bool-profunctor Φ : X → Y:

Both X and Y are preorders, e.g. with W ≤ N and b ≤ a. With bridges coming from the profunctor in blue, one can now use both paths within the cities and the bridges to get from points in city X to points in city Y. For example, since there is a path from N to e and E to a, we have Φ(N,e) = true and Φ(E,a) = true. On the other hand, since there is no path from W to d, we have Φ(W, d) = false.

In fact, one could put a box around this entire picture and see a new preorder with W ≤ N ≤ c ≤ a, etc. This is called the collage of Φ; we’ll explore this in more detail later; see Definition 4.42.

Exercise 4.12.

We can express Φ as a matrix where the (m, n)th entry is the value of Φ(m, n) \(\in\) \(\mathbb{B}\). Fill out the Bool-matrix:

We’ll call this the feasibility matrix of Φ.

Example 4.13 (Cost-profunctors and their interpretation as bridges).

Let’s now consider Cost-profunctors. Again we can view these as bridges, but this time our bridges are labelled by their length. Recall from Definition 2.53 and Eq. (2.56) that Cost-categories are Lawvere metric spaces, and can be depicted using weighted graphs. We’ll think of such a weighted graph as a chart of distances between points in a city, and generate a Cost-profunctor by building a few bridges between the cities.

Here is a depiction of a Cost-profunctor Φ: X Y:

The distance from a point x in city X to a point y in city Y is given by the shortest path that runs from x through X, then across one of the bridges, and then through Y to the destination y. So for example

Φ(B,x) = 11, Φ(A,z) = 20, Φ(C,y) = 17.

Exercise 4.15.

Fill out the Cost-matrix:

Remark 4.16 (Computing profunctors via matrix multiplication). We can give an algo- rithm for computing the above distance matrix using matrix multiplication. First, just like in Eq. (2.59), we can begin with the labelled graphs in Eq. (4.14) and read off the matrices of arrow labels for X, Y, and Φ:

Recall from Section 2.5.3 that the matrix of distances dY for Cost-category X can be obtained by taking the matrix power of MX with smallest entries, and similarly for Y.

The matrix of distances for the profunctor Φ will be equal to d\(_{X}\) ∗ M\(_{Φ}\) ∗ d\(_{Y}\).

In fact, since X has four elements and Y has three, we also know that \(\Phi=M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\).

Exercise 4.17.

Calculate \(\Phi=M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\), remembering to do matrix multiplication according to the (min, +)-formula for matrix multiplication in the quantale Cost; see Eq. (2.101).

Your answer should agree with what you got in Exercise 4.15; does it? ♦

Back to co-design diagrams

Each box in a co-design diagram has a left-hand and a right-hand side, which in turn consist of a collection of ports, which in turn are labeled by preorders. For example, consider the chassis box below:

Its left side consists of two ports one for load and one for velocity and these are the functionality that the chassis produces. Its right side consists of three ports one for torque, one for speed, and one for $ and these are the resources that the chassis requires. Each of these resources is to be taken as a preorder. For example, load might be the preorder ([0, ∞], ≤), where an element x \(\in\) [0, ∞] represents the idea “I can handle any load up to x.,” while $ might be the two-element preorder {up_to_$100, more_than_$100}, where the first element of this set is less than the second.

We then multiply—i.e. we take the product preorder of all preorders on the left, and similarly for those on the right. The box then represents a feasibility relation between the results. For example, the chassis box above represents a feasibility relation

Chassis : (load × velocity) → (torque × speed × $)

Let’s walk through this a bit more concretely. Consider the design problem of filming a movie, where you must pit the tone and entertainment value against the cost.

A feasibility relation describing this situation details what tone and entertainment value can be obtained at each cost; as such, it is described by a feasibility relation Φ: (T × E) → $. We represent this by the box

where T, E, and $ are the preorders drawn below:

A possible feasibility relation is then described by the profunctor

This says, for example, that a good-natured but boring movie costs $500K to produce (of course, the producers would also be happy to get $1M).

To elaborate, each arrow in the above diagram is to be interpreted as saying, “I can provide the source given the target”. For example, there are arrows witnessing each of “I can provide $500K given $1M”, “I can provide a good-natured but boring movie given $500K”, and “I can provide a mean and boring movie given a good-natured but boring movie”. Moreover, this relationship is transitive, so the path from (mean, boring) to $1M indicates also that “I can provide a mean and boring movie given $1M”.

Note the similarity and difference with the bridge interpretation of profunctors in Example 4.11: the arrows still indicate the possibility of moving between source and target, but in this co-design driven interpretation we understand them as indicating that it is possible to get to the source from the target.

Example 4.18.

In the above diagram, the node (g/n, funny) has no dashed blue arrow emerging from it. Is this valid? If so, what does it mean? ♦