与递归数据类型的统一

Question

继suggestion使用嵌套结构的递归数据类型就像树一样，我尝试使所述rechaurive datatyep在测试程序中工作，但遇到（又一个，对我来说很神秘）错误。

我的计划是这样的：

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

---

一种方法是坚持你的数据类型定义，并使用钻营保持功能，以及改变一切，以满足这些决定：

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

或混合搭配以上。 （对于记录对元组问题的修复与对于currying-tuple问题的修复无关。）

---

顺便说一句，我认为这是一个错误，包括在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