列表归纳 - 证明更强 属性 (Haskell)
Induction on lists - Proving Stronger Property (Haskell)
我会马上说这是一个任务，我不是在寻找答案 - 只是一些方向，因为我已经为此工作了很长一段时间。给定以下尾递归求和函数：
sumTR [ ] acc = acc
sumTR (x:xs) acc = sumTR xs (x + acc)
我们必须通过归纳法证明：
sumTR xs (sumTR ys acc) = sumTR (ys ++ xs) acc
在证明基本情况（对 xs 进行归纳并将 ys 视为常数）后，我得出：
sumTR x:xs(sumTR ys acc) = ... = sumTR xs (x + sumTR ys acc)
sumTR (ys ++ x:xs) acc = ... = sumTR xs (sumTR ys (x + acc))
我们的讲师举了一个更简单的例子（sum1 xs = sum2 xs，sum1 是简单的递归），当他达到不能让它们更相似的地步时，他证明了 'stronger property'，注意像 sum2 xs acc = acc + sum of xs 这样的东西。然后他设置了一个涉及 'for all acc' 的归纳假设，然后将 acc 设置为 0。
我遇到的主要问题是 acc 已经在左轴和右轴上了，所以我觉得我已经接近了，但我并没有真正证明更强大 属性（这个问题没有‘具体要求它，但我认为我们应该使用它）。此外，我不确定在将元素取出（或插入）函数时，我可以在多大程度上使用加法的关联性。
感谢任何帮助！
在 ys 上进行归纳要容易得多，因为对于空 ys，我们有
sumTR xs (sumTR [] acc) = -- by first case of (inner) sumTR
sumTR xs acc = -- by definition of (++)
sumTR ([] ++ xs) acc -- Q.E.D.
对于y:ys，我们有
sumTR xs (sumTR (y:ys) acc) = -- by second case of (inner) sumTR
sumTR xs (sumTR ys (y + acc)) = -- by induction
sumTR (ys ++ xs) (y + acc) = -- by second case of sumTR, "in reverse"
sumTR (y:(ys ++ xs)) acc = -- by definition of (++)
sumTR ((y:ys) ++ xs) acc -- Q.E.D.
使用 ys 对我们有帮助，因为 (++) 是通过其左侧参数的递归定义的，在本例中为 ys。
我会马上说这是一个任务，我不是在寻找答案 - 只是一些方向，因为我已经为此工作了很长一段时间。给定以下尾递归求和函数：
sumTR [ ] acc = acc
sumTR (x:xs) acc = sumTR xs (x + acc)
我们必须通过归纳法证明：
sumTR xs (sumTR ys acc) = sumTR (ys ++ xs) acc
在证明基本情况（对 xs 进行归纳并将 ys 视为常数）后，我得出：
sumTR x:xs(sumTR ys acc) = ... = sumTR xs (x + sumTR ys acc)
sumTR (ys ++ x:xs) acc = ... = sumTR xs (sumTR ys (x + acc))
我们的讲师举了一个更简单的例子（sum1 xs = sum2 xs，sum1 是简单的递归），当他达到不能让它们更相似的地步时，他证明了 'stronger property'，注意像 sum2 xs acc = acc + sum of xs 这样的东西。然后他设置了一个涉及 'for all acc' 的归纳假设，然后将 acc 设置为 0。
我遇到的主要问题是 acc 已经在左轴和右轴上了，所以我觉得我已经接近了，但我并没有真正证明更强大 属性（这个问题没有‘具体要求它，但我认为我们应该使用它）。此外，我不确定在将元素取出（或插入）函数时，我可以在多大程度上使用加法的关联性。
感谢任何帮助！
在 ys 上进行归纳要容易得多，因为对于空 ys，我们有
sumTR xs (sumTR [] acc) = -- by first case of (inner) sumTR
sumTR xs acc = -- by definition of (++)
sumTR ([] ++ xs) acc -- Q.E.D.
对于y:ys，我们有
sumTR xs (sumTR (y:ys) acc) = -- by second case of (inner) sumTR
sumTR xs (sumTR ys (y + acc)) = -- by induction
sumTR (ys ++ xs) (y + acc) = -- by second case of sumTR, "in reverse"
sumTR (y:(ys ++ xs)) acc = -- by definition of (++)
sumTR ((y:ys) ++ xs) acc -- Q.E.D.
使用 ys 对我们有帮助，因为 (++) 是通过其左侧参数的递归定义的，在本例中为 ys。