I have a local
block with few helper methods. After that, comes a main function (between the in
and end
block):
datatype color = BLACK | RED;
datatype 'a RBTree = Nil
| Br of (int * 'a * color) * 'a RBTree * 'a RBTree;
datatype Balance = RR | LR | LL | RL;
exception NotFound;
local
fun max (num1, num2) ...
fun get_hight ...
fun get_balance_factor ...
fun LL_rotate ...
fun LR_rotate ...
fun RR_rotate ...
fun RL_rotate ...
fun balance_tree (Nil) = (Nil)
| balance_tree (Br(node, Nil, Nil)) = (Br(node, Nil, Nil))
| balance_tree (Br(node, left, right)) =
if (get_balance_factor (Br(node, left, right))) = 2 then
if (get_balance_factor left) = ~1 then (* LR *)
LR_rotate (Br(node, left, right))
else if (get_balance_factor left) > ~1 then (* LL *)
LL_rotate (Br(node, left, right))
else if (get_balance_factor Br(node, left, right)) = ~2 then
if (get_balance_factor right) = 1 then (* RL *)
RL_rotate (Br(node, left, right))
else if (get_balance_factor right) < 1 then (* RR *)
RR_rotate (Br(node, left, right))
else (Br(node, left, right))
in
fun insert ((Nil), item) = Br(item, (Nil), (Nil) )
| insert ( (Br(node, left, right)), item) =
if (#1(node) = #1(node)) then
(Br(item, left, right))
else if (#1(node) < #1(node)) then
balance_tree (Br(node, insert(left, item), right))
else
balance_tree (Br(node, left, insert(right, item)))
end;
where the ...
stands for the implementation.
And insert
is the 'main' function.
SML gives me this output:
- use "ex4.sml";
[opening ex4.sml]
datatype color = BLACK | RED
datatype 'a RBTree = Br of (int * 'a * color) * 'a RBTree * 'a RBTree | Nil
datatype Balance = LL | LR | RL | RR
exception NotFound
ex4.sml:58.1-58.3 Error: syntax error: replacing IN with LET
ex4.sml:69.1 Error: syntax error found at END
uncaught exception Compile [Compile: "syntax error"]
raised at: ../compiler/Parse/main/smlfile.sml:15.24-15.46
../compiler/TopLevel/interact/evalloop.sml:44.55
../compiler/TopLevel/interact/evalloop.sml:296.17-296.20
I don't understand why I should be replacing in
with let
?
SML/NJ's parser errors are a little strange. What it means when it says "repacing IN with LET" is that it saw the token "IN" (i.e., the keyword "in") at the beginning of line 58, but it got stuck parsing there because it had no way to resolve what the IN goes with. In situations like this it performs error recovery by pretending that you wrote something different, I think based on some hard-coded rules. The rules aren't designed to fix your program, just to allow parsing to continue so that you can see multiple parse errors in one compilation attempt. In this case, it's just saying that it pretended to see "LET" (i.e., the keyword "let") instead of "IN", and then continued trying to parse. In my experience, the right way to proceed is just to look at the location of the first parse error, fix it, and recompile. The later errors can be very confusing, and its message about how it tried to recover is usually useless.