sml - 如何在 SML 中推断函数类型

Question

我有一个foo定义如下的函数

fun foo x y = x (x (x y));

如何推断函数类型？

答案是：

val foo = fn : ('a -> 'a) -> 'a -> 'a

Answer 1

这个过程称为类型推断，由Hindley-Milner 算法在 SML 中完成。

首先让我们从泛型类型签名开始foo：

val foo = fn : 'c -> 'b -> 'a

where xhas type'c和yhas type 'b。

我们有以下步骤：

• x y是函数应用，x应该有签名'b -> 'd，我们有一个方程'c = 'b -> 'd并且x y有类型'd。
• x (x y)意味着我们'b -> 'd在参数类型'dso 'd = 'b和上应用函数类型'c = 'b -> 'b。
• x (x (x y))意味着我们'b -> 'b在参数类型上应用函数类型'b并返回'a（类型foo）；就够了'b = 'a。
• 统一后，我们有'c = 'a -> 'a and 'b = 'a并且foo有一个泛型类型：val foo = fn : ('a -> 'a) -> 'a -> 'a