haskell - haskell在处理复杂的程序流程时有多懒

Question

我想知道 Haskell 有多聪明/多懒。我能否始终确定 Haskell 只会执行生成特定输出所必需的操作？

Answer 1

没有。

Haskell 为其核心类 lambda 演算指定了指称语义，您可以依赖该语义。此外，还有一个元理论证明特定的归约顺序——通俗地称为“惰性求值”——实现了语义；许多人将其用作 Haskell 程序行为方式的心智模型。

Haskell 程序可能会以两种方式结束不必要的评估:

• Haskell 实现可能会选择评估更多。 GHC 在大多数地方使用惰性求值，但我相信在某些情况下它会使用其他求值顺序来提高效率。您还可以查看 Eager Haskell项目，它正试图使用​​另一种实现策略。原则上，一个实现将有权选择将一些计算推测性地 fork 到另一个线程(然后在不需要时丢弃结果)。依此类推——这个主题有很多可能的变体。

• 指定的指称语义可能需要比“必要”更多的评估。例如，一个偶尔会绊倒初学者的:

    primes :: [Int]
    primes = 2 : filter prime [3,5..]
  
    prime :: Int -> Bool
    prime x = and [x `mod` p /= 0 | p <- primes, p < x]
  

  当检查 3 是否应该在列表 primes 中时，实际上没有必要检查 primes 过去的任何元素2，因为序列是严格单调递增的。但是 Haskell 并没有(没有尝试)聪明到注意到这一点；它将直接尝试检查其余的 primes 并以无限循环结束，而不是给出素数列表。

  一个更小的例子:你可能认为 x && False 总是 False，但是 x 通常会被计算，因为语义说如果 x 是，这应该是一个无限循环。 (对比 False && x，它通常不会导致计算 x。)

就是说，当您说到“复杂结构”时，想到的一件事是:Haskell 是否会做惰性事情即使是我定义的自定义数据类型？也就是说， HashMap 、平衡树和 k-d 树等复杂结构是否得到了惰性处理？答案是是，至少对于 GHC 是这样；除了 IO 之外，Prelude 中的任何类型在本质上都没有什么特别之处。列表、 bool 值、Maybe 等是惰性的，不是因为编译器了解它们的特殊之处，而仅仅是因为 Haskell 指定的惰性求值减少规则及其作为类型的声明。

当然，有很多方法可以选择退出懒惰。您将在 Hackage 上看到的一些结构以各种方式实现了这一点；但别担心，通常这会在他们的文档中声明。