曾经有人向我展示了SML中的一个小技巧，他们在REPL中编写了大约3或4个函数，最后一个值的结果类型非常长（需要很多页才能滚动完）。
是否有人知道生成这种长类型的代码，或者是否有一个名称来描述这种行为？
SML中类型定义的增长：使用Hindley Milner类型推断
28
- jkcorrea
2
在这种特定情况下，展示了推理系统的最坏情况复杂度，并且生成的类型跨越了许多页面滚动。只是好奇如何重新创建它。 - jkcorrea
在编程中，"many page scrolls" 是一个不同于我所想的 "long" 的版本。 - user2864740
1个回答
45
Hindley/Milner类型推断推断的类型如果以正确的方式组合，可能会呈指数级增长。例如：
在这种情况下，类型再次呈指数级增长，但与上述情况不同的是，所有组成类型都是不同的新鲜类型变量，因此即使图形表示也会呈指数级增长（在pN声明数量方面）。 因此，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风格的类型推断在最坏情况下是指数级的（在空间和时间上）。 但值得指出的是，指数级情况只能发生在类型呈指数级增长的情况下 - 即在您甚至无法实际表达需要进行类型推断的情况下。
- Andreas Rossberg
1
1非常棒的解释，不仅告诉了我们如何做，更重要的是为什么会发生这种情况。非常感谢！ - jkcorrea
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接