使用 with-abstraction 的终止检查失败

Question

我很惊讶地看到以下函数未能通过终止检查。 y ∷ ys 在结构上比 x ∷ y ∷ ys 小，不是吗？

open import Data.List using (List ; [] ; _∷_)
open import Data.Nat using (ℕ ; zero ; suc)
open import Data.Nat.Properties using (<-cmp)

foo : List ℕ → ℕ
foo [] = 0
foo (x ∷ []) = 1
foo (x ∷ y ∷ ys) with <-cmp x y
... | _ = suc (foo (y ∷ ys))

做以下两件事中的一件（或两件）似乎能让终止检查器看到曙光：

删除 with-抽象。
更改最后一个子句以匹配 y ∷ ys 而不是 x ∷ y ∷ ys 并使用 ys 而不是 y ∷ ys 进行递归。（由于缺少 x，还将 <-cmp x y 更改为 <-cmp y y。）

现在我比平时更困惑了，我想知道：发生了什么，with-抽象（及其辅助函数）如何影响所有这些，以及做什么我怎么办？

我看过有关终止的其他问题和答案，但是 - 与那些更复杂的情况不同 - 手头的情况似乎是关于基本结构递归，不是吗？

更新

我刚刚找到了问题的答案，但如果有人想更清楚地了解到底发生了什么，例如，with-抽象究竟如何干扰终止检查，那么我'我会非常乐意接受那个答案。

Answer 1

事实证明，这是自 2.6.1 以来终止检查器的已知限制。请参阅 2.6.1 更改日志中的 终止检查 部分：https://github.com/agda/agda/blob/v2.6.1/CHANGELOG.md

模式匹配和递归调用不适用于它们之间的 with-抽象。一种解决方法是也对递归调用进行抽象，以便 将其上拉 到 with- 抽象中（从 with- 抽象之后的原始位置） .

open import Data.List using (List ; [] ; _∷_)
open import Data.Nat using (ℕ ; zero ; suc)
open import Data.Nat.Properties using (<-cmp)

foo : List ℕ → ℕ
foo [] = 0
foo (x ∷ []) = 1
foo (x ∷ y ∷ ys) with foo (y ∷ ys) | <-cmp x y
... | rec | _ = suc rec

在上面的代码中，模式匹配 x ∷ y ∷ ys 和递归调用 foo (y ∷ ys) 不再跨越 with 抽象，终止检查成功。

以上解决了我的问题，但更改日志描述了更微妙的情况，需要多加注意。

此问题在 Agda 问题 #59 (!) 中进行了跟踪，其中包含更多详细信息和问题的历史记录：https://github.com/agda/agda/issues/59

使用 with-abstraction 的终止检查失败

Failing termination check with a with-abstraction

agda