Why is the signature different for these two Standard ML functions?

Question

I am trying to implement a function that checks whether or not a list is empty (similar to List.null).

This has signature val isEmpty = fn: ''a list -> bool:

fun isEmpty ls =
  ls = []

This has signature val isEmpty = fn: 'a list -> bool:

fun isEmpty [] = true
  | isEmpty _ = false

Why are the signatures different for these two functions although they do the same thing?

John Coleman · Accepted Answer · 2022-05-19T11:32:21.247

1

A big hint to what is happening here is that (in SML/NJ) the first definition triggers Warning: calling polyEqual. It is based on a list comparison, but in SML that only makes sense for equality types. Your first definition fails when you do something like

isEmpty [1.0, 2.1];

whereas the other two definitions have no problem with that. Thus -- the three definitions don't "do the same thing". They almost do, but not quite.

See Warning: calling polyequal for more on that warning.

edited May 19 '22 at 11:32

answered May 19 '22 at 11:12

John Coleman

51,337
7
54
119

In Poly/ML and Moscow ML, there is no warning. In Moscow ML, `isEmpty [1.0, 2.1];` gives no error. – Flux May 19 '22 at 11:17
@Flux I was using SML/NJ.Whether or not there is a warning, the signature on the first definition says that it only applies to lists of equality types. Perhaps in Moscow ML `real` is implemented as an equality type. If so, this is non-standard. You should be able to find another example (e.g. a list of functions) for it to throw an error. – John Coleman May 19 '22 at 11:26
Thank you. My mistake was in testing the function only on int list, char list, and string list inputs. – Flux May 19 '22 at 14:21

score 0 · Answer 2 · edited May 21 '22 at 09:30

The main reason is that the first version is more powerful than the second. The equality operator has the following type, which will constrain the type signature of the first version:

$ sml
Standard ML of New Jersey (64-bit) v110.99.2 [built: Thu Sep 23 13:44:44 2021]
- op =;
val it = fn : ''a * ''a -> bool

The ''a constraint propagates to the enclosing function definition.

The second version doesn't make use of that operator because it doesn't need to, it only needs to look at the shape of the list, not its constituent elements. We can desugar it to make this more obvious:

fun isEmpty list =
  case list of
  | nil => true
  | _ :: _ => false

It's clear here that it doesn't care about the elements, whereas the other does care, potentially, even if it doesn't in your particular case. For example:

fun isPalindrome list =
  list = List.rev list

Why is the signature different for these two Standard ML functions?

2 Answers2