стандартный мл сделать из списка - PullRequest
Новая
       45

стандартный мл сделать из списка

0 голосов
/ 31 марта 2012

Я хочу сделать стандартную функцию 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

Что не так с кодом? Спасибо

EDIT:

Вторая версия моего кода: 

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;

Этот код выдает нужный мне тип, но это правильно?

1 Ответ

2 голосов
/ 01 апреля 2012

Две проблемы с первой версией вашего кода:

  • Вы объявляете функцию в своем блоке 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;
...