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

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

Этот код произвел тип, который я хочу, но правильно ли это?


tree currying binary-search-tree sml ml
person hakuna matata    schedule 31.03.2012    source источник
comment
Это, конечно же, домашнее задание из учебника из книги Веббера «Современные языки программирования», глава 11, упражнение 11.   -  person John Tang Boyland    schedule 13.10.2017

Ответы (1)


arrow_upward
2
arrow_downward

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

  • Вы объявляете функцию в своем блоке let, которая никогда не используется, и ваша функция рекурсивно вызывает себя до тех пор, пока первый аргумент не станет пустым списком, поэтому ваш код можно упростить до fun makeBST _ _ = EMPTY, так что это, вероятно, причина вашей ошибки. re получает, потому что 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;
person howardh    schedule 01.04.2012
comment
Вам нужна строка val tree = EMPTY? - person recursion.ninja; 28.10.2013