data constructor used without argument in pattern?

Question

I'm not that familiar with SML but I have wrote the following program:

datatype 'a bin_tree = Leaf of 'a
|   Node of 'a bin_tree * 'a bin_tree

fun height Leaf (x) = 0
|   height Node (l1,l2) = 1 + Int.max(l1,l2)

fun is_balanced Leaf (x) = true
|   is_balanced Node (l1,l2) = 
    if(abs(height(l1) - height(l2))<2)
        then (is_balanced(l1); is_balanced(l2))
    else false

val prod_tree = fold_tree
    op* (fn x => x)

fun fold_tree e f Leaf (x) =  f(x)
|   fold_tree e f Node (l1, l2) = (e(fold_tree e f(l1)), e(fold_tree e f(l2)))

However, when the is compiled use "lab2.sml"; I get the following error:

lab2.sml:4.12-4.16 Error: data constructor Leaf used without argument in pattern
lab2.sml:5.10-5.14 Error: data constructor Node used without argument in pattern
lab2.sml:7.17-7.21 Error: data constructor Leaf used without argument in pattern
lab2.sml:8.15-8.19 Error: data constructor Node used without argument in pattern
lab2.sml:9.10-9.33 Error: operator and operand don't agree [overload conflict]

I've done my research but maybe I'm just missing something. Any help would be greatly appreciated. Thanks!

Answer 1

There are a number of issues. Since this seems to be homework, I'll point out a few things but let you work out the details:

1) In SML, function application has the highest possible precedence. Thus the line

fun height Leaf (x) = 0

parses as

fun (height Leaf) x = 0

rather than the intended

fun height (Leaf x) = 0

Note that (height Leaf) has the function height applied to the constructor Leaf where Leaf has no argument -- hence the cryptic error message data constructor Leaf used without argument in pattern. You repeat essentially the same error in other places in your code. The solution in all cases is to put parenthesis around the constructor expression; e.g. use (Leaf x) rather than Leaf (x).

2) Int.max(l1,l2) makes no sense since l1 and l2 are trees rather than integers. Probably you meant to take the height of these trees.

3) ; isn't a Boolean operator. andalso is.

4) You are trying to use fold_tree before you have defined it. Define it first.

Given these hints you should be able to debug your code. I was able to get your functions working after just a few minutes, so you are almost there.