Haskell惰性求值下anyBig函数的GHC求值顺序探究

Haskell的惰性求值是否有用或存在风险，取决于计算瓶颈是时间复杂度还是栈大小。为了更深入理解Haskell的求值机制，我们来看下面的示例：

首先定义简单函数：

isBig :: Int -> Bool
isBig = (<=) 5

基于此，我们定义判断列表中是否存在大数的函数：

anyBig :: [Int] -> Bool
anyBig = or . map isBig

按照惰性求值的特性，传入[7,1,2,1]时，理论上只需要调用一次isBig就能返回True。我们来梳理GHC可能的求值顺序：

anyBig [7,1,2,1]                                    -- 开始
(or . map isBig) [7,1,2,1]                          -- 展开anyBig的定义
or $ map isBig [7,1,2,1]                            -- 展开函数组合(.)的定义
foldr (||) False $ isBig 7 : map isBig [1,2,1]      -- 展开or和map的定义（顺序不定）
False || foldr (||) (isBig 7) (map isBig [1,2,1])   -- 展开foldr的定义
foldr (||) (isBig 7) (map isBig [1,2,1])            -- 展开||的定义（False || x = x）

此时，存在两种求值可能性：

• 可能性1：GHC足够智能，识别出唯一阻碍模式匹配的是最后一个参数，因此执行：

foldr (||) (isBig 7) (isBig 1 : map isBig [2,1])     -- 展开map的定义
(isBig 7) || foldr (||) (isBig 1) (map isBig [2,1])  -- 展开foldr的定义

• 可能性2：GHC因无匹配项，会在同一层级求值所有内容：

foldr (||) True (isBig 1 : map isBig [2,1])          -- 展开map的定义，同时求值isBig 7得到True
True || foldr (||) (isBig 1) (map isBig [2,1])       -- 展开foldr的定义

在情况2中，根据||的定义（True || _ = True），计算会立即终止并返回True。但在情况1中，不确定GHC会优先展开map得到：

(isBig 7) || (isBig 1) || (isBig 2) || (isBig 1) 

还是会先求值isBig 7，像情况2那样直接返回结果。另外，假设最终得到上述表达式，由于||是右结合（infixr），如果从右侧开始计算，反而会达到最慢的速度。

内容的提问来源于stack exchange，提问作者MannyC