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)

The underscore, `_`, can only occur as a "wildcard" in patterns. — molbdnilo, Jun 16 '21 at 14:59
You are also misplacing parentheses, missing the cases of a `Node` that contains one `Node` and one `Leaf`, and writing too complicated boolean expressions. (`if c then true else false`→ `c`, and `if a = true andalso b = true then true else false` → `a andalso b`.) — molbdnilo, Jun 16 '21 at 15:02

molbdnilo · Accepted Answer · 2021-06-16T15:19:23.233

2

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

edited Jun 16 '21 at 15:19

answered Jun 16 '21 at 15:14

molbdnilo

64,751
3
43
82

so the problem is that for sml my datatype ```Node(b,_,_)``` is something like "compound" so I can't extract the value of v, rightaway? – tonythestark Jun 16 '21 at 15:19
I think the main problem is that you are assuming that parentheses are for surrounding an argument list, like in other languages. – molbdnilo Jun 16 '21 at 15:21
I know that in ```else``` for example sml needs to see only one instruction so we need parentheses to treat it as such but this is not the case here. Could you elaborate a little bit more ? – tonythestark Jun 16 '21 at 15:26
1

I don't understand what you're referring to. There are no instructions in SML, only expressions. – molbdnilo Jun 17 '21 at 05:32

If & Else & Pattern Matching in SML altogether?

1 Answers1