ML类型的功能,一个小窍门？

Question

我准备GATE考试.最古老的问题之一是我们不熟悉.有些专家请为我们澄清一下.

以下哪一项可以作为以下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),是一个2元组.函数的参数必须是元组然后:

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);

我们没有找到关于参数类型的更多信息,我们只是确认元组的第二个元素必须确实是一个列表,因为它使用了::构造函数.

我们来看看身体:

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

看起来它正在构建一个列表,所以它必须返回一个列表,这与我们到目前为止描绘的返回类型一致,即... list.让我们试着找出元素的类型.

它似乎添加了一个函数对象作为通过递归调用函数构建的列表的头部f,我们正在研究该函数.所以我们返回的列表元素必须是函数:

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

但是这个功能有什么作用呢？它g使用2元组参数调用.现在我们可以填写一些关于2元组f接收的第一个元素的信息.它必须是一个接收2元组的函数:

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变量分配了一个类型,但是它来自于接收到的2元组的第二个参数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

类型变量到具体类型的对应表可以是这样的:

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

我们可以在这里停止,因为我们可以看到它'b被分配给不同的类型,因此这个函数签名不能分配给我们给出的实现.

选择3和4

它们与选择2类似,但我会将它们作为练习给读者:)