CODEWITHSUNDEEP
syntaxsml
user1981597
user1981597

Reputation: 1

Beginner SML Syntax

I am very new to SML. I am currently working on a project that is checking to see if a mobile is balanced.

My datatype mobile is defined as follows:

datatype mobile = Object of int 
                | Wire   of mobile * mobile

Then I have a weight function to check the weight of a mobile: 

fun weight (Object w)   = w 
  | weight (Wire (l,r)) = weight l + weight r

I am now trying to check if the mobile is balanced. I have the following: 

fun balanced (Object w)   = true 
  | balanced (Wire (l,r)) = if weight l = weight r and balanced l and balanced r then true else false

However, I keep getting an error:

stdIn:18.19-18.31 Error: syntax error: deleting  AND ID
stdIn:18.34 Error: syntax error found at AND

Could someone please tell me what I am doing wrong?

Upvotes: 0

Views: 755

Answers (3)

raok
raok

Reputation: 191

By the way, this is a very inefficient way to determine whether a mobile is balanced, because the weights of subtrees are computed over and over again. Think of a function weight_of_balanced_mobile that either returns NONE if the mobile is not balanced or SOME w if it is balanced.

fun weight_of_balanced_mobile (Object w) = SOME w
  | weight_of_balanced_mobile (Wire (l,r)) =
       case weight_of_balanced_mobile l
         of NONE => NONE
          | SOME u => case weight_of_balanced_mobile r
                        of NONE => NONE
                         | SOME v => if u = v then SOME (u+v) else NONE;

 fun is_balanced mobile =
        case weight_of_balanced_mobile mobile
          of NONE => false
           | SOME _ => true;

The problem here is that your 'balanced' function returns just one bit of information, whereas to compute efficiently, we need more information. I have come to regard Boolean as a danger sign.

Another way to structure the computation so that you get more information (not just that something is balanced, but how heavy it is) is to pass a continuation. We'll make a function that takes a mobile and a 'what to do if this mobile is balanced' argument. Oh, let's make it take a 'value value to use if it isn't as well.

(* val check_balance : mobile -> 'a -> (int -> 'a) -> 'a *)
fun check_balance (Object w) _ f = f w
  | check_balance (Wire (l,r)) d f =
       check_balance l d (fn u =>
          check_balance r d (fn v =>
             if u = v then f (u+v) else d));

fun is_balanced mobile = check_balance mobile false (fn _ => true);

If you look at it just right, this is the same as the previous code turned inside out.

Upvotes: 2

Jesper.Reenberg
Jesper.Reenberg

Reputation: 5944

As Brian points out, we use andalso and orelse in SML.

However there are no errors in the code, when this is fixed correctly.

Also as pointed out by Andreas Rossberg, when ever you write an expression of the form

if b then 
  true
else
  false

then you should immediately think of this picture, and exchange it with the expression b, as it is obviously the same.

Given this, your balanced function end up looking something like this

fun balanced (Object w)   = true
  | balanced (Wire (l,r)) = weight l = weight r andalso
                            balanced l andalso balanced r

Upvotes: 3

Brian
Brian

Reputation: 20285

Changing and to andalso gets past the syntax error found at AND errors.

- fun balanced (Object w) =
    true | balanced(Wire(l,r)) = 
    if weight l = weight r andalso balanced l andalso r
    then
     true
    else
     false;

But then you get this:

stdIn:5.8-5.29 Error: operand of andalso is not of type bool [tycon mismatch]
  operand: mobile
  in expression:
    (balanced l) andalso r

which is because the type of the weight function is val weight = fn : mobile -> int which does not satisfy the boolean constraint for andalso since it returns an int.

Upvotes: 1

Related Questions