畸形定义:在顺序模式下不允许非线性模式

Question

我已经定义了以下功能：

fun count:: "'a ⇒ 'a list ⇒ nat" where
"count a Nil = 0" |
"count a (Cons b xs) = (count a xs)" |
"count a (Cons a xs) = (count a xs) + (Suc 0)"

它应该计算具有带有相同类型的Elemts中元素A的出现数量。我收到以下错误：

Malformed definition:
Nonlinear patterns not allowed in sequential mode.
⋀a xs. count a (a # xs) = count a xs + Suc 0 

Answer 1

相对于模式，'线性'表示每个自由变量仅发生一次。在您的第三行中，左侧的图案两次包含a，这使其成为非线性。功能软件包的"顺序"模式不支持这。这是您可以在一个接一个地指定重叠函数方程的模式，而匹配的第一个是计数的模式。这也是" Fun"命令使用的模式，哪种功能编程语言通常会使用（请注意，这些语言通常也不允许非线性模式）。

您基本上有两种可能性：如果您绝对想使用非线性模式，则可以写

function count:: "'a ⇒ 'a list ⇒ nat" where
  "count a Nil = 0"
| "a ≠ b ⟹ count a (Cons b xs) = (count a xs)"
| "count a (Cons a xs) = (count a xs) + (Suc 0)"
  by (metis neq_Nil_conv surj_pair) auto
termination by lexicographic_order

请注意，您必须表明这些模式是详尽而非重叠的，以及终止。"有趣"的功能不力，但会自动做所有这些事情。

更容易，更好的方法就是以更适合系统自动化的方式重新重新定义：

fun count:: "'a ⇒ 'a list ⇒ nat" where
  "count a Nil = 0"
| "count a (Cons b xs) = (count a xs) + (if a = b then 1 else 0)‹›

由于各种原因，这几乎总是可取的（较短，更容易，与代码生成更好）。

有关功能包的更多信息，请咨询文档。这是一个非常强大且通用的工具，但是如果您只能用"乐趣"获得想要的东西，那通常就是您想要的方式。