[Haskell-cafe] Why does not zipWith' exist

[Daniel Fischer]

On Friday 01 February 2013, 12:50:18, Andres Löh wrote:
> Hi Kazu.
> 
> I'd be surprised if zipWith' yields significant improvements. In the
> case of foldl', the strictness affects an internal value (the
> accumulator). However, in the case of zipWith', you're just forcing
> the result a bit more, but I guess the "normal" use pattern of fibs is
> that you want to see a prefix of the result anyway. So the overall
> amount of evaluation is the same.
> 
> I've tried to hack up a quick criterion test comparing my own naive
> zipWith, the Prelude zipWith (which may have additional optimizations,
> I haven't checked), and zipWith':

> 
> main :: IO ()
> main = defaultMain $ [
>     bench "fibs " (nf (take 10000 . fibs ) ())
>   , bench "fibsP" (nf (take 10000 . fibsP) ())
>   , bench "fibs'" (nf (take 10000 . fibs') ())
>   ]
> 
> The additional () arguments are to prevent GHC from sharing the list
> in between calls. I haven't tested thoroughly if GHC looks through
> this hack and optimizes it anyway.
> 
> Compiling without optimization, I get 1.15ms/1.11ms/1.10ms.
> With -O, I get 85us/85us/88us.
> 
> Am I overlooking anything? What's your test?

zipWith' would [I haven't tested, but I'm rather confident] make a difference if 
you benchmarked

    bench "name" (whnf (fibs !!) 100000)

etc.

The reason is that 

foo = initialValues : zipWith f foo (tail foo)

is rather a scan than a real zip, so evaluating an element depends on 
evaluating all previous elements, and thus can build a huge thunk if the 
elements aren't demanded in order.

For a real zip where an element of the result does not depend on the values of 
earlier elements, plain zipWith would perform (usually only marginally) better 
than zipWith'.