Insert element into a tree from a list in Standard ML

Question

I have just started to learn SML on my own and get stuck with a question from the tutorial. Let say I have:

tree data type

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

insert function

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)

an integer list

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

my question is how can I add write a function to loop through each element in the list and add to a tree?

Your answer is really appreciated.

Answer 1

Use foldl with insert as the folding function and an empty tree as the starting value.

For every item in the list foldl will call insert with the item and the so-far created tree as arguments. The result of the call to insert will then be used in the next call to insert with the next item in the list and so on.

Also note that the definitions of the tree type and the insert function in your question are broken: First of all you didn't give the type a name (the syntax is datatype name = Foo | Bar, not datatype Foo | Bar). Second of all constructor names have to start with capital letters. So the type definition needs to be datatype tree = Node of (tree*int*tree) | Null and in the insert function you have to replace each occurrence of "node" and "null" with "Node" and "Null".