Pinned Tweet
My answers to my 4 favorite StackOverflow questions: roboguy13.github.io/
David Young retweeted
Replying to @ShriramKMurthi
Meanwhile the rest of us schmucks had to make do with this

ALT Screenshot of a window from "Mavis Beacon Teaches Typing" for Windows XP, featuring Mavis Beacon (a tall Black woman with long hair and a suit, arms folded and smiling) next to a whiteboard. The image has been edited so that the whiteboard instead displays the inference rules for the simply-typed lambda calculus
New blog post introducing string diagrams: this is a visual language that we can use to talk about many different kinds of type systems.
Then I use them to show how a monad really *is* a monoid in a category of endofunctors.
roboguy13.github.io/blog/str…
Difficult choices to make. I really liked Disco Elysium but did it actually shape me more than these? Should I include Apex Legends or Overwatch over something else? What about Baldur's Gate 3? Dunno.
This is what I'm thinking today, anyway.
1
5
455
The connection between monads and monoids ("monads are monoid objects in a category of endofunctors"):
Replying to @tritlo
To me, that's the definition where it's less clear that it's a monoid object.
What I think is really interesting is that if you look at the string diagram equations showing the monad laws (in terms of unit and join), they are visually identical to the string diagrams showing the usual monoid laws (just with different labels).
If you join three layers together into one by using join twice, it doesn't matter if you start by joining the inner two layers or you start by joining the outer two layers. That's exactly the associativity.
In the string diagram equations below: read these like "circuit diagrams" with "data" flowing upward from the bottom. The open circle is the unit, and the parts where three wires meet (two inputs, one output) is the multiplication. The inputs to the diagram are where a wire meets the bottom boundary, and an output is where a wire meets the top boundary.
If we think of the unit and multiplication like the operations of a traditional monoid, then the first two equations are the usual unit laws. The last equation is associativity.
But if we think of the "inputs" as being "layers" of F for some endofunctor F (using fmap when needed to "go under" a layer), and the multiplication is the join operation, then these equations are *exactly* the monad equations!
3
642
The relationship between dependent products (aka dependent function types) and exponentiation (non-dependent function types).
Replying to @roboguy20 @bouguereau_stan
I was reminded of this again today and I think I came up with a better way to explain what's happening here.
Pi types are often written as in the attached image, very much like traditional product notation.
To think of this numerically, the "body" is a number that depends on a.
Numerically, if the body does not actually reference a at all, then the whole product is equal to the number n^|A| (where n is the body).
For example, think of A as being the set {True, False} and the body is `if a then 2 else 4`. This gives you 2 * 4 = 8. And the type system equivalent of that could be something like A = Bool and B = `if a then Bool else (Bool + Bool)`. In that example there are 8 possible values of type Pi_(a : A) B, matching the number you get in the numeric version.
But in terms of types, if the "body" of the product does not refer to a, this is exactly the same as a non-dependent function type. But that's an exponential (*and* a product)!
So for instance, take A = {True, False} again and let B = 4. Then the product is 4 * 4, or 4^2 = 16. And likewise, there are 16 possible functions of type Pi_(a : Bool) (Bool + Bool).
In the non-dependent case, they are exactly the iterated products that correspond to exponentials!
A non-technical example of proof relevance:
Say you're hosting a party. You want to make sure that each guest has one chair, and each chair has one guest. There are two ways to approach this:
(1) Someone tells you the number of guests and someone else tells you the number of chairs. You make sure that the two numbers are equal. That's all you can say from only knowing the numbers.
(2) You could write down an explicit pairing, associating one guest with one chair and vice versa: this guest sits in this specific chair, etc. This gives a seating chart.
The second one establishes the same fact as the first one, plus some additional information given by the explicit one-to-one correspondence. When a guest asks "where do I sit" it gives one specific answer, unlike the first one.
Crucially, there are multiple different ways to make the correspondence in (2), giving you multiple different seating charts. Each seating chart is a proof of the fact that there are as many chairs as guests. The fact that there can be multiple distinct charts is proof relevance.
Inductive relations can be fun and useful to work with in proof assistants. I wonder where there could be similar objects in other parts of math?
I guess I see them as having two characteristic aspects, beyond "just" being relations:
1. They can be "proof relevant," meaning that there can be multiple witnesses for the same related "tuple." A good example is the ElementOf : List A → A → Type relation. A list of natural numbers might have multiple 3s in it. The witness tells us where to find one particular 3.
2. They have an induction principle, and there can be multiple inductive relations with different induction principles which give you (the extension of) the same relation. An example of that is that there are multiple different ways to define the ≤ on natural numbers as an inductive relation, with different induction principles. These are logically equivalent, but sometimes one can be easier to work with than another.
I think spans give you the first part. A span is a diagram of the shape `A ← X → B` in a category. The X is called the apex of the span and A and B are its feet. We can think of the generalized elements of X as being witnesses for a relation between A and B. Different generalized elements of X can correspond to the same "related pair" of A and B.
So, from that perspective, spans are like proof relevant relations. A span is "proof irrelevant" if there's at most one witness for each "related pair" (this is exactly when the span is "jointly monic").
Recursion principles, before we get to induction principles, I associate with initial algebras of endofunctors. An algebra of an endofunctor F is a morphism of the shape `F A → A` in our category for some A. These F-algebras form a category, where the objects are F-algebras and the morphisms are commutative squares. If that category has an initial object `F(Z) → Z`, we know that this map is actually one half of an isomorphism between Z and F(Z) (this fact is known as Lambek's lemma), so Z is the initial fixpoint for F. The recursion principle comes from the morphisms guaranteed to exist by the fact that the algebra is initial.
The induction principle part is where I get hazier. I think we start with a fibration `E → B` where our endofunctor F will be on B, and our predicates live in E, and we again consider the category of F-algebras. At some point I should try working through this in more detail and see if I can also see where proof relevance might come up there (maybe spans in B?)...
3
366
Here's an interesting encoding of loopless (multi-)graphs in Agda.
Something I like about this is that we can use the computational content of (Bishop-)finiteness proofs to compute the incident edges of a node, by starting with a finite graph.
First, I define a finite graph as one where its node type and edge type are Bishop-finite.
Then, given a particular node A, we have a boolean-valued predicate `Edge → Bool` which says whether or not it connects to A. This carves out a subset of our Bishop-finite Edge type.
Because this is a *boolean-valued* predicate (rather than the Type-valued predicates I mentioned in a previous post), we can constructively prove that such a subset is always finite. A proof of this fact gives us an enumeration of the edges satisfying our predicate, as well as the degree of A (since it also tells us the size of our subset).
For completeness, this is the definition of Subset in this: it's the fiber over `true` of the predicate
1
4
148
This graph encoding is why I was thinking about the finite subset thing I mention in the post here: nitter.cf/roboguy20/status/20922…
Unlike in that post, we only need to consider predicates which we *can* always decide (boolean-valued ones) so we don't run into the same "problem."
Constructive math and classical math both have their initially unintuitive aspects.
As an example, consider the disjunction property. This says that if our theory can prove the disjunction A ∨ B, then our theory can prove A or prove B. This is a property that you might naively expect provability to have.
Classical logic actually does not have that property! Something like intuitionistic propositional logic, on the other hand, does have it.
In classical math, we have LEM which says that we can always prove A ∨ ¬A no matter what A is. But A could be independent of our theory. In that case, we cannot prove A and we cannot prove ¬A, even though LEM allows us to prove A ∨ ¬A. The presence of LEM fairly directly destroys the disjunction property (unless the theory is complete).
On the other hand, here's an unintuitive fact for constructive math: First, we can define "A is finite" as saying that there is a bijection with a set consisting of natural numbers from 0 to N-1 for some N (this is called "Bishop-finiteness"). Then, using this notion of "finite," we cannot prove that all subsets of a finite set are themselves finite.
Constructively, in order to prove a set is finite we need to exhibit an enumeration of its elements. But a subset can be defined as the comprehension of any definable predicate, including ones we can't decide in our theory. In the case of such an undecidable predicate, we can't decide which elements are in its extension.
To be concrete, let's look at a singleton set {a}. We can take any arbitrary proposition P, and define a subset {x ∈ {a} | P}. But if we could prove that this subset is Bishop-finite, we can determine whether or not P is true by looking at the N given by our enumeration. ¬P holds if N = 0 and P holds if N = 1.
Since P can be any proposition, this just gives us LEM!
2
275
Constructive math and classical math both have their initially unintuitive aspects.
As an example, consider the disjunction property. This says that if our theory can prove the disjunction A ∨ B, then our theory can prove A or prove B. This is a property that you might naively expect provability to have.
Classical logic actually does not have that property! Something like intuitionistic propositional logic, on the other hand, does have it.
In classical math, we have LEM which says that we can always prove A ∨ ¬A no matter what A is. But A could be independent of our theory. In that case, we cannot prove A and we cannot prove ¬A, even though LEM allows us to prove A ∨ ¬A. The presence of LEM fairly directly destroys the disjunction property (unless the theory is complete).
On the other hand, here's an unintuitive fact for constructive math: First, we can define "A is finite" as saying that there is a bijection with a set consisting of natural numbers from 0 to N-1 for some N (this is called "Bishop-finiteness"). Then, using this notion of "finite," we cannot prove that all subsets of a finite set are themselves finite.
Constructively, in order to prove a set is finite we need to exhibit an enumeration of its elements. But a subset can be defined as the comprehension of any definable predicate, including ones we can't decide in our theory. In the case of such an undecidable predicate, we can't decide which elements are in its extension.
To be concrete, let's look at a singleton set {a}. We can take any arbitrary proposition P, and define a subset {x ∈ {a} | P}. But if we could prove that this subset is Bishop-finite, we can determine whether or not P is true by looking at the N given by our enumeration. ¬P holds if N = 0 and P holds if N = 1.
Since P can be any proposition, this just gives us LEM!
A nice description of the principle of induction as corresponding to saying something is the "smallest" "thing" (here, a set using the subset ordering) satisfying some closure property.
In this perspective, we start with some predicate P on (in this case) the natural numbers which is closed under the Peano operations. This predicate describes some subset of the natural numbers (its extension).
Induction lets us use the fact that the set of natural numbers is the *smallest* set closed under the Peano operations to show that our subset is actually the *entire* set of natural numbers (and so our predicate holds for every natural number). That's because our subset is closed under the Peano operations and is a subset of the natural numbers. But that can only happen if it *is* the set of natural numbers, since the set of natural numbers is already the smallest set that's closed in that way.
This is a reusable idea, going very much beyond just the natural numbers.
carloangiuli.com/courses/b52…
4
8
494
@Aron_Adler thought you might find this interesting if you're not already familiar with this idea
1
79
One kind of intuition for topology
Replying to @caballerobrah
the main issue I had with topology is that some of the resources I was trying to learn from didn't seem to talk much about what sort of general intuition we should have about it.
"Topology Via Logic," I think, does a much better job there, although it's also approaching it from a very unusual (but very explicitly CS-/PL-relevant) perspective.
A topology is something like a set together with a collection of observations we're allowed to make about the things in that set.
Imagine you're measuring stuff. Your measuring tape has a limited precision, so the observations you're allowed to make are limited to that precision. You are able to, in some cases, make an observation like "this is greater than 5 ft." But you can never make the observation "this is *exactly* 5 ft."
Logic also has this. Some statements are falsifiable but not "affirmable" ("there are no black swans"). And, closely related, so does computation ("this program does not halt").
The open sets of a topology tell you the observations you can make about the things in the set using "finite" information. A continuous function is exactly a function where any observation about the output gives you an observation about the input.
There is actually a very direct path from some fundamentals of logic to the actual definition of a topological space, where you only talked about logic the entire time (no explicit geometric or spatial things, etc).
1
3
760
Continues here: nitter.cf/roboguy20/status/20890…
Replying to @caballerobrah
I agree. To round it out a bit, here's a somewhat brief version of how you end up with the definition of a topological space from logic.
Say we're thinking about a "logic of finite observations" (all of my examples could be thought of as being instances of that).
We might wonder under which logical operations this is closed. Meaning, which operations always give back a finite observation if we give them finite observations as their inputs?
Well, logical AND and logical OR work. For AND, we just try to observe the two pieces. For OR, we only need to observe one of them.
But also, we can observe an *infinite* disjunction. In order to affirm an infinite disjunction, we only need to affirm one of its disjuncts (making a single finite observation).
Conjunction, on the other hand, does not work that way. We'd need to make an *infinite* observation in order to observe an infinite conjunction, which is not allowed.
Finally, there is the "trivially true" observation which is true of everything, and the "trivially false" observation which is false of everything. Those are surely finite, since they don't actually require any information.
We now think of the things we're observing as being some set X of "points." Each observation will be a subset of X, consisting of the points that it holds true for. These are what we call open sets.
Logical AND is intersection of open sets, and logical OR is union of open sets.
In those terms, what we just said is that the union (OR) of some (possibly infinite) collection of open sets must also be an open set. The intersection (AND) of a *finite* collection of open sets must be an open set. The set X itself must be open (trivially true), and the empty set must be open (trivially false).
That is exactly the definition of a topology on the set X.
If you're interested in learning more about topology from this CS/PL/logic perspective, I think the book Topology Via Logic is very good. Also, Martin Escardo has a nice monograph "Synthetic Topology: of Data Types and Classical Spaces" which is freely available here: sciencedirect.com/science/ar…
Both of those, particularly the first parts, are more friendly than you might expect. The Escardo one uses a lot of Haskell examples to demonstrate the ideas.
106
















