让 Agda 相信递归函数正在终止
Convincing Agda that a recursive function is terminating
我在说服 Agda 函数递归调用中的参数在结构上小于传入参数时遇到了一些困难。
我定义了对、对列表（将有限函数表示为 input/output 对中的 "sets"）以及此类列表的并集，如下所示：
data _x_ {l : Level} (A B : Set l) : Set l where
<_,_> : A -> B → A x B
data FinFun (A B : Set) : Set where
nil : FinFun A B
_::_ : A x B → FinFun A B → FinFun A B
_U_ : {A B : Set} -> FinFun A B -> FinFun A B -> FinFun A B
nil U f' = f'
(x :: xs) U f' = x :: (xs U f')
我还定义了 "neighborhoods" 和两个这样的邻域的上界：
data UniNbh : Set where
bot : UniNbh
lam : FinFun UniNbh UniNbh -> UniNbh
_u_ : UniNbh -> UniNbh -> UniNbh
bot u bot = bot
bot u (lam f) = lam f
(lam f) u bot = lam f
(lam f) u (lam f') = lam (f U f')
最后，对于这个问题最重要的是，我定义了一个函数，给定一个邻域对列表，它取列表中所有对的第一个分量的上界：
pre : FinFun UniNbh UniNbh -> UniNbh
pre nil = bot
pre (< x , y > :: f) = x u pre f
给我带来麻烦的互递归函数本质上是这样的：
f : UniNbh -> UniNbh -> UniNbh -> Result
-- Base cases here. When any argument is bot or lam nil, no
-- recursion is needed.
f (lam (a ∷ as)) (lam (b ∷ bs)) (lam (c ∷ cs)) =
f (lam (a ∷ as)) (pre (b ∷ bs)) (lam (c ∷ cs))
pre f 小于 lam f，或者其中一个基本情况将结束递归似乎很明显，但 Agda 看不到这一点是可以理解的。为了解决这个问题，我尝试了很多不同的想法，但都没有奏效。在这一点上，我认为唯一的方法是使用标准库中的 Induction.WellFounded，但我不知道如何使用。
我未能成功证明以下数据类型是有根据的：
data preSmaller : UniNbh -> UniNbh -> Set where
pre-base : preSmaller (pre nil) (lam nil)
pre-step : ∀ (x y f f') ->
preSmaller (pre f) (lam f') ->
preSmaller (pre (< x , y > :: f')) (lam (< x , y > :: f'))
我什至不确定这种数据类型是否有用，即使我可以证明它是有根据的。
当四处寻找有关如何使用 Induction.WellFounded 的信息时，我只能找到非常简单的例子来表明 < 对于自然数 是有根据的，但我无法概括这些想法对于这种情况。
抱歉这么久 post。任何帮助将不胜感激！
由于某些 unicode，我看不到全部定义 - 您引入的许多字符都呈现为正方形。 WellFounded 的基本思想并不是某种数据类型变小的证明。基本思想是 Agda 可以看到 Acc _<_ x 由包裹在 Acc _<_ y 中的访问函数构造的变得更小。
在你的情况下，preSmaller 似乎就是这样一个 _<_。很难判断是否是这样，因为缺少很多文本。然后你需要构造一个函数，可以为给定的任意两个 x y : UniNbh.
构建一个 Acc preSmaller y
编辑后的问题仍然遗漏了一些定义（例如，什么是 post nil。但我明白了正在发生的事情的要点。
您对 preSmaller 的定义类似于 Nat 对 _<_ 的以下定义：
data _<_ : Nat -> Nat -> Set where
z< : {n : Nat} -> zero < (succ n)
s<s : {m n : Nat} -> m < n -> (succ m) < (succ n)
请注意，它与标准定义不同，因为 m 和 n 都变大了。这会影响 WellFounded-ness 证明的构建。
-- may just as well import, but let me be self-contained:
data Acc {A : Set} (_<_ : A -> A -> Set) (x : A) : Set where
acc : ((y : A) -> y < x -> Acc _<_ y) -> Acc _<_ x
Well-founded : (A : Set) -> (R : A -> A -> Set) -> Set
Well-founded A _<_ = (x : A) -> Acc _<_ x
{-# BUILTIN EQUALITY _==_ #-} -- rewrite rule needs this, if I am not using
-- Unicode version of it from Prelude
<-Well-founded : Well-founded Nat _<_
<-Well-founded zero = acc \_ ()
<-Well-founded (succ x) = acc aux where
aux : (y : Nat) -> y < (succ x) -> Acc _<_ y
aux zero _ = <-Well-founded zero
aux (succ y) (s<s y<x) with <-Well-founded x | is-eq? (succ y) x
... | acc f | no sy!=x = f (succ y) (neq y<x sy!=x)
... | wf-x | yes sy==x rewrite sy==x = wf-x
辅助函数：
data False : Set where
false-elim : {A : Set} -> False -> A
false-elim ()
data Dec (A : Set) : Set where
yes : A -> Dec A
no : (A -> False) -> Dec A
_==?_ : {A : Set} -> A -> A -> Set
_==?_ x y = Dec (x == y)
s== : {m n : Nat} -> (succ m) == (succ n) -> m == n
s== refl = refl
is-eq? : (m n : Nat) -> m ==? n
is-eq? zero zero = yes refl
is-eq? (succ m) zero = no \()
is-eq? zero (succ n) = no \()
is-eq? (succ m) (succ n) with is-eq? m n
... | no f = no \sm=sn -> f (s== sm=sn)
... | yes m=n = yes (cong succ m=n)
-- if m < n and m+1 /= n, then m+1 < n
neq : {m n : Nat} -> m < n -> ((succ m) == n -> False) -> (succ m) < n
neq {_} {zero} ()
neq {zero} {succ zero} z< f = false-elim (f refl)
neq {zero} {succ (succ n)} z< f = s<s z<
neq {succ m} {succ n} (s<s m<n) f = s<s (neq m<n \m=n -> f (cong succ m=n))
要带走的重要物品：
_<_ 的标准定义允许构建更简单的 WellFounded-ness 证明，因为可以一次递减一个参数。 _<_ 的不同定义需要减少两者，这似乎是一个问题。然而，使用辅助函数 neq 可以构造一个递归，其中只有一个和相同的参数变小。
_==_ 对 Nat 的可判定性允许我构建这样的递归。 Agda 可以看到对 <-WellFounded 的递归调用是针对结构较小的 x，因此终止。然后根据相等性测试的结果使用不同的结果。使用 neq 的分支计算必要的 Acc 给定 <-WellFounded 为更小的 x 发现的函数：函数终止，因为 Agda 允许构造这样的函数。另一个分支 x == (succ y) 按原样使用值，因为 rewrite 使 Agda 相信它是正确的类型。
通过构造 <-WellFounded:
的实例，然后可以使用有根据性来证明函数终止
_-|-_ : Bin -> Bin -> Bin
x -|- y with max-len x y
... | n , (x<n , y<n) = Sigma.fst (a (<-Well-founded n) b (x , x<n) (y , y<n)) where
a : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ n)
a+O : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ (succ n))
a+I : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ (succ n))
a+O f c m n with a f c m n
... | r , r<n = r O , s<s r<n
a+I f c m n with a f c m n
... | r , r<n = r I , s<s r<n
a {zero} _ _ (_ , ())
a {succ sz} (acc f) cc mm nn with cc | mm | nn
... | b | m O , s<s m< | n O , s<s n< = a+O (f sz n<n1) b (m , m<) (n , n<)
... | b | m O , s<s m< | n I , s<s n< = a+I (f sz n<n1) b (m , m<) (n , n<)
....-- not including the whole thing here - it is too long.
我不包括两个二进制数加法的整个构造（也不是有效的 - 只是证明有根据的练习）。这里要注意的重要一点是递归是如何开始的，以及它是如何被重用来构造新的 Acc 实例来匹配类型的——这里 S-Bin 表示最多位长度的二进制数 n，而 Agda 确信 Acc _<_ n 变小了，即使它不能证明 S-Bin n 变小。
我在说服 Agda 函数递归调用中的参数在结构上小于传入参数时遇到了一些困难。
我定义了对、对列表（将有限函数表示为 input/output 对中的 "sets"）以及此类列表的并集，如下所示：
data _x_ {l : Level} (A B : Set l) : Set l where
<_,_> : A -> B → A x B
data FinFun (A B : Set) : Set where
nil : FinFun A B
_::_ : A x B → FinFun A B → FinFun A B
_U_ : {A B : Set} -> FinFun A B -> FinFun A B -> FinFun A B
nil U f' = f'
(x :: xs) U f' = x :: (xs U f')
我还定义了 "neighborhoods" 和两个这样的邻域的上界：
data UniNbh : Set where
bot : UniNbh
lam : FinFun UniNbh UniNbh -> UniNbh
_u_ : UniNbh -> UniNbh -> UniNbh
bot u bot = bot
bot u (lam f) = lam f
(lam f) u bot = lam f
(lam f) u (lam f') = lam (f U f')
最后，对于这个问题最重要的是，我定义了一个函数，给定一个邻域对列表，它取列表中所有对的第一个分量的上界：
pre : FinFun UniNbh UniNbh -> UniNbh
pre nil = bot
pre (< x , y > :: f) = x u pre f
给我带来麻烦的互递归函数本质上是这样的：
f : UniNbh -> UniNbh -> UniNbh -> Result
-- Base cases here. When any argument is bot or lam nil, no
-- recursion is needed.
f (lam (a ∷ as)) (lam (b ∷ bs)) (lam (c ∷ cs)) =
f (lam (a ∷ as)) (pre (b ∷ bs)) (lam (c ∷ cs))
pre f 小于 lam f，或者其中一个基本情况将结束递归似乎很明显，但 Agda 看不到这一点是可以理解的。为了解决这个问题，我尝试了很多不同的想法，但都没有奏效。在这一点上，我认为唯一的方法是使用标准库中的 Induction.WellFounded，但我不知道如何使用。
我未能成功证明以下数据类型是有根据的：
data preSmaller : UniNbh -> UniNbh -> Set where
pre-base : preSmaller (pre nil) (lam nil)
pre-step : ∀ (x y f f') ->
preSmaller (pre f) (lam f') ->
preSmaller (pre (< x , y > :: f')) (lam (< x , y > :: f'))
我什至不确定这种数据类型是否有用，即使我可以证明它是有根据的。
当四处寻找有关如何使用 Induction.WellFounded 的信息时，我只能找到非常简单的例子来表明 < 对于自然数 是有根据的，但我无法概括这些想法对于这种情况。
抱歉这么久 post。任何帮助将不胜感激！
由于某些 unicode，我看不到全部定义 - 您引入的许多字符都呈现为正方形。 WellFounded 的基本思想并不是某种数据类型变小的证明。基本思想是 Agda 可以看到 Acc _<_ x 由包裹在 Acc _<_ y 中的访问函数构造的变得更小。
在你的情况下，preSmaller 似乎就是这样一个 _<_。很难判断是否是这样，因为缺少很多文本。然后你需要构造一个函数，可以为给定的任意两个 x y : UniNbh.
Acc preSmaller y
编辑后的问题仍然遗漏了一些定义（例如，什么是 post nil。但我明白了正在发生的事情的要点。
您对 preSmaller 的定义类似于 Nat 对 _<_ 的以下定义：
data _<_ : Nat -> Nat -> Set where
z< : {n : Nat} -> zero < (succ n)
s<s : {m n : Nat} -> m < n -> (succ m) < (succ n)
请注意，它与标准定义不同，因为 m 和 n 都变大了。这会影响 WellFounded-ness 证明的构建。
-- may just as well import, but let me be self-contained:
data Acc {A : Set} (_<_ : A -> A -> Set) (x : A) : Set where
acc : ((y : A) -> y < x -> Acc _<_ y) -> Acc _<_ x
Well-founded : (A : Set) -> (R : A -> A -> Set) -> Set
Well-founded A _<_ = (x : A) -> Acc _<_ x
{-# BUILTIN EQUALITY _==_ #-} -- rewrite rule needs this, if I am not using
-- Unicode version of it from Prelude
<-Well-founded : Well-founded Nat _<_
<-Well-founded zero = acc \_ ()
<-Well-founded (succ x) = acc aux where
aux : (y : Nat) -> y < (succ x) -> Acc _<_ y
aux zero _ = <-Well-founded zero
aux (succ y) (s<s y<x) with <-Well-founded x | is-eq? (succ y) x
... | acc f | no sy!=x = f (succ y) (neq y<x sy!=x)
... | wf-x | yes sy==x rewrite sy==x = wf-x
辅助函数：
data False : Set where
false-elim : {A : Set} -> False -> A
false-elim ()
data Dec (A : Set) : Set where
yes : A -> Dec A
no : (A -> False) -> Dec A
_==?_ : {A : Set} -> A -> A -> Set
_==?_ x y = Dec (x == y)
s== : {m n : Nat} -> (succ m) == (succ n) -> m == n
s== refl = refl
is-eq? : (m n : Nat) -> m ==? n
is-eq? zero zero = yes refl
is-eq? (succ m) zero = no \()
is-eq? zero (succ n) = no \()
is-eq? (succ m) (succ n) with is-eq? m n
... | no f = no \sm=sn -> f (s== sm=sn)
... | yes m=n = yes (cong succ m=n)
-- if m < n and m+1 /= n, then m+1 < n
neq : {m n : Nat} -> m < n -> ((succ m) == n -> False) -> (succ m) < n
neq {_} {zero} ()
neq {zero} {succ zero} z< f = false-elim (f refl)
neq {zero} {succ (succ n)} z< f = s<s z<
neq {succ m} {succ n} (s<s m<n) f = s<s (neq m<n \m=n -> f (cong succ m=n))
要带走的重要物品：
_<_ 的标准定义允许构建更简单的 WellFounded-ness 证明，因为可以一次递减一个参数。 _<_ 的不同定义需要减少两者，这似乎是一个问题。然而，使用辅助函数 neq 可以构造一个递归，其中只有一个和相同的参数变小。
_==_ 对 Nat 的可判定性允许我构建这样的递归。 Agda 可以看到对 <-WellFounded 的递归调用是针对结构较小的 x，因此终止。然后根据相等性测试的结果使用不同的结果。使用 neq 的分支计算必要的 Acc 给定 <-WellFounded 为更小的 x 发现的函数：函数终止，因为 Agda 允许构造这样的函数。另一个分支 x == (succ y) 按原样使用值，因为 rewrite 使 Agda 相信它是正确的类型。
通过构造 <-WellFounded:
_-|-_ : Bin -> Bin -> Bin
x -|- y with max-len x y
... | n , (x<n , y<n) = Sigma.fst (a (<-Well-founded n) b (x , x<n) (y , y<n)) where
a : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ n)
a+O : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ (succ n))
a+I : {n : Nat} -> Acc _<_ n -> Bin -> S-Bin n -> S-Bin n -> S-Bin (succ (succ n))
a+O f c m n with a f c m n
... | r , r<n = r O , s<s r<n
a+I f c m n with a f c m n
... | r , r<n = r I , s<s r<n
a {zero} _ _ (_ , ())
a {succ sz} (acc f) cc mm nn with cc | mm | nn
... | b | m O , s<s m< | n O , s<s n< = a+O (f sz n<n1) b (m , m<) (n , n<)
... | b | m O , s<s m< | n I , s<s n< = a+I (f sz n<n1) b (m , m<) (n , n<)
....-- not including the whole thing here - it is too long.
我不包括两个二进制数加法的整个构造（也不是有效的 - 只是证明有根据的练习）。这里要注意的重要一点是递归是如何开始的，以及它是如何被重用来构造新的 Acc 实例来匹配类型的——这里 S-Bin 表示最多位长度的二进制数 n，而 Agda 确信 Acc _<_ n 变小了，即使它不能证明 S-Bin n 变小。