用HindleyMilner型推理在SML中定义类型定义的增长
有人曾经在SML中向我展示过一些“技巧”，他们在REPL中写出了3或4个函数，最后一个值的结果类型非常长（如许多页面滚动长）。
有人知道什么代码会产生这么长的类型，或者是否有这种行为的名称？
由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式的推断是最坏情况下的指数（在空间和时间上）。 然而，值得指出的是，指数情况只能发生在类型呈指数级增长的情况下 - 即在没有类型推断的情况下，甚至不能实际表达。
链接地址: http://www.djcxy.com/p/80885.html上一篇: Growth of Type Definition in SML Using Hindley Milner Type Inference