<div dir="ltr">Hi Jesper,<div> Thanks for the great reply. I had forgotten about passing of absurd hypotheses, I obviously spend too much time trying to prove things that are true in Agda...</div><div>Cheers,</div><div>Matthew</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 1, 2019 at 3:48 PM Jesper Cockx <<a href="mailto:Jesper@sikanda.be">Jesper@sikanda.be</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Hi Matthew,<br></div><div dir="ltr"><br></div><div dir="ltr">In our paper on definitional proof irrelevance (<a href="https://hal.inria.fr/hal-01859964" target="_blank">https://hal.inria.fr/hal-01859964</a>) we give a criterion for when it is allowed to pattern match on an irrelevant argument. As we argue in the paper, the condition that the datatype has a single constructor is neither sufficient nor necessary. The criterion we give is not yet implemented in Agda, but I hope to add it in the not-too-distant future (it depends on my PR <a href="https://github.com/agda/agda/pull/3589" target="_blank">https://github.com/agda/agda/pull/3589</a> being merged first). Unfortunately, the Acc datatype does not satisfy this criterion. In fact, allowing pattern matching on irrelevant Acc would break strong normalization of the theory, as you can always have an absurd hypothesis of type Acc but evaluation would not be blocked on this argument because it's irrelevant. So the best you can do is get propositional 
(instead of definitional)

 irrelevance by proving irrelevance of Acc by hand (or postulate it).</div><div dir="ltr"><br></div><div>A historical note: Agda used to allow matching on single-constructor datatypes under the --experimental-irrelevance flag, but this was completely broken so I decided to remove it last year (<a href="https://github.com/agda/agda/commit/b5f8b509bbe362c4bbb14612a6666e720cabf26a" target="_blank">https://github.com/agda/agda/commit/b5f8b509bbe362c4bbb14612a6666e720cabf26a</a>)<br></div><div dir="ltr"><br></div><div>-- Jesper<br></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 1, 2019 at 8:33 AM Matthew Daggitt <<a href="mailto:matthewdaggitt@gmail.com" target="_blank">matthewdaggitt@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"> In the Agda <a href="https://agda.readthedocs.io/en/v2.6.0/language/irrelevance.html" target="_blank">documentation</a> it is pretty clear that the only time you can pattern match against irrelevant arguments is when the type is empty. My own reasoning for this has always been that this is to stop decisions being made depending on the result of the pattern match. This leads me to wonder if there are any theoretical reasons why it's not possible to also mark a type irrelevant when it only has a single constructor?<br></div><div><br></div><div>Consider the motivating example below. Clearly the `Acc` argument is never actually used in the computation of the final value, and no decisions can be based on its value as it only has a single constructor. It seems like it should be possible to mark it irrelevant. If this were possible then we would immediately get rid of a whole bunch of annoying congruence lemmas.</div><div dir="ltr">```<br><div>gcd : (m n : ℕ) → Acc _<_ m → n < m → ℕ</div><div>gcd m zero     _         _   = m</div><div>gcd m (suc n) (acc rec) n<m = gcd′ (suc n) (m % suc n) (rec _ n<m) (a%n<n m n)</div><div>```</div><div>Many thanks,</div><div>Matthew</div></div></div>
_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se" target="_blank">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" rel="noreferrer" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br>
</blockquote></div>
</blockquote></div>