Data type declaration in ML

Question

I'm reviewing some Scheme to ML conversions we had done in class awhile back, and I'm confused on why we did (or didn't) do something. The first ML code becomes:

fun sub(x,y,nil) = nil
  | sub(x,y,z1::z2) = if (x = z1) then y :: sub(x,y,z2) else z1::sub(x,y,z2);

The 2nd one becomes:

datatype InputType=Null | Number of int  | Cons of InputType*InputType;

fun sub2(x,y,Null) = Null 
  | sub2(x,y,Number(z)) = if (x = z) then Number(y) else Number(z)
  | sub2(x,y,Cons(z1,z2)) = Cons(sub2(x,y,z1),sub2(x,y,z2));

I understand that the variable types need to be the same throughout the entire function. Therefore, since there is type Null, number, and cons, they need to be combined in a data type. However, with that logic, why does the first one not need a new data type? Last I checked, type "Null" and type "Cons" are not the same thing....

Any help would be appreciated. Thanks.

Answer 1

The first function simply uses the list type, which is predefined in the SML library as

datatype 'a list = nil | :: of 'a * 'a list

(where :: is additionally declared to be infix). So same situation in both cases, really.

As an aside, note that Null or Cons are not types. They are data constructors, i.e., values.