recursion - 与递归数据类型的统一

Question

遵循 suggestion要对像树这样的嵌套结构使用递归数据类型，我试图使上述递归数据类型在测试程序中工作，但遇到了(对我来说又一个非常神秘的)错误。

我的程序是这样的:

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 的二叉树，通过递减的 n 递归调用自身，直到 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 }。对于大多数实际目的，您可以将元组和记录视为组合类型的两种相似但完全独立的方式。但现在您知道为什么会出现错误消息引用“字段 1”。)

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

---

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

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) }

或者更改数据类型定义以消除记录类型，并更改函数以消除柯里化(Currying):

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))

或混合搭配以上内容。 (记录与元组问题的修复独立于柯里化(Currying)与元组问题的修复。)

---

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

相反，我认为你应该有空叶子:

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

或者有子节点但没有自己的值的节点:

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

或者消除叶子和节点之间的区别，并使子节点可选:

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