1

我想制作一个函数标准 ml，它接受一个列表和函数，并从中制作一个 BST。该函数的类型是：'a list -> ('a * 'a -> bool) -> 'a tree，但是我遇到了一些问题，这是我编写的代码：

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;

这段代码产生了我想要的类型，但它正确吗？

4

1 回答 1

2

您的代码的第一个版本存在两个问题：

  • 您在 let 块中声明了一个从未使用过的函数，并且您的函数递归调用自身，直到第一个参数为空列表，因此您的代码可以简化为fun makeBST _ _ = EMPTY，所以这可能是您出现错误的原因接收是因为 SML 不知道EMPTY应该是什么类型。
  • 第 3 行的双引号应该是单引号

不过，既然您已经制作了第二个版本，我猜您已经掌握了这一点。不过，您的新代码仍然不正确。对该函数的任何调用的结果都是一棵以列表的第一个元素为根和两个EMPTY子元素的树。您正在比较左右子树，然后在正确的位置添加新值，但问题是您只返回该子树而不是整个树。你想要的是以下内容：

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-01T05:59:14.227 回答