SML Error:Types of if branches do not agree

Question

I am trying to find if an element is a part of a set. Here is my function:

fun elementOf(x:int, (nil:int list, nil:bool list)) = nil
  | elementOf(x, (y::ys, z::zs)) = if x = y then z else elementOf(x, (ys, zs));

So if I were to call elementOf(2, ([2,7,4], [false,true,false])) it would return false.

However, I get the error message:

Error: types of if branches do not agree [tycon mismatch]
then branch: bool
else branch: 'Z list
in expression: if x = y then z else elementOf(x,ys,zs))

What is a 'Z list and how do I fix this error?

Answer 1

What is a 'Z list?

A 'Z list is Standard ML's way of inferring the return type of nil in your base case. nil could be any type of list, since it's empty. 'Z is a type variable.

How do I fix this error?

The problem is that elementOf cannot sometimes return nil and other times true / false. By changing the base-case to false, the function will work such that elements not in the list are also not in the set:

fun elementOf(x:int, (nil:int list, nil:bool list)) = false
  | elementOf(x, (y::ys, z::zs)) = if x = y then z else elementOf(x, (ys, zs));

But there is probably not a good reason to store elements that are not in the set, as opposed to throwing them away. A slightly more efficient representation would simply be a list of members:

fun elementOf (x, nil : int list) = false
  | elementOf (x, y::ys) = x = y orelse elementOf (x, ys)

Or made with the built-in list combinator List.exists:

fun elementOf x xs = List.exists (y => x = y) xs

Or written in point-free style:

fun curry f x y = f (x, y)
val elementOf = List.exists o curry op=

A better one yet relies on binary trees:

data binTree = Empty
             | Node of binTree * int * binTree

fun elementOf (x, Empty) false
  | elementOf (x, Node (left, y, right)) =
    (case Int.compare (x, y) of
          LESS => elementOf (x, left)
        | EQUAL => true
        | GREATER => elementOf (x, right))