Download 1 Introduction

proc {Merge Xs Ys ?Zs}
case Xs#Ys
of nil#Ys then Zs = Ys
[] Xs#nil then Zs = Xs
[] (X|Xr)#Ys then Zs = X|{Merge Ys Xr $}
[] Xs#(Y|Yr) then Zs = Y|{Merge Yr Xs $}
end
end
Figure 6: Binary Merge of Two Lists in Nested Form
R,
and therefore {P X ...} could considered as a function call that can be inserted
in any expression instead of the result argument R. So
{Q {P X ... } ... }
is equivalent to:
local R in
{P X ... R}
{Q R ... }
end
Now back to our example, a more concise form using functional nesting is:
{Browse {Insert alex 17
{Insert rebecca 20
{Insert eeva 45 {Insert seif 43 nil}}}}}
There is one more rule to remember. It has to do with a nested application inside
a record or a tuple as in:
Zs = X|{Merge Xr Ys $}
Here, the nested application goes after the record construction statement; Do you
know why ?. So we have
local Zr in
Zs = X|Zr
{Merge Xr Ys Zr}
end
We can now rewrite our Merge procedure as shown in Figure 6, where we use nested
application.
5.5 Procedures as Values
Since we have been inserting elements in binary trees, let us dene a program that
checks if is data structure is actually a binary tree. The procedure BinaryTree
shown in FigureB~ inaryTree checks a structure to verify whether it is a binary tree
or not, and accordingly returns true or false in its result argument B. Notice that
we also dened the auxiliary local procedure And.
Consider the call
{And {BinaryTree T1} {BinaryTree T2} B}
17