在 Isabelle 中为乘法定义原始递归

Question

我是 Isabelle 的新手，我正在尝试定义原始递归函数。我已经尝试了加法，但我在乘法方面遇到了问题。

datatype nati = Zero | Suc nati

primrec add :: "nati ⇒ nati ⇒ nati" where
"add Zero n = n" |
"add (Suc m) n = Suc(add m n)"

primrec mult :: "nati ⇒ nati ⇒ nati" where
"mult Suc(Zero) n = n" |
"mult (Suc m) n = add((mult m n) m)"

上面的代码出现以下错误

Type unification failed: Clash of types "_ ⇒ _" and "nati"

Type error in application: operator not of function type

Operator: mult m n :: nati

Operand: m :: nati

有什么想法吗？

Answer 1

问题出在您的 mult 函数上：它应该如下所示：

primrec mult :: "nati ⇒ nati ⇒ nati" where
  "mult Zero n = Zero" |
  "mult (Suc m) n = add (mult m n) m"

函数 programming/Lambda 演算中的函数应用是绑定最强的运算，它关联到左侧：类似 f x y 的意思是“f 应用于 x，结果应用于 y' – 或者，等效地由于 Currying：函数 f 应用于参数 x 和 y.

因此，像 mult Suc(Zero) n 这样的东西会读作 mult Suc Zero n，即函数 mult 必须是一个接受三个参数的函数，即 Suc，Zero 和 n。这给你一个类型错误。同样，add ((mult m n) m) 不起作用，因为它与 add (mult m n m) 相同，这意味着 add 是一个接受一个参数的函数，而 mult 是一个接受三个参数的函数。

最后，如果您修复了所有这些问题，您将收到另一个错误消息，提示您在 mult 函数的 left-hand 侧有一个 non-primitive 模式。你不能 pattern-match 像 Suc Zero 这样的东西，因为它不是原始模式。如果你使用 fun 而不是 primrec，你可以这样做，但这不是你想在这里做的：你想改为处理 Zero 和 Suc 的情况（请参阅我的解决方案）。在您的定义中，mult Zero n 甚至是未定义的。

在 Isabelle 中为乘法定义原始递归

Defining Primtive Recursion for multiplication in Isabelle

isabelle