Often in Haskell, one writes code like sum [x|x<-[1..n],x satisfies some predicate]. I understand that lazy evaluation can make things like this more efficient, for example the and function will stop evaluating a list as soon as it sees a single false. So will Haskell evaluate the entire list in the first case I mentioned, wasting tons of memory, or will lazy evaluation somehow make it as efficient as a tail-recursive or iterative approach?
1 Answer
As I mentioned in my comment, the reason sum tends not to run programs out of memory is complicated, and relies on compiler trickery. Therefore, I'll answer your question based on a let's-pretend world where sum is defined differently. GHC tries very hard to turn the real version into something more like the let's-pretend version whenever it can, so this is not too far from the truth. Let's pretend:
sum :: Num a => [a] -> a
sum xs = sumWith 0 xs
sumWith :: Num a => a -> [a] -> a
sumWith acc [] = acc
sumWith acc (x : xs) =
let acc' = acc + x
in acc' `seq` sumWith acc' xs
The detailed mechanics of [x | x <- [1..n], p x] are also a bit complicated, but you seem to be okay with the assumption that its elements are generated lazily, which is about all you need to know to consider the sum. For simplicity's sake, let's drop the predicate and just consider sum [1..3]:
sum [1..3]
==>
sumWith 0 [1..3]
==> -- pattern match on [1..3], forcing the first `(:)` constructor
let acc' = 0 + 1
in acc' `seq` sumWith acc' [2..3]
==> -- forcing acc' `seq` ... forces acc'
sumWith 1 [2..3]
==> -- pattern match on the list
let acc' = 1 + 2
in acc' `seq` sumWith acc' [3..3]
==> force acc'
sumWith 3 [3..3]
==>
let acc' = 3 + 3
in acc' `seq` sumWith acc' []
==>
sumWith 6 []
==>
6
As you can see, the seq forces the term to collapse down to its original size each time we take a step, so we operate in constant memory. In fact, GHC can do even better—various optimizations can often lead to this allocating no memory at all and operating entirely in CPU registers.
The real sum
The real sum is peculiar; I'd call it a historical artifact. It is missing the critical seq, so its definition is roughly equivalent to
sum :: Nom a => [a] -> a
sum xs = sumWith 0 xs
sumWith :: Num a => a -> [a] -> a
sumWith acc [] = acc
sumWith acc (x : xs) = sumWith (acc + x) xs
If you go through this step by step like I did above, you'll see that it doesn't operate in constant space, because the accumulator term will keep growing. It starts at 0, then goes to 0 + 1, then 0 + 1 + 2, then 0 + 1 + 2 + 3. Whoops! Fortunately, GHC can generally patch this problem up. It uses something called "demand analysis", a variety of "strictness analysis", to figure out that it can force the accumulator on each step without changing the meaning of the program. So it does that, and everything generally works out okay.
The real real sum
I've still been lying a bit, because the real sum is actually defined, these days, for all Foldable containers, and its definition for lists is really
sum = foldl (+) 0
foldl, in turn, is actually defined (for lists) as
foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
foldl k z0 xs =
foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0
Whaaaaat? Well, that oneShot is a bit of primitive magic to guide the optimizer. We can take it out and simplify things a bit:
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl k z0 xs = foldr (\v fn z -> fn (k z v)) id xs z0
I'm not going to go into detail here about how this "foldl as foldr" definition works—you can find various explanations around. But this strange definition is tied up with the list fusion magic Bakuriu mentioned in a comment. In particular, foldr combines nicely with lots of things by way of compiler rewrite rules in the list library.
sumis a little weird, but imagine definingsum' = foldl' (+) 0. Can you see why that won't run out of memory?sumdoes not run out of memory is complicated--it depends on compiler optimizations. But you can write your own version ofsumthat is easily seen to be space-safe.folds and built-in functions, but will fail when you use recursive definitions.