与递归数据类型的统一

Question

按照对嵌套结构（如树）使用递归数据类型，我试图使所述递归数据类型在测试程序中工作，但遇到（又一个，对我来说非常神秘）错误。

我的程序是这样的：

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


fun recursivetreebuilder a n =
  if n = 0
  then
      Leaf a
  else
      Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

因此，该函数应该构建一棵深度为 n 的二叉树，方法是递归调用自身并递减 ns 直到 n 为 0。

但是我收到这个错误：

Can't unify {left: 'a tree, right: 'a tree, value: 'a} with {value: 'b} *
(Int32.int/int -> 'c) * (Int32.int/int -> 'c) (Field 1 missing) Found near if
<( n, 0) then Leaf(a) else Node( a, recursivetreebuilder( ...), ......)

使用递归数据类型旨在解决使用嵌套列表时的另一个统一问题。也许我应该能够看到问题在哪里给出了我的另一个问题的解释，但我还没有。

编译器指的是什么“字段 1”？当递归数据类型旨在使其能够统一同一数据类型的不同“子类型”时，为什么它不能统一？

编辑

尝试了几个建议的结构，但仍然出现错误。例如

datatype 'a tree =
     Leaf of 'a
     |  Node of 'a tree * 'a tree


fun recursivetreebuilder a n =
  if n < 0
  then
      Leaf (a)
  else
      Node (recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

我明白了

val printList = fn : Int.int list -> unit
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Exception- Fail "Static errors (pass2)" raised

Answer 1

这里有两个问题。

第一个问题是——例如——{ value : 'a, left: 'a tree, right: 'a tree } 是一个记录类型，而 (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 是一个元组而不是记录。所以他们不匹配；这就像将 real 传递给期望 int.

的函数

（撇开迂腐：技术上元组实际上是记录，但非常具体；(a, b, c) 是 { 1 = a, 2 = b, 3 = c } 的语法糖。对于大多数实用目的，您可以将元组和记录视为组合类型的两种 similar-but-completely-separate 方式。但现在您知道为什么 error-message 指的是 "Field 1"。）

第二个问题是您声明函数使用柯里化 (fun recursivetreebuilder a n = ...)，但随后您尝试使用元组调用它 (recursivetreebuilder(a, n-1))。

一种方法是坚持您的数据类型定义，并保持函数使用柯里化，并更改所有内容以匹配这些决定：

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

fun recursivetreebuilder a n =
  if n = 0
  then
      Leaf { value = a}
  else
      Node { value = a,
             left = recursivetreebuilder a (n-1),
             right = recursivetreebuilder a (n-1) }

或更改您的数据类型定义以消除记录类型，并更改函数以消除柯里化：

datatype 'a tree =
  Leaf of 'a
| Node of 'a * 'a tree * 'a tree

fun recursivetreebuilder (a, n) =
  if n = 0
  then
      Leaf a
  else
      Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

或mix-and-match以上。（record-vs.-元组问题的修复独立于 currying-vs.-元组问题的修复。）

顺便说一下，我认为在 Leaf 和 Node 情况下都包含一个值是错误的。根据您当前的定义，不可能有一棵恰好包含 0 个或恰好 2 个元素的树。

相反，我认为您应该留空叶子：

datatype 'a tree =
  Leaf
| Node of 'a * 'a tree * 'a tree

或具有 child-nodes 但没有自己的值的节点：

datatype 'a tree =
  Leaf of 'a
| Node of 'a tree * 'a tree

或者去掉叶子和节点的区别，使children可选：

datatype 'a tree =
   Node of 'a * 'a tree option * 'a tree option

与递归数据类型的统一

unification with recursive datatypes

recursion

types

sml

unification

编辑