标准ml使bst不在列表中 [英] standard ml make bst out of a list

问题描述

我想制作一个带有列表和功能并从中制作BST的功能标准ml.该函数的类型为:'a list -> ('a * 'a -> bool) -> 'a tree，但是我遇到了一些问题，这是我编写的代码:

I want to make a function standard ml that takes a list and function and makes a BST out of it. The function's type is: 'a list -> ('a * 'a -> bool) -> 'a tree, but I'm having some problems with it, here are the code I wrote:

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 <);所示，出现以下错误:

The type i'm getting with this function is: 'a list -> ('b * 'c -> bool) -> 'd tree and when I try to call it, like the following makeBST [4, 3, 6, 7, 8, 2, 0, 1] (op <); I get the following error:

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

代码有什么问题? 谢谢

What is wrong with the code? Thanks

我的代码的第二个版本:

Second version of my code:

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;

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

This code produced the type i want but is it correct?

推荐答案

第一版代码存在两个问题:

Two problems with the first version of your code:

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

• You're declaring a function in your let block which is never used, and your function recursively calls itself until the first argument is an empty list, so your code can be simplified to fun makeBST _ _ = EMPTY, so this is probably the reason for the error you're receiving because SML doesn't know what type EMPTY is supposed to be.
• Double quotes on line 3 which should be a single quote

但是，由于您已经制作了第二个版本，所以我想您已经抓住了这个版本.您的新代码仍然不正确.对该函数的任何调用结果都是一棵以列表的第一个元素为根并且有两个EMPTY子级的树.您正在比较左右子树，然后在正确的位置添加新值，但是问题是您只返回该子树而不是整个树.您想要的是以下内容:

Though, since you've made a second version, I'm guessing you caught this already. Your new code still isn't correct yet though. The result of any call to this function is a tree with the first element of the list as a root and two EMPTY children. You're comparing the left and right subtree and then adding the new value at the right place, but the issue is that you only return that subtree and not the entire tree. What you want is the following:

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;

这篇关于标准ml使bst不在列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！