Why map does not force strictness whereas zipWith does?

Question

There are two strict versions of zipWith function:

1) Really strict, elements of lists l1 and l2 get evaluated so their thunks do not eat all stack space (Don Stewart code)

zipWith' f l1 l2 = [ f e1 e2 | (e1, e2) <- zipWith k l1 l2 ]
            where
                k x y = x `seq` y `seq` (x,y)

2) Not really strict, attempt to force evaluation by other way.

zipWith'' f l1 l2 = [ f e1 e2 | (e1, e2) <- zip (map (\x -> x `seq` x) l1) (map (\x -> x `seq` x) l2) ]

The question is: why the equivalent code from the 2nd example using map does not make the function also strict?

Respirator

The zipWith' function will force any element thunks in l1 and l2 as it processes the elements, but the f e1 e2 thunk is not forced. – Judie

Answer 1

It's a common mistake to use

x `seq` x

Which is exactly equivalent to

x

An excellent explanation is available in Neil Mitchell's post on Bad Strictness.

Snapp

Interesting but it does not correspond why the following versions are not equivalent: zipWith''' f l1 l2 = [ f e1 e2 | (e1, e2) <- zip (sLst l1) (sLst l2) ] where sLst [] = [] sLst (x:xs) = x seq x : sLst xs and zipWith''' f l1 l2 = [ f e1 e2 | (e1, e2) <- zip (sLst l1) (sLst l2) ] where sLst [] = [] sLst (x:xs) = x : sLst xs – Respirator

Recursive construction of list with x seq x : sLst xs makes it strict whereas "equivalent" x : sLst xs does not ... – Respirator

Those are not equivalent. The first version you wrote is seq x (x : sLst xs). Mind the associativity. – Snapp

Forget it, my mistake due to functions precedence. The former expression without parens did meant x seq (x : sLst xs). – Respirator

Answer 2

Instead of tautological map, one can use this function to force the list:

evl []     = []
evl (x:xs) = x `seq` (x:evl xs)
-- Cannot figure out how to do this with fold.

Then the strict zipWith is

zipWith''' f xs ys = zipWith f (evl xs) (evl ys)

Trovillion

This will not work for infinite lists, while Don's version will. – Snapp

Some explanation for beginners like me why n.m.'s solution won't work for infinite lists ? – Respirator

@jaspervdj: It seems to work with infinite lists too (it forces the elements, not the spine). – Trovillion