SML-NJ List Equals Nil vs Null List

Question

I have a question about the way SML of New Jersey interprets lists:

Suppose I have a function f(x : 'a, n : int) : 'a list such that f returns a list of n copies of x, e.g. f(2,5) = [2,2,2,2,2], f(9,0) = [].

So then I go into the REPL, and I check f(9,0) = nil, and it returns true. From this, I assumed that you could use list = nil to check whether a list is the empty list. I used this in a function, and it wouldn't run. I ended up learning that the type definitions are different:

sml:121.2-123.10 Error: operator and operand don't agree [equality type required] operator domain: ''Z * ''Z
operand: 'a list * 'Y list
in expression:
xs = nil

(Where xs was my list). I then learned that the way to check if a list is the empty list is with null list. Why is this so? What's going on with nil? Can someone explain this behavior to me?

I also note that apparently (case xs = of nil is the same as checking null xs. Does this mean nil is a type?

Answer 1

This is an error related to polymorphism. By default, when an empty list is evaluated, it has the type 'a list. This means that the list can contain elements of any type. If you try to evaluate 1::[], you won't get a type error because of that. This is called polymorphism, it is a feature that allows your functions to take arguments of any type. This can be useful in functions like null, because you don't care about the contents of the list in that case, you only care about its length (in fact, you only care if it's empty or not). However, you can also have empty lists with different types. You can make your function return an empty int list. In fact, you are doing so in your function.

This is the result in a trivial implementation of your function:

- fun f(x : 'a, n : int) : 'a list =
    case n of
        0 => []
      | _ => x::f(x, n-1);
val f = fn : 'a * int -> 'a list
- f(4,5);
val it = [4,4,4,4,4] : int list
- f(4,0);
val it = [] : int list

As you can see, even if the second argument is 0, your function returns an int list. You should be able to compare it directly with an list of type 'a list.

- it = [];
val it = true : bool

However, if you try to compare two empty lists that have different types and are not type of 'a list, you should get an error. You can see an example of it below:

- [];
val it = [] : 'a list
- val list1 : int list = [];
val list1 = [] : int list
- val list2 : char list = [];
val list2 = [] : char list
- list1 = [];
val it = true : bool
- list2 = [];
val it = true : bool
- list1 = list2;
stdIn:6.1-6.14 Error: operator and operand don't agree [tycon mismatch]
  operator domain: int list * int list
  operand:         int list * char list
  in expression:
    list1 = list2

Also, case xs of nil is a way of checking if a list is empty, but this is because nil (which is just a way to write []) has the type 'a list by default. (Note that case expressions don't directly return a boolean value.) Therefore, nil is not a type, but 'a list is a polymorphic type that you can compare with lists of any type, but if your empty lists don't have polymorphic type, you will get a type error, which I think what is happening in your case.