types - 要统一的类型变量出现在类型中

Question

我有一个函数可以从 2 个列表中重建一棵树。我返回了所有分支的列表，但出现了一个我不明白的错误。但我认为它与返回类型有关。

错误是这样的:

Can't unify ''a with ''a list (Type variable to be unified occurs in type) Found near recon
( ::( preoH, preoT), ::( inoH, ...))
Exception- Fail "Static errors (pass2)" raised

错误发生的行是函数定义的标题 fun recon (preoH::preoT, inoH::inoT) =

该错误的确切含义是什么，为什么会发生？

(* Reconstruts a binary tree from an inorder and a preorder list. *)
fun recon (preoH::preoT, inoH::inoT) =
  (* Case 0: Leaf reached*)
  if
      preoT = [] andalso inoT = [] andalso preoH = inoH
  then
      [preoH]
  else
      let
      (* split the list of nodes into nodes to the left and nodes to the
      right of preoH; ST stands for subtree *)
      val (inoLST, inoRST) = splitat (inoH::inoT, preoH)
      val (preoLST, preoRST) = splitafter (preoT, last(inoLST))
      in
      (* Case 1: Unary branch encountered, make preoH the parent node of the
      subtree and combine the left and right preorder and inorder lists*)
      if
              length(inoLST) <> length(preoLST)
      then
          [preoH, recon (preoLST@preoRST, inoLST@inoRST)]
      (* Case 2: Binary branch encountered, proceed as normal *)
      else
              [recon (preoLST, inoLST), preoH, recon (preoRST, inoRST)]
      end;

Answer 1

将变量与某物统一意味着为该变量找到一个等于该某物的值。例如，我们可以统一一些简单的东西(我将使用三重相等来表示这两项必须相等):

a === int

统一的结果是我们可以用 a 代替的值。在这种情况下，我们可以用 int 代替 a 并且等式将成立(它类似于数学中求解方程组):

a: int
-----------
int === int

或者我们可以统一一个稍微复杂一点的方程:

a -> int === bool -> b

在这里，我们需要找到需要代入a 和b 的值，以使等式成立。 a 的 bool 和 b 的 int:

a: bool
b: int
---------------------------
bool -> int === bool -> int

我希望你现在已经明白了。在你的情况下，编译器必须统一这个:

a === a list

好吧，它是 ''a 而不是错误消息中的 a，但我们暂时可以忽略它。问题是因为 a 出现在两边，方程是不可统一的，因此错误消息中的提示(强调我的)“类型变量要统一出现在类型中”。如果我们说 a 必须是 a list 并在两边用它替换 a 我们会得到这个:

a list === a list list

我们还没有删除我们需要解决的 a 变量，我们也不会很快。这就是编译器 barfs 的原因，它会导致无限循环，而简单检查变量是否出现在等式两边是避免该循环的好方法。

为什么会发生在您的案例中？简短的版本是您试图使用嵌套列表表示一棵树，而 SML 的类型系统无法处理。您尝试根据列表构建的树看起来类似于此:

[[a], a, [a]]

a 是一些通用类型变量。列表是同类容器，它们只能包含单一类型的值，这意味着 [a] 和 a 必须是同一类型，即:

a === a list

我已经解释了为什么这会导致错误。

解决方案是使用递归数据类型来表示树，例如:

datatype 'a tree =
  Leaf
| Node of { value : 'a, left: 'a tree, right: 'a tree }

这是有效的，因为它允许我们递归地定义它，即叶子的类型是 tree 本身。您的 recon 函数应该将 ''a tree 作为其返回类型。

希望现在更清楚一些。