Why are even lazy folds so eager?

user_2910747 0
Viewed 103

This code:

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

says this when I evaluate 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

but I would have preferred it to have stopped sooner. I've tried this with everything imaginable in place of the foldl and with && in place of andy but it never seems to get the hint.

It seems to me that the line andy False _ = False doesn't invite the compiler to evaluate the second parameter. I haven't forced any strictness. What's going on? Even C can do better.

lazy-evaluation haskell
1 Answers

tandy is strict in both parameters, even though andy is not. This is because of the tracing. You ask it to show both inputs in the call to trace, so it has to evaluate both arguments.

Consider `tandy2':

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

Instead of blindly evaluating both arguments in its tracing, it is careful to only evaluate the same arguments it would otherwise. This makes it actually reflect the same strictness properties as andy has.

Try using tandy2 with foldr and you'll see it stops evaluating as soon as it hits a 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

There you go. It never evaluates the False branch more than once.

user_3832000
Related