標準ml使bst不在列表中

我想製作一個函數標準ml，它需要一個列表和函數，並使BST不在列表中。該函數的類型是：'a list -> ('a * 'a -> bool) -> 'a tree，但我有一些問題吧，下面是我寫的代碼：標準ml使bst不在列表中

datatype 'data tree = 
    EMPTY 
| NODE of 'data tree * 'data * "data tree; 

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
    let 
     fun insert EMPTY x = NODE(EMPTY, x, EMPTY) 
      | insert (NODE(left, root, right)) x = 
       if f(x, root) then 
        insert left x 
       else 
        insert right x 
    in 
     makeBST xs f 
    end;

類型我與這個函數得到的是：'a list -> ('b * 'c -> bool) -> 'd tree，當我試圖把它，像下面makeBST [4, 3, 6, 7, 8, 2, 0, 1] (op <);我得到以下錯誤：

stdIn:16.1-16.40 Warning: type vars not generalized because of 
    value restriction are instantiated to dummy types (X1,X2,...) 
val it = EMPTY : ?.X1 tree

什麼是錯的代碼？感謝

編輯：

我的代碼的第二個版本：

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
     let 
      val tree = EMPTY 
      fun insert EMPTY x = NODE (EMPTY, x, EMPTY) 
       | insert (NODE(left, root, right)) x = 
        if f(x, root) then 
         insert left x 
        else 
         insert right x 
     in 
      insert (makeBST xs f) x 
     end;

此代碼生成我想要的類型，但它是正確的？

來源

2012-03-31 hakuna matata

當然，這是從韋伯的現代編程語言第11章課本作業問題，鍛鍊11 – 2017-10-13 12:51:18

兩個問題，你的代碼的第一個版本：

你宣佈你的讓利塊的函數，而從未使用過，而你的函數遞歸調用自身，直到第一個參數是一個空列表，所以你的代碼可以簡化爲fun makeBST _ _ = EMPTY，所以這可能是你收到錯誤的原因，因爲SML不知道EMPTY應該是什麼類型。
3線雙引號應該是一個單引號

不過，因爲你做了第二個版本，我猜你抓住了這個了。儘管如此，你的新代碼仍然不正確。對此函數的任何調用的結果都是以列表的第一個元素作爲根的樹和兩個子樹。您正在比較左側和右側子樹，然後在正確的位置添加新值，但問題是您只返回該子樹而不是整個樹。你想要的是以下幾點：

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
     let 
      val tree = EMPTY 
      fun insert EMPTY x = NODE (EMPTY, x, EMPTY) 
       | insert (NODE(left, root, right)) x = 
        if f(x, root) then 
         Node(insert left x, root, right) 
        else 
         Node(left, root, insert right x) 
     in 
      insert (makeBST xs f) x 
     end;

來源

2012-04-01 05:59:14 howardh

您是否需要行'VAL樹= EMPTY'？ – 2013-10-28 01:53:32

標準ml使bst不在列表中

回答

相關問題