为什么连懒惰的褶皱都如此渴望？

Question

此代码：

import Data.Foldable
import Debug.Trace

factors :: [Bool]
factors = [True, True, False, True, True, True, True, True]

andy :: Bool -> Bool -> Bool
andy False _ = False
andy True False = False
andy True True = True

tandy :: Bool -> Bool -> Bool 
tandy a b = let c = a `andy` b in trace (show a ++ " & " ++ show b ++ " = " ++ show c) c

wonder :: Bool
wonder = foldl tandy True factors

当我评估 wonder 时说：

True & True = True  
True & True = True  
True & False = False
False & True = False
False & True = False
False & True = False
False & True = False
False & True = False

但我希望它早点停止。我已经尝试用所有可以想象的东西代替 foldl 并用 && 代替 andy 但它似乎从来没有得到提示。

在我看来，andy False _ = False 行并没有要求编译器评估第二个参数。我没有强迫任何严格。这是怎么回事？即使是 C 也可以做得更好。

Answer 1

tandy 在两个参数中都是严格的，即使 andy 不是。这是因为跟踪。您要求它在对 trace 的调用中显示两个输入，因此它必须评估两个参数。

考虑“tandy2”：

tandy2 :: Bool -> Bool -> Bool
tandy2 False _ = trace ("False & anything = False") False
tandy2 True b = trace ("True & " ++ show b ++ " = False") b

与其在跟踪中盲目地评估两个参数，不如谨慎地只评估它本来会评估的相同参数。这使得它实际上反映了与 andy 相同的严格属性。

尝试将 tandy2 与 foldr 结合使用，您会发现它在遇到 False 时立即停止计算。

$ ghci
GHCi, version 9.2.1: https://www.haskell.org/ghc/  :? for help
ghci> import Debug.Trace
ghci> let tandy2 False _ = trace ("False & anything = False") False ; tandy2 True b = trace ("True & " ++ show b ++ " = False") b
ghci> foldr tandy2 True []
True
ghci> foldr tandy2 True [True]
True & True = False
True
ghci> foldr tandy2 True [True, False]
False & anything = False
True & False = False
False
ghci> foldr tandy2 True [True, False, True]
False & anything = False
True & False = False
False

给你。它从不多次计算 False 分支。

为什么连懒惰的褶皱都如此渴望？

Why are even lazy folds so eager?

haskell

lazy-evaluation