haskell - 多态函数的特化

Question

在他的演讲“类，Jim，但不是我们所知道的”中，Simon Peyton-Jones 谈到了如何在 GHC 中实现类型类，方法是让多态函数采用一个额外的参数，该参数是一个具有正确函数的字典赋予功能。

然后他说 GHC 经常通过特殊大小写函数来优化函数，而不是在运行时实际传递这个字典。然后他说这并不总是可能的，因为Haskell 具有多态递归，所以即使你拥有整个程序，也不一定能消除所有的多态。

他这是什么意思？在编译时无法知道多态函数将传递的类型的程序示例是什么？

Answer 1

这是一个多态递归的典型例子。假设我们有一个类似于列表的数据类型，但每个元素的类型是前一个元素的两倍：

data Poly a = Nil | Cons a (Poly (a,a)) deriving Show

foo :: Poly Int
foo = Cons 3 (Cons (4,5) (Cons ((6,7),(8,9)) Nil))

length' :: Poly a -> Int
length' Nil = 0
length' (Cons _ xs) = 1 + length' xs

请注意，递归调用length'与原始调用具有不同的类型。

由于不可能静态地知道可能会创建哪些此类列表，因此我们无法从程序中删除所有字典。