为什么这两个标准 ML 函数的签名不同？

Question

我正在尝试实现一个检查列表是否为空的函数（类似于 List.null）。

这有签名 val isEmpty = fn: ''a list -> bool:

fun isEmpty ls =
  ls = []

这有签名 val isEmpty = fn: 'a list -> bool:

fun isEmpty [] = true
  | isEmpty _ = false

为什么这两个函数的签名不同，尽管它们做同样的事情？

Answer 1

这里发生的事情的一个重要提示是（在 SML/NJ 中）第一个定义触发 Warning: calling polyEqual。它基于列表比较，但在 SML 中只对相等类型有意义。当您执行类似

的操作时，您的第一个定义失败

isEmpty [1.0, 2.1];

而其他两个定义没有问题。因此——这三个定义不会“做同样的事情”。他们几乎做到了，但不完全是。

有关该警告的更多信息，请参阅 Warning: calling polyequal。

Answer 2

主要原因是第一个版本比第二个版本更强大。相等运算符具有以下类型，它将约束第一个版本的类型签名：

$ 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

''a 约束传播到封闭函数定义。

第二个版本没有使用该运算符，因为它不需要，它只需要查看列表的形状，而不是其组成元素。我们可以将其脱糖以使其更明显：

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

很明显，它不关心这些元素，而另一个可能关心，即使在您的特定情况下它不关心。例如：

fun isPalindrome list =
  list = List.rev list

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