functional-programming - 使用 Hindley Milner 类型推断的 SML 中类型定义的增长

Question

有人曾经在 SML 中向我展示了一个小技巧，他们在他们的 REPL 中写出了大约 3 或 4 个函数，最后一个值的结果类型非常长(就像许多页面滚动很长)。

有谁知道什么代码会生成这么长的类型，或者是否有这种行为的名称？

Answer 1

如果以正确的方式组合它们，由 Hindley/Milner 类型推断推断的类型可能会变得指数级大。例如:

fun f x = (x, x, x)
val t = f (f (f (f (f 0))))

在这里， t是一个嵌套的三元组，其嵌套深度对应于 f 的调用次数 n .因此，整体类型的大小为 3^n。

然而，这实际上并不是最坏的情况，因为类型具有规则结构并且可以在线性空间中有效地由图表示(因为在每个级别上，所有三个组成类型都是相同的并且可以共享)。

真正最坏的情况是使用多态实例化来解决这个问题:

fun f x y z = (x, y, z)
val p1 = (f, f, f)
val p2 = (p1, p1, p1)
val p3 = (p2, p2, p2)

在这种情况下，类型再次呈指数级大，但与上面不同的是，所有组成类型都是不同的新类型变量，因此即使是图形表示也会呈指数增长(在 pN 声明的数量上)。

所以是的，Hindley/Milner 风格的类型推断是最坏情况指数(空间和时间)。然而，值得指出的是，指数情况只能发生在类型变得指数大的情况下——即在没有类型推断的情况下你甚至无法实际表达的情况。