# What should we return when pattern matching on a Path constructor?

Context: Cubical Type Theory

Consider a simple HIT, say, an HitInt:

data HitInt : Set where
pos : (n : ℕ) → HitInt
neg : (n : ℕ) → HitInt
posneg : pos 0 ≡ neg 0


Or, if you don't speak Agda we can use cubicaltt:

data int = pos (n : nat)
| neg (n : nat)
| zeroP <i> [ (i = 0) -> pos zero
, (i = 1) -> neg zero ]


We want to define, for instance, a succ operation for it. As a functional programmer, we want to pattern matching on this HIT. In Agda, it's:

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (neg zero) = pos 1
sucHitInt (neg (suc n)) = neg n
sucHitInt (posneg x) = pos 1


Or in cubicaltt:

sucInt : int -> int = split
pos n -> pos (suc n)
neg n -> sucNat n
where sucNat : nat -> int = split
zero -> pos one
suc n -> neg n
zeroP @ i -> pos one


What I'm interested in is the last case-split of these two pattern matchings. The function is supposed to return the successor of the input integer, but we need to implement something that "finds the successor of the input Path".

My question is, how are we supposed to implement this case-split? In the cubicaltt version (taken from the cubicaltt's GitHub repository, examples/integer.ctt), it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer. Is this really what we want to do? Why it's not returning a Path like <i> pos 1 (even this is not a member of the higher inductive family)?

What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer

My understanding is that it matches points of path rather than path itself. This is why the matching is on posneg x (where x : I) rather than posneg itself.

Since paths can be seen as (special) maps from I, we can think of HIT constructors as just a special of regular constructors, i.e.

  posneg : I ↝ HitInt [i0 ↦ pos 0 ; i1 ↦ neg 0]


where if you ignore "special" properties of Interval, it looks like a regular constructor (in cubicaltt notation it already looks similar except that I is always treated specially).

What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

It's the only way to satisfy constraints imposed by previous definitions (this works for both zero cases). In fact, Agda can correctly solve even two holes (in right order):

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (posneg i) = {!!}
sucHitInt (neg zero) = {!!}
sucHitInt (neg (suc n)) = neg n


Why it's not returning a Path like pos 1 (even this is not a member of the higher inductive family)?

Again, since we're matching on points rather than paths; for symmetry it's possible to imagine that case as equal to:

sucHitInt (posneg i) = (λ _ → pos 1) i


reading somewhat like "for all projections from I at i to path posneg we have projections from I at I to constant path (λ _ → pos 1)". This doesn't quite work in Agda (because typecheking lambda application directly isn't very well supported), however the following (with the same meaning) does:

sucHitInt (posneg i) = refl {x = pos 1} i


Finally, abusing notation, we could rewrite that as

(ap sucHitInt posneg) i = (refl {x = pos 1}) i


(where ap (from the HoTT book) corresponds to cong in typical Agda) and, getting rid of i from the both sides, recover path to path mapping.

PS: i'm new to cubical myself, so hopefully someone can correct or extend my answer

• Yes, thanks for pointing out the interval parameter in the Path constructor! This is very helpful! – ice1000 Jan 21 '19 at 0:20
• By the way, is ↦ and ↝ used generally as you use them (for path endpoints and abstraction) in type theory? – ice1000 Jan 21 '19 at 0:22
• @ice1000 I chose ↝ just as a fancy arrow, i don't know if it was used as such. As for ↦, it's quite commonly used in lambdas and i think i've seen it in such context as well – caryoscelus Jan 21 '19 at 0:41