Вставить элемент в дерево из списка в Standard ML - PullRequest
Новая
       38

Вставить элемент в дерево из списка в Standard ML

1 голос
/ 12 марта 2010

Я только начал изучать SML самостоятельно и застрял с вопросом из учебника. Допустим, у меня есть:

тип данных дерева 

datatype node of (tree*int*tree) | null

функция вставки 

fun insert (newItem, null) = node (null, newItem, null)
|   insert (newItem, node (left, oldItem, right)) =                               
    if (newItem <= oldItem) then node (insert(newItem,left),oldItem, right)
                            else
                                 node (left, oldItem, insert(newItem, right)

список целых чисел 

val intList  = [19,23,21,100,2];

У меня вопрос: как добавить функцию записи для циклического просмотра каждого элемента в списке и добавления в дерево?

Ваш ответ действительно приветствуется.

1 Ответ

1 голос
/ 13 марта 2010

Используйте foldl со вставкой в ​​качестве функции складывания и пустое дерево в качестве начального значения.

Для каждого элемента в списке foldl будет вызывать insert с элементом и созданным до сих пор деревом в качестве аргументов. Затем результат вызова для вставки будет использован при следующем вызове для вставки со следующим элементом в списке и т. Д.

Также обратите внимание, что определения типа дерева и функции вставки в вашем вопросе неверны: во-первых, вы не дали типу имя (синтаксис datatype name = Foo | Bar, а не datatype Foo | Bar). Во-вторых, имена конструкторов должны начинаться с заглавных букв. Таким образом, определение типа должно быть datatype tree = Node of (tree*int*tree) | Null, и в функции вставки вы должны заменять каждое вхождение "node" и "null" на "Node" и "Null".

...