Haskell 惰性、求值顺序和模式匹配

Question

我先说我正在学习 Haskel，所以不要太苛刻。

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]                                    -- start
(or . map isBig) [7,1,2,1]                          -- definition of anyBig
or $ map isBig [7,1,2,1]                            -- definition of composition
foldr (||) False $ isBig 7 : map isBig [1,2,1]      -- or and map evaluated in some order
False || foldr (||) (isBig 7) (map isBig [1,2,1])   -- definition of foldr
foldr (||) (isBig 7) (map isBig [1,2,1])            -- definition of ||

现在有几种可能性

1. GHC 足够聪明，可以弄清楚唯一阻止模式匹配的是最后一个参数，所以它确实如此

foldr (||) (isBig 7) (isBig 1 : map isBig [2,1])     -- definition of map
(isBig 7) || foldr (||) (isBig 1) (map isBig [2,1])  -- definition of foldr

1. GHC 在同一级别评估所有内容，因为没有匹配项

foldr (||) True (isBig 1 : map isBig [2,1])          -- definition of map
True || foldr (||) (isBig 1) (map isBig [2,1])       -- definition of foldr

现在在情况 2. 中，根据 || 的定义，计算以 True 停止。在情况 1 中，我不清楚 GHC 是否愿意打开 map 以到达

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

或者如果它首先评估 isBig 7 并像 2 中那样返回。另外，假设我们真的以那个结束

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

这实际上会最大限度地显示，因为 || 是 infixr 所以它从右边开始。

Answer 1

(||) 函数 is implemented as [src] :

(||)                    :: Bool -> Bool -> Bool
True  || _              =  True
False || x              =  x

这意味着它会查看第一个操作数，如果它是 True，它不会对第二个操作数进行模式匹配，因此永远不会计算其余操作数。只有在第一个为 False 的情况下，它才会返回第二个操作数，从而继续计算。

这意味着:

    foldr (||) False (map isBig [7,1,2,1])
 -> foldr (||) False (isBig 7 : map isBig [1,2,1])
 -> isBig 7 || (foldr (||) False (map isBig [1,2,1]))
 -> True || (foldr (||) False (map isBig [1,2,1]))
 -> True

如果 foldr 因此使用一个可以(有时)仅通过评估第一个操作数返回结果的函数，它就可以停止递归。

当我们传递一个无限列表时，我们可以看到这一点。的确，例如:

anyBig (1 : 7 : repeat 1)

这里的列表是 [1, 7, 1, 1, 1, …]，所以有无限多的元素。但由于 isBig 7 为 True，它将停止并返回 True:

ghci> anyBig (1 : 7 : repeat 1)
True