Types containing with/rewrite clauses in agda, or, how to use rewrite instead of subst?

Those pipes indicate that reduction is suspended pending the result of the expressions in question, and it typically boils down to the fact that you had a with block whose result you need to know to proceed. This is because the rewrite construct just expands to a with of the expression in question along with any auxiliary values that might be needed to make it work, followed by a match on refl.

In this case, it just means that you need to introduce the +-comm n m in a with block and pattern match on refl (and you’ll probably need to bring n + m into scope too, as it suggests, so the equality has something to talk about). The Agda evaluation model is fairly straightforward, and if you pattern match on something (except for the faux pattern matches on records), it won’t reduce until you pattern match on that same thing. You might even be able to get away with rewriting by the same expression in your proof, since it just does what I outlined for you.

More precisely, if you define:

f : ...
f with a | b | c
...  | someDataConstructor | boundButNonConstructorVariable | someRecordConstructor = ...

and then you refer to f as an expression, you will get the pipes you observed for expression a only, because it matches on someDataConstructor, so at the very least to get f to reduce you will need to introduce a and then match on someDataConstructor from it. On the other hand, b and c, although they were introduced in the same with block, do no halt evaluation, because b doesn’t pattern match, and c‘s someRecordConstructor is known statically to be the only possible constructor because it’s a record type with eta.

Leave a Comment