标准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不在列表中

回答

相关问题