要统一的类型变量出现在类型中
Type variable to be unified occurs in type
我有一个函数可以从 2 个列表中重建一棵树。我 return 所有分支的列表,但我收到一个我不明白的错误。但我认为它与 return 类型有关。
错误是这样的:
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;
将变量与某物统一意味着为该变量找到一个等于该某物的值。例如,我们可以统一一些简单的东西(我将使用三重等于来表示两项必须相等):
a === int
统一的结果是一个我们可以用 a
代替的值。在这种情况下,我们可以将 int
替换为 a
,方程将成立(类似于数学中求解方程组):
a: int
-----------
int === int
或者我们可以统一一个稍微复杂一点的方程式:
a -> int === bool -> b
在这里,我们需要找到需要代入a
和b
的值,以使等式成立。这些是 bool
for a
和 int
for b
:
a: bool
b: int
---------------------------
bool -> int === bool -> int
我希望你现在已经明白了。在你的情况下,编译器必须统一这个:
a === a list
嗯,您的错误消息中是 ''a
而不是 a
,但我们暂时可以忽略它。问题是因为 a
出现在两边,所以方程是不可统一的,因此错误消息中的提示(强调我的)"Type variable to be unified occurs in type"。如果我们说 a
必须是 a list
并将两边的 a
替换为 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
函数的 return 类型应为 ''a tree
。
希望现在更清楚了。
Ionut 对类型统一的工作原理给出了全面的解释,所以这里提示一下:
[preoH, recon (preoLST@preoRST, inoLST@inoRST)]
第一个元素的类型为 'a,第二个元素的类型为 'a list.
[recon (preoLST, inoLST), preoH, recon (preoRST, inoRST)]
第二个元素的类型为 'a,第一个和第三个元素的类型为 'a list.
当你检查列表是否为空时,考虑使用null preoT
,或者使用模式匹配来处理这种情况。
我有一个函数可以从 2 个列表中重建一棵树。我 return 所有分支的列表,但我收到一个我不明白的错误。但我认为它与 return 类型有关。
错误是这样的:
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;
将变量与某物统一意味着为该变量找到一个等于该某物的值。例如,我们可以统一一些简单的东西(我将使用三重等于来表示两项必须相等):
a === int
统一的结果是一个我们可以用 a
代替的值。在这种情况下,我们可以将 int
替换为 a
,方程将成立(类似于数学中求解方程组):
a: int
-----------
int === int
或者我们可以统一一个稍微复杂一点的方程式:
a -> int === bool -> b
在这里,我们需要找到需要代入a
和b
的值,以使等式成立。这些是 bool
for a
和 int
for b
:
a: bool
b: int
---------------------------
bool -> int === bool -> int
我希望你现在已经明白了。在你的情况下,编译器必须统一这个:
a === a list
嗯,您的错误消息中是 ''a
而不是 a
,但我们暂时可以忽略它。问题是因为 a
出现在两边,所以方程是不可统一的,因此错误消息中的提示(强调我的)"Type variable to be unified occurs in type"。如果我们说 a
必须是 a list
并将两边的 a
替换为 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
函数的 return 类型应为 ''a tree
。
希望现在更清楚了。
Ionut 对类型统一的工作原理给出了全面的解释,所以这里提示一下:
[preoH, recon (preoLST@preoRST, inoLST@inoRST)]
第一个元素的类型为 'a,第二个元素的类型为 'a list.
[recon (preoLST, inoLST), preoH, recon (preoRST, inoRST)]
第二个元素的类型为 'a,第一个和第三个元素的类型为 'a list.
当你检查列表是否为空时,考虑使用
null preoT
,或者使用模式匹配来处理这种情况。