使用 zip、map 和 products 终止递归函数的问题

Question

我在尝试定义在 zip 上使用 map 的递归函数时遇到问题。

这是我的代码的简化版本，第一个有效

datatype bar = Bar "bar list"

function (sequential) bar_lub :: "[bar,bar] ⇒ bar" ("_⊔b_" [30,60] 60)
  where
    "(Bar ts) ⊔b (Bar us) = Bar (map (λ(t1,t2). t1 ⊔b t2) (zip ts us))"
  by pat_completeness auto

这很好，结果是

的终止目标

1. ⋀ts us a b. (a, b) ∈ set (zip ts us) ⟹ P (a, b) ~ P (Bar ts, Bar us)

给定适当的 P 和 ~。

很容易证明

当我将列表更改为成对列表时，我的问题就来了，如下所示

datatype 'a foo = Foo "('a foo × 'a) list"

function (sequential) foo_lub1 :: "['a foo, 'a foo] ⇒ 'a foo" ("_⊔_" [30,60] 60)
  where
    "(Foo ts) ⊔ (Foo us) = Foo (map (λ((t1,_), (t2,_)). (t1 ⊔ t2, undefined)) (zip ts us))"
  by pat_completeness auto

现在，我们得到了终止目标

1. ⋀ts us t1 b1 t2 b2 xc. ((t1, b1), t2, b2) ∈ set (zip ts us) ⟹ P (t1, xc) ~ P (Foo ts, Foo us)

变量xc出现了，和任何东西都没有关系。理想情况下，我希望有假设 xc = t2，并且证明很简单。

有谁知道为什么会这样，有什么补救方法吗？

Answer 1

function 包使用同余规则来确定递归调用的上下文。不幸的是，同余规则不能捕获所有类型的上下文，元组上的深度模式匹配就是失败的例子。幸运的是，有一个简单的解决方法：使用投影 fst 和 snd 而不是元组抽象：

function (sequential) foo_lub1 :: "['a foo, 'a foo] ⇒ 'a foo" ("_⊔_" [30,60] 60)
  where
    "(Foo ts) ⊔ (Foo us) = Foo (map (λx. (fst (fst x) ⊔ fst (snd x), undefined)) (zip ts us))"

使用 zip、map 和 products 终止递归函数的问题

Problems with termination of a recursive function using zip, map, and products

termination

isabelle

使用 zip、ma​​p 和 products 终止递归函数的问题

Problems with termination of a recursive function using zip, map, and products

termination

isabelle

使用 zip、map 和 products 终止递归函数的问题