标准 ML：不确定高阶函数的类型

Question

我正在阅读 Harper 的书《标准 ML 简介》，对第 11.3 节“返回函数”有点困惑。

1) 他定义了一个创建常量函数的函数。他写道：

"给定一个值 k，应用程序 constantly k 产生一个函数，无论何时应用它都会产生 k。这是 constantly 的定义：

val constantly = fn k => (fn a => k)

该函数始终具有类型 'a -> ('b -> 'a)。”这对我来说很有意义：您提供类型 'a 的值，它 returns 一个始终 returns 该值的函数（类型 'a)，无论输入如何（类型 'b，可能与类型 'a 相同，也可能不同）。

但是他说我们也可以将这个函数定义为：

fun constantly k a = k

这看起来像是一个接受两个参数和 returns 第一个参数的函数...但不是 returns 另一个函数...

的函数

我错过了什么？

2) 稍后，Harper 讨论了 map 函数。我了解基本的地图功能。然后他谈到了一个 map 函数，它可以让我们将传入的函数应用于许多列表（而不是多次调用我们的原始 map 函数，每次调用都使用相同的传入函数）。他写道：

fun map' f nil = nil
    | map' f (h::t) = (f h) :: (map' f t)

"The function map so defined has type ('a -> 'b) -> 'a list -> 'b list. It takes a function of type 'a -> 'b as argument and yields another function of type 'a list -> 'b list as result."

我在这里很迷茫，因为它看起来像 map' 只是将 f 应用于列表中的所有元素和 returns 结果列表。所以我会认为它会是这样的类型：

('a -> 'b) * 'a list -> 'b list

我哪里错了？

感谢您的帮助，克莱曼

Answer 1

你的两个问题都是由于不清楚函数的实际参数是什么而引起的。在 SML 中，每个函数（回想一下函数是值）都只接受一个参数。该参数可能是一个元组（'a * 'b 类型，但它仍然是单个参数（需要解构）。

在SML中，fun f x1 x2 ... = T是val rec f = fn x1 => fn x2 => ... => T的语法糖。所以 constantly k 的计算结果为 fn a => k。

给map类型('a -> 'b) * 'a list -> 'b list还是('a -> 'b) -> 'a list -> 'b list是库设计问题，但效果是一样的。他们做同样的事情，虽然第一个接受一个函数的元组和一个列表，而第二个接受函数第一个和 returns 从列表到列表的函数。这在编程语言文献中称为 "currying"。（元组版本是"uncurried"，另一个是"curried"。）

Answer 2

神奇的词是"currying"：https://en.wikipedia.org/wiki/Currying

在 ML（以及 Haskell）中，函数应用程序比任何其他运算符绑定得更紧密。因此 constantly k a 解析为 (constantly k) a。 constantly k 绑定到一个函数。想明白是什么函数，可以脑补一下定义

fun constantly k a = k

相当于

fun (constantly k) a = k

这表示 (constantly k) 是将任意 a 映射到 k 的函数。

因此它的类型是 'a -> ('b -> 'a)，如文中所述。

通过

定义 constantly 没有任何违法行为

fun constantly (k,a) = k

它将具有您似乎期望的类型 'a * 'b -> 'a，但是将其称为 "constantly" 有点奇怪，因为它不是常量函数。

我相信哈珀迟早会做到这一点。此类函数在 ML 和 Haskell（尤其是 Haskell）中大量使用。

标准 ML：不确定高阶函数的类型

Standard ML: Unsure of Type of Higher Order Function

functional-programming

sml