毫升类型的功能，一丁点提示？

Question

我为高考做准备。最古老的问题之一是我们不熟悉。一些专家请为我们澄清这一点。

以下哪一种类型可以用于下面的ML函数？

my f(g, nil)=nil | f(g,x::xs)=(fn a  ⇒ g(a,x))::f(g, xs);

1) (int *book → real) * bool list → (int → real) list
2) (bool *int → int) * real list → (bool → int) list
3) (int *int → real) * real list → (real → bool) list
4) (bool *real → int) * int list → (int → int) list

答案单上写着(1)是正确的。为了更好的理解，评论还是简短的描述？

Answer 1

您应该做的第一件事之一是自己重写函数定义。这将迫使您实际解析和理解它。

fun f (g, nil)     = nil
  | f (g, x :: xs) = (fn a => g (a, x)) :: f (g, xs);

因此，f是一个函数，甚至问题是，它必须具有... -> ...类型。

val f : ... -> ...

它收到了什么？让我们看一下函数的第一个模式：

fun f (g, nil)     = nil

这是某种形式的(a, b)，它是一个二元组。那么，函数的参数必须是元组：

val f : (... * ...) -> ...

通过查看定义，我们无法确定g必须具有什么类型，但是它使用nil作为元组的第二个元素，nil是空列表。这意味着元组的第二个组件必须是以下内容的列表：

val f : (... * ... list) -> ...

我们还能推断出什么？返回值也是nil，这意味着函数返回某个东西的列表，还不清楚它是什么。

val f : (... * ... list) -> ... list

好的，让我们现在跳到函数定义的第二个模式：

| f (g, x :: xs) = (fn a => g (a, x)) :: f (g, xs);

我们没有找到更多关于参数类型的信息，我们只是确认元组的第二个元素必须是list，因为它使用的是::构造函数。

让我们看看身体：

(fn a => g (a, x)) :: f (g, xs)

它看起来像是在构建一个列表，所以它必须返回一个列表，这与我们所勾画的返回类型(即... list )是一致的。让我们试着找出元素的类型。

它似乎添加了一个函数对象作为列表的头，这个列表是通过递归调用函数f构建的，我们目前正在研究这个函数。因此，我们返回的列表中的元素必须是函数：

val f : (... * ... list) -> (... -> ...) list

不过，这个功能是什么呢？它使用两个元组参数调用g。现在，我们可以填写一些有关二元组f接收的第一个元素的信息。它也必须是一个接收两个元组的函数：

val f : (((... * ...) -> ...) * ... list) -> (... -> ...) list

我们能对添加到返回列表中的函数文字接收到的a参数说些什么吗？不完全是，只是把它传递给了g。我们能告诉任何关于x类型的信息吗？不完全是，只是把它传递给了g。此外，a和x之间是否存在任何约束？看上去不像。到目前为止，我们只能知道g的类型一定是这样的：

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

其中'a、'b和'c是多态类型，即任何具体类型都可以满足它们。你可以把它们看作是整体。现在我们可以为f函数填充更多的类型：

val f : ((('a * 'b) -> 'c) * ... list) -> (... -> ...) list

实际上，我们可以做得更多，我们已经为x变量分配了一个类型，但是这来自于f接收的二元组的第二个参数，所以让我们也填写一下：

val f : ((('a * 'b) -> 'c) * 'b list) -> (... -> ...) list

我们甚至可以填写返回列表的元素类型，因为我们已经为此分配了类型。

val f : ((('a * 'b) -> 'c) * 'b list) -> ('a -> 'c) list

我们可以在不改变含义的情况下，从我们想出的类型中删除一些额外的括号，因为类型操作符优先规则：

val f : ('a * 'b -> 'c) * 'b list -> ('a -> 'c) list

现在，我们的函数类型已经完成。但是，这种类型在可能的答案列表中找不到，所以我们必须看看是否可以使用其中的任何一种，而不是我们已经确定的答案。为什么？因为我们的函数类型使用类型变量，这些变量可以由具体类型填充。让我们一个接一个地把他们：

选择1

val f : ('a  * 'b   -> 'c)   * 'b list   -> ('a  -> 'c) list
val f : (int * bool -> real) * bool list -> (int -> real) list

看起来'a可能是int，'b可能是bool (您粘贴的是book，但我假设它是一个错误)，'c可能是一个真实的。所有的替换都与这些对应匹配，所以我们声明，是的，对于给定的函数，第一选择可以是一种可能的类型，即使不是最一般的。让我们做第二个选择：

选择2

val f : ('a   * 'b  -> 'c)  * 'b list   -> ('a   -> 'c) list
val f : (bool * int -> int) * real list -> (bool -> int) list

具体的-type对应表的类型变量可以是：

• 'a -> bool
• 'b -> int
• 'c -> int
• 'b -> real

我们可以在这里停止，因为我们可以看到'b被分配给不同的类型，所以这个函数签名不能分配给我们已经给出的实现。

选择3和4

它们类似于选择2，但我将让它们作为读者的练习:)