带有 Integral 类型类的 Haskell 斐波那契列表

Question

如果我在 GHCi 中加载以下列表，则列表的计算速度会很慢，直到计算完列表中的第 33 项 3524578 后程序最终关闭。

fibonacci :: (Integral a) => [a]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

如果我删除第一行并加载以下行，列表的计算速度会非常快并且 GHCi 不会关闭。

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

为什么多态列表比Integer列表慢这么多？ GHCi 为什么关闭？

Answer 1

在你的第一个版本中，虽然它看起来像一个值，但你实际上编写了一个函数(比 Haskell 本身级别更低的函数)。

要理解这一点，请考虑您的定义可能包含的以下代码:

main = println (fibonacci !! 17 :: Int, fibonacci !! 19 :: Integer)

当然，17和19完全是任意的。要点是，第一个元组元素需要将斐波那契计算为 Int 列表，而第二个元组元素则假设它是 Integers 列表。你可能知道，Haskell 中不存在这样的介于 Int 和 Integer 之间的列表 - 列表要么是 [Int] 要么是 [Integer](或完全不同的东西)。

正因为如此，我们可以根据纯粹的逻辑基础得出结论，无需深入了解 Haskell 的运行时系统，fibonacci也不是 的列表Int 也不是 Integer 列表，也不是其他内容的列表 - 它只是根据请求构建此类列表的方法。

话虽这么说，只要你这样做:

take 10 fibonacci

应该没有那么重要(斐波那契仅计算一次最多 10 个元素)。

但是当你说

map (fibonacci !!) [1..10]

有可能为每个索引重新计算斐波那契数。显然，指数越高，所需的时间就越长。