If & Else & Pattern Matching in SML altogether?

Question

I've been trying to compile this piece of code for 3 hours and nothing improved. I know that my datatype compiles without problem and also the first case of pattern matching . But when the second case comes in (a node with two nodes for children ) it won't compile. The problems seem to be in the line with if and the 4 conditions.

datatype Heap = Leaf of int 
                  |Node of int * Heap  * Heap 
(*.........................................*)

fun isHeap Leaf(a) = true
  | isHeap Node(a,Leaf(b),Leaf(c)) =  if (a<=b andalso a<=c) then true
                                      else false
  | isHeap (Node(a, Node(b,_,_), Node(c,_,_)) )= 
        if(a<= c andalso a<=b andalso isHeap (Node(b,_,_))  andalso isHeap (Node(c,_,_))  )
           then true
        else false

I tried , to do another it way by breaking the four conditions into

        let
            val left =  isHeap (Node(b,_,_))  
            val right =  isHeap (Node(c,_,_)) 
        in
            if(left = true andalso right = true) then true
            else false
        end
    else false 

That work either ( I think because let in has return type unit while else boole)

Answer 1

I suspect the secret error message is complaining about the third case because you forgot parentheses around the parameter in the first two cases –

isHeap Leaf(a)

is equivalent to

isHeap Leaf a

which has two parameters, and the second case also has two parameters,Node and (a,Leaf b,Leaf c).

Also, you're trying to use _ as an expression, which you can't.

Rather than trying to fix this (your function will become very tedious and unreadable once you add the two missing cases), I suggest introducing a helper function:

fun value (Leaf v) = v
  | value (Node (v, _, _)) = v

and then you can simplify the code to

fun isHeap (Leaf _) = true
  | isHeap (Node (v, left, right)) = v <= value left 
                             andalso v <= value right
                             andalso isHeap left
                             andalso isHeap right