Posts by Tags

Recursion as an Effect

10 minute read

Published: December 28, 2025

In one of my previous post I showed that any theory featuring general recursion is inconsistent when viewed as a logical system which inevitably leads to the idea that all definable functions in such a theory should be total (or productive). However, losing Turing-completeness could be somewhat problematic for some, but it can be addressed in several ways. One of these, an possibly the most popular, is to isolate recursion into a monad, effectively regarding recursion as an effect. We discuss several lifting monads which are fit for purpose.

On Lax Monoidal Functors

4 minute read

Published: December 19, 2025

What is the difference between

• a lax monoidal functor
• a monoid in a Day-monoidal category
• a morphism of lax-algebras for the free monoid 2-monad, and
• a codistributive law with the tensor product?

Bisimulations, Equality and Traces

5 minute read

Published: October 09, 2023

Strong bisimulation for CCS is the preferred equivalence method in concurrency because it relates less programs than trace equality. However, the reality is that is strong bisimulation and trace equality ought to be regarded as equivalent. This is the essence behind proof assistant’s like (e.g.) Isabelle. So what is going here?

The mini Yoneda lemma for Type Theorists

1 minute read

Published: September 09, 2023

I have managed to teach the Yoneda lemma to students who knew very little about category theory, here’s how you do it.

CCCs and the complete models of STLC

2 minute read

Published: March 16, 2023

Cartesian closed categories are not regarded as complete models of the Simply Typed \(\lambda\)-calculus in the traditional sense. Let’s see why.

Inconsistencies in Cartesian Closed Categories with fixed-points

5 minute read

Published: November 10, 2022

Any Cartesian Closed Category (CCC) with an initial object and a fixed-point operator is trivial. Essentially this means that in languages like (e.g.) Haskell the empty type is not actually empty as it contains the non-terminating computation. Perhaps this is obvious, but here’s the categorical explanation.

Recursion as an Effect

10 minute read

Published: December 28, 2025

In one of my previous post I showed that any theory featuring general recursion is inconsistent when viewed as a logical system which inevitably leads to the idea that all definable functions in such a theory should be total (or productive). However, losing Turing-completeness could be somewhat problematic for some, but it can be addressed in several ways. One of these, an possibly the most popular, is to isolate recursion into a monad, effectively regarding recursion as an effect. We discuss several lifting monads which are fit for purpose.

The Axiom of Choice in Type Theory

7 minute read

Published: November 25, 2022

The Axiom of Choice (AC) is an axiom that states that the product of a family of non-empty sets is itself non-empty. This is a rather controversial axiom amongst mathematicians but in type theory this axiom is provable within the logic.

Recursion as an Effect

10 minute read

Published: December 28, 2025

In one of my previous post I showed that any theory featuring general recursion is inconsistent when viewed as a logical system which inevitably leads to the idea that all definable functions in such a theory should be total (or productive). However, losing Turing-completeness could be somewhat problematic for some, but it can be addressed in several ways. One of these, an possibly the most popular, is to isolate recursion into a monad, effectively regarding recursion as an effect. We discuss several lifting monads which are fit for purpose.

On Lax Monoidal Functors

4 minute read

Published: December 19, 2025

What is the difference between

• a lax monoidal functor
• a monoid in a Day-monoidal category
• a morphism of lax-algebras for the free monoid 2-monad, and
• a codistributive law with the tensor product?

On Lax Monoidal Functors

4 minute read

Published: December 19, 2025

What is the difference between

• a lax monoidal functor
• a monoid in a Day-monoidal category
• a morphism of lax-algebras for the free monoid 2-monad, and
• a codistributive law with the tensor product?

Recursion as an Effect

10 minute read

Published: December 28, 2025

In one of my previous post I showed that any theory featuring general recursion is inconsistent when viewed as a logical system which inevitably leads to the idea that all definable functions in such a theory should be total (or productive). However, losing Turing-completeness could be somewhat problematic for some, but it can be addressed in several ways. One of these, an possibly the most popular, is to isolate recursion into a monad, effectively regarding recursion as an effect. We discuss several lifting monads which are fit for purpose.

Inconsistencies in Cartesian Closed Categories with fixed-points

5 minute read

Published: November 10, 2022

Any Cartesian Closed Category (CCC) with an initial object and a fixed-point operator is trivial. Essentially this means that in languages like (e.g.) Haskell the empty type is not actually empty as it contains the non-terminating computation. Perhaps this is obvious, but here’s the categorical explanation.

Recursion as an Effect

10 minute read

Published: December 28, 2025

In one of my previous post I showed that any theory featuring general recursion is inconsistent when viewed as a logical system which inevitably leads to the idea that all definable functions in such a theory should be total (or productive). However, losing Turing-completeness could be somewhat problematic for some, but it can be addressed in several ways. One of these, an possibly the most popular, is to isolate recursion into a monad, effectively regarding recursion as an effect. We discuss several lifting monads which are fit for purpose.

Bisimulations, Equality and Traces

5 minute read

Published: October 09, 2023

Strong bisimulation for CCS is the preferred equivalence method in concurrency because it relates less programs than trace equality. However, the reality is that is strong bisimulation and trace equality ought to be regarded as equivalent. This is the essence behind proof assistant’s like (e.g.) Isabelle. So what is going here?

The mini Yoneda lemma for Type Theorists

1 minute read

Published: September 09, 2023

I have managed to teach the Yoneda lemma to students who knew very little about category theory, here’s how you do it.

CCCs and the complete models of STLC

2 minute read

Published: March 16, 2023

Cartesian closed categories are not regarded as complete models of the Simply Typed \(\lambda\)-calculus in the traditional sense. Let’s see why.

Inconsistencies in Cartesian Closed Categories with fixed-points

5 minute read

Published: November 10, 2022

Any Cartesian Closed Category (CCC) with an initial object and a fixed-point operator is trivial. Essentially this means that in languages like (e.g.) Haskell the empty type is not actually empty as it contains the non-terminating computation. Perhaps this is obvious, but here’s the categorical explanation.

The Axiom of Choice in Type Theory

7 minute read

Published: November 25, 2022

The Axiom of Choice (AC) is an axiom that states that the product of a family of non-empty sets is itself non-empty. This is a rather controversial axiom amongst mathematicians but in type theory this axiom is provable within the logic.

CCCs and the complete models of STLC

2 minute read

Published: March 16, 2023

Cartesian closed categories are not regarded as complete models of the Simply Typed \(\lambda\)-calculus in the traditional sense. Let’s see why.