SML beginner syntax problem.

[DarkLightning7]

I'm trying to implement a simple recursive list search in SML/NJ but am getting some errors i dont understand. Here is the code:

fun find x  y = 
    if (null y)
        then false
    else if x = hd(y)
        then true
    else find(x, tl(y));

Here are the errors:

stdIn:130.6-135.22 Error: case object and rules don't agree [circularity]
  rule domain: ''Z * ''Z list
  object: (''Z * ''Z list) * 'Y
  in expression:
    (case (arg,arg)
      of (x,y) =>
           if null y
           then false
           else if <exp> = <exp> then true else find <exp>)
stdIn:130.6-135.22 Error: right-hand-side of clause doesn't agree with function result type [tycon mismatch]
  expression:  'Z -> _
  result type:  bool
  in declaration:
    find = (fn arg => (fn <pat> => <exp>))

Line 130 is:

fun find x y = (

Any help is greatly apreciated.

[sepp2k]

You're defining your function as f x y, so it's a curried function of type ''a -> ''a list -> bool. However you call it recursively as f (x, tl y), so you call it with a tuple as its argument.

If we insert a tuple ''b * ''b list as ''a into the type signature, we get (''b * ''b list) -> (''b * ''b list) list -> bool, so the expression find (x, tl y) has the type (''b * ''b list) list -> bool. However it should just have the type bool. Therefore you get a type error.

To fix your issue you should either call your function as a curried function (find x (tl y)) or define it as a tupled function fun find (x,y) = .... You can't define it as one and call it as the other.

[DarkLightning7]

Thanks for the reply. Im still not sure what im doing wrong Im trying to call tl[tail function] on y inside of find(), but what im actualy doing is passing tl and y as arguments?

[DarkLightning7]

I got the interpreter to accept it but the function doesn't return anything when its called.

fun find x  y = 
    if (null y)
        then false
    else if (x = (hd y))
        then true
    else (find x (tl(y)));


find (3, [2,3,5]);
find (3, [1,2,5]);

Here is the output for the above:

val find = fn : ''a -> ''a list -> bool
val it = fn : (int * int list) list -> bool
val it = fn : (int * int list) list -> bool

What am i doing wrong?

Also if somone could explain the difference between find(x, tl(y)) and (find x (tl y)) because they appear to be the same logicly, that would be great.

[DarkLightning7]

Sorry just figured out i was calling it wrong should be (find 3 [2,3,5]); and (find 3 [1,2,5]);. Why do i have to call it this way when a function like fun factorial n = if n < 1 then 1 else n * factorial (n - 1); can be called using factorial(10)?

[sepp2k]

factorial(10) is just an unidiomatic way to write factorial 10, i.e. it calls factorial with the number 10 as its argument. The reason that it works is that it's legal to surround any expression with parentheses. For the same reason it would also be legal to write val x = (10) instead of val x = 10 or (10) + (4) instead of 10 + 4.

When you write find (3, [1,2,5]), you're calling find with the tuple (3, [1,2,5]) as its argument. Since the argument to find can be of any type, SML accepts this and simply remembers that ''a (the type of the argument to find) is int * int list, i.e. a tuple containing an integer and a list of integers. Since the return type of find is ''a list -> bool and ''a in this case is int * int list, that means that this call to find will return a function of type (int * int list) list -> bool as its result, which clearly isn't what you want.

As I said, you need to decide when you define a function (that needs more than one argument) whether you want it to take its arguemnts in form a tuple of arguments or whether you want it to be curried and then you need to call it that way.

[DarkLightning7]

Thanks. Your above answer made a lot of sense I didnt realize I was constructing a tuple when i called the function that way.