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

user_5916915 0
Viewed 69

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?

sml
2 Answers

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.

user_49962480

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
Ionut_G_Stan_588080
Related