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

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使等式成立.这些是bool为了a和int为b:

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来表示树,例如:

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

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

希望现在有点清楚了.