與遞歸數據類型的統一

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