Insert element into a tree from a list in Standard ML
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开发者_StackOverflow loop through each element in the list and add to a tree?
Your answer is really appreciated.
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".
精彩评论