9

我开始学习函数式编程（OCaml），但我不了解有关 fp 的一个重要主题：签名（我不确定它是否是正确的名称）。当我输入一些东西并用 ocaml 编译时，我得到例如：

# let inc x = x + 1 ;;
val inc : int -> int = <fun>

这是微不足道的，但我不知道，为什么会这样：

let something f g a b = f a (g a b)

给出一个输出：

val something : (’a -> ’b -> ’c) -> (’a -> ’d -> ’b) -> ’a -> ’d -> ’c = <fun>

我想，对于你们中的许多人来说，这个主题绝对是 fp 的基础知识，但我在这里寻求帮助，因为我在互联网上没有找到任何关于 OCaml 中签名的内容（有一些关于 Haskell 中的签名的文章，但没有解释）。

如果这个话题能以某种方式继续存在，我在这里发布了几个函数，这些签名让我感到困惑：

# let nie f a b = f b a ;; (* flip *)
val nie : (’a -> ’b -> ’c) -> ’b -> ’a -> ’c = <fun>

# let i f g a b = f (g a b) b ;;
val i : (’a -> ’b -> ’c) -> (’d -> ’b -> ’a) -> ’d -> ’b -> ’c = <fun>


# let s x y z = x z (y z) ;;
val s : (’a -> ’b -> ’c) -> (’a -> ’b) -> ’a -> ’c = <fun>

# let callCC f k = f (fun c d -> k c) k ;;
val callCC : ((’a -> ’b -> ’c) -> (’a -> ’c) -> ’d) -> (’a -> ’c) -> ’d = <fun>

感谢您的帮助和解释。

4

2 回答 2

18

要理解这种类型签名，您需要了解几个概念，我不知道您已经了解了哪些概念，所以我尽力解释了每个重要概念：

咖喱

如您所知，如果您有 type foo -> bar，则这描述了一个函数，该函数接受 type 的参数foo并返回 type 的结果bar。由于->是右结合的，因此类型foo -> bar -> baz与foo -> (bar -> baz)并因此描述了一个接受类型参数foo并返回类型bar -> baz值的函数，这意味着返回值是一个接受类型值bar并返回类型值的函数baz。

这样的函数可以被称为my_function my_foo my_bar，因为函数应用是左关联的，所以它与 相同(my_function my_foo) my_bar，即它应用于my_function参数my_foo，然后将作为结果返回的函数应用于参数my_bar。

因为它可以这样调用，所以类型的函数foo -> bar -> baz通常被称为“一个带有两个参数的函数”，我将在这个答案的其余部分这样做。

类型变量

如果您定义一个类似的函数let f x = x，它将具有类型'a -> 'a。但'a实际上 OCaml 标准库中的任何地方都没有定义类型，那么它是什么？

任何以 a 开头的类型'都是所谓的类型变量。类型变量可以代表任何可能的类型。所以在上面的例子中，f可以用 anint或 astring或 alist或任何东西来调用 - 没关系。

此外，如果同一类型变量多次出现在类型签名中，则它将代表同一类型。所以在上面的例子中，这意味着返回类型f与参数类型相同。因此，如果f使用 an 调用int，则返回 an int。如果用 a 调用它string，它会返回 astring等等。

因此，一个类型的函数'a -> 'b -> 'a可以接受任何类型的两个参数（第一个和第二个参数的类型可能不同）并返回一个与第一个参数相同类型的值，而一个类型的函数'a -> 'a -> 'a将接受两个参数同一类型。

关于类型推断的一个注意事项：除非你明确地给一个函数一个类型签名，否则 OCaml 总是会推断出最通用的类​​型。因此，除非函数使用仅适用于给定类型的任何操作（+例如），否则推断的类型将包含类型变量。

现在解释一下类型...

val something : ('a -> 'b -> 'c) -> ('a -> 'd -> 'b) -> 'a -> 'd -> 'c = <fun>

这个类型签名告诉你这something是一个接受四个参数的函数。

第一个参数的类型是'a -> 'b -> 'c。即一个函数采用任意且可能不同类型的两个参数并返回任意类型的值。

第二个参数的类型是'a -> 'd -> 'b。这又是一个有两个参数的函数。这里要注意的重要一点是，函数的第一个参数必须与第一个函数的第一个参数具有相同的类型，并且函数的返回值必须与第一个函数的第二个参数具有相同的类型。

第三个参数的类型是'a，这也是两个函数的第一个参数的类型。

最后，第四个参数的类型是'd，也就是第二个函数的第二个参数的类型。

返回值将是 type 'c，即第一个函数的返回类型。

于 2010-11-17T00:43:11.293 回答
6

如果您真的对该主题感兴趣（并且可以访问大学图书馆），请阅读 Wadler 的优秀（如果有些过时）“函数式编程简介”。它以一种非常好读的方式解释了类型签名和类型推断。

两个进一步的提示：请注意 -> 箭头是右关联的，因此您可以将事物从右边括起来，这有时有助于理解事物，即a -> b -> c与a -> (b -> c). 这与第二个提示有关：高阶函数。你可以做类似的事情

let add x y = x + y
let inc = add 1

因此在 FP 中，将“add”视为一个必须接受两个数值参数并返回一个数值的函数通常不是正确的做法：它也可以是一个接受一个数值参数并返回一个具有类型的函数的函数数 -> 数。

理解这一点将帮助你理解类型签名，但你也可以不这样做。在这里，快速简便：

# let s x y z = x z (y z) ;;
val s : (’a -> ’b -> ’c) -> (’a -> ’b) -> ’a -> ’c = <fun>

看右手边。y给定一个参数，所以它是类型a -> b，其中 a 是 的类型z。x给定了两个参数，第一个参数是z，所以第一个参数的类型也必须是a。(y z)第二个参数 的类型是，b因此 的类型x是(a -> b -> c)。这使您可以s立即推断出类型。

于 2010-11-17T00:42:33.177 回答