0

我正在尝试运行一个函数 subst(tr, v1, v2) 返回一个新的 ntree，其中 v1 的所有值都被输出树中的 v2 替换。

datatype 'a ntree = leaf of 'a | node of 'a ntree list;

fun map(f, []) = [] | map(f,x::t)=f(x) :: map(f,t);

fun subst(leaf(d), v1, v2) = if d=v1 then v2 else d
  | subst(node(q), v1, v2) = let fun w(k) =
  if k=v1 then subst(v2, v1, v2) else subst(k, v1, v2)
  in map(w, q)
  end;

但我得到一个循环错误 b/c 我的 rhs of 子句不同意函数结果类型。我的表达式是 ''Z 列表，我的结果类型是 ''Z

4

1 回答 1

1

您忘记再次subst使用适当的ntree构造函数包装结果，因此，类型系统试图将类型等同于d列表。此外，w鉴于您将其映射到 ntree 列表（即，k是一个 ntree，并且您无法将其与 比较v1），您的函数并没有多大意义。

一般提示：如果您有奇怪的类型错误，一开始无法理解，通常可以通过添加类型注释来缩小它们的范围，例如在函数参数或结果上。

以下代码应该可以工作（未经测试）：

fun subst(leaf d, v1, v2) = leaf(if d = v1 then v2 else d)
  | subst(node q, v1, v2) = node(map(fn k => subst(k, v1, v2), q))

使用适量的柯里化，并使用标准map函数，它可以更简单：

fun subst v1 v2 (leaf d) = leaf(if d = v1 then v2 else d)
  | subst v1 v2 (node q) = node(map (subst v1 v2) q)

此外，作为风格上的 nit，最好将构造函数 (Leaf和Node) 大写，以便将它们与模式中的变量区分开来。

于 2013-04-16T06:45:42.533 回答