函数式编程中的签名/类型(OCaml)

Question

我开始学习函数式编程(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>

感谢您的帮助和解释.

Answer 1

为了理解这种类型的签名,你需要理解几个概念,我不知道你已经做了哪些,所以我尽力解释每个重要的概念:

哗众取宠

如您所知,如果您有类型foo -> bar,则描述一个带有类型参数foo并返回类型结果的函数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可以用一个int或一个string或一个list或任何东西来调用- 这没关系.

此外,如果同一类型变量不止一次出现在类型签名中,则它将代表相同的类型.所以在上面的例子中,这意味着返回类型f与参数类型相同.因此,如果f用a调用int,则返回一个int.如果用a调用它string,则返回a string等等.

所以类型的函数'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的类型是,第二个参数的第二个参数的类型.

返回值将是类型'c,即第一个函数的返回类型.

Answer 2

如果你真的对这个主题感兴趣(并且可以访问大学图书馆),请阅读Wadler的优秀(如果有些过时)"函数式编程简介".它以非常好的和可读的方式解释了类型签名和类型推断.

另外两个提示:请注意 - >箭头是右关联的,因此您可以从右侧包含事物,这有时有助于理解事物,即a -> b -> c与...相同a -> (b -> c).这与第二个提示相关:高阶函数.你可以做的事情

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

所以在FP中,将'add'想象为一个必须采用两个数值参数并返回数值的函数通常不是正确的事情:它也可以是一个函数,它接受一个数值参数并返回一个带有类型的函数num - > num.

理解这将有助于您理解类型签名,但您可以在没有的情况下完成.在这里,快速简便:

# 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立即推断出类型.