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.

2
Contributors
6
Replies
16
Views
4 Years
Discussion Span
Last Post by DarkLightning7

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.

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?

Edited by 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.

Edited by 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)`?

Edited by DarkLightning7

`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.

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