agda

Defining operations on HITs


I am a simple man who does not really understand all the ins and outs of Cubical Agda. I have attempted to read its docs, and HoTT, and stopped following what was going on fairly quickly.

What I am specifically hoping for is an example of how to write a simple operation for a higher inductive type, ideally without libraries outside of Cubical.Core.Everything.

For a specific example, let's consider the integers as a quotient over pairs of naturals:

data N : Set where
  0N : N
  suc : N -> N

_+N_ : N -> N -> N
0N +N n = n
suc m +N n = suc (m +N n)

data Z : Set where
  zpair : N -> N -> N
  zeq : (a b c d : N) -> (a +N d) === (b +N c) -> zpair a b === zpair c d

_+Z_ : Z -> Z -> Z
zpair a b + zpair c d = zpair (a +N c) (b +N d)
zeq a b c d ad=bc i + zeq e f g h eh=fg j = ???

I can and have worked my way through e.g. zpair + zeq and vice versa, where there's an i : I and I can just construct an appropriate path and apply it to i. I don't understand what to do when I have i j : I and I'm combining the points on the paths together, and in particular it doesn't look like I can just wedge them together, nor do I see an obvious composition or a value in I to apply it to.

A satisfactory answer would fill in the ???, assuming any necessary convenient lemmas on _+N_ and using the equational reasoning API as necessary.

I've looked at definitions of the integers in Agda that define them as a quotient, but I can't find where this sort of operation is defined.


Solution

  • The usual approach to this is to add a set truncation constructor, like

      squash : isSet Z
    

    This ensures that you can fill in any square in Z, for example using isSet→SquareP. (Note that isSet Z unfolds to something that has the right shape to be used as the type of a higher constructor.)

    You can see this approach in action in the cubical library here: note that is defined as the quotient of ℕ × ℕ by some relation rel, where quotients are defined as a higher inductive type with a squash/ constructor that forces the quotient to be a set.

    For another approach that does not require truncating, see the 1lab: here we restrict the path constructor to relating pairs of the form (x, y) and (x + 1, y + 1). You can convince yourself that this does not introduce any non-trivial loops, so that the resulting HIT is a set (start by drawing ℕ × ℕ as a grid, then draw a line between every pair of points that is related by a path; do you see how this differs from the previous approach?).

    Once this is in place, it is common to abstract away the details of the implementation by defining a recursion principle for the integers, which often can have a simpler form if we assume that the target type is of lower h-level (in this case, a set).