[Haskell-cafe] ghc has problems with 'zipWith' ?

Daniel Fischer daniel.is.fischer at web.de
Tue Dec 7 12:44:33 EST 2004

I have recently come across the curious phenomenon that ghci is sometimes much 
slower than hugs. The occasion that gave rise to it was in connection with 
continued fractions, where, having a continued fraction with quotients a(n), 
n >= 0, you get the numerators of the convergents by the recursion formula

        p(n) = a(n)*p(n-1) + p(n-2)

starting with p(-2) = 0 and p(-1) = 1 (same recursion formula for the 
denominators, starting with q(-2) = 1 and q(-1) = 0). Now I implemented this 
algorithm first using 'zipWith':

ms :: [Integer] -> [Integer]
ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as)

only to find it awfully slow, ms (replicate 27 2) for example took over 10 
seconds, feeding a large list to 'ms' is inadvisable. Then I wrote a fast 
version of that algorithm, namely

ps :: [Integer] -> [Integer]
ps as = pStep 0 1 as
                  pStep :: Integer -> Integer -> [Integer] -> [Integer]
                  pStep _ _ [] = []
                  pStep x y (a:as) = z:pStep y z as
                                                    z = a*y+x

This works fine, so I wanted to find out what went wrong in the first version. 
In hugs, the 'zipWith'-version takes fewer reductions and both versions take 
more or less the same time, much less than 'ms' in ghci, more than 'ps' in 
ghci. The performance of 'ms' in ghci is significantly improved by a 'let' 
(or 'where') expression:

pms :: [Integer] -> [Integer]
pms as = let mas = pms as in
               zipWith (+) (zipWith (*) as (1:mas)) (0:1:mas)

(no difference in hugs), however this is still much slower than 'ps', 
last (pms (replicate 1000 1))
takes about 2.75 secs,
last (ps (replicate 1000 1))
about 0.01, even 
last (ps (replicate 10000 1))
took only 0.34 secs.

Since usually ghci is MUCH faster than hugs, I am baffled by this behaviour. 

Does anybody know why this is so? 
And, apart from avoiding 'zipWith', what can be done to remedy the situation?

Daniel Fischer

P.S.: ghci doesn't take 'zipWith' too well in other circumstances either, 
referring to the example of Fibonacci numbers in the book of Simon Thompson, 
the 'fastFib' function on page 76 runs faster in ghci than 'fibs' on page 
431, in hugs, 'fibs!!n' takes fewer reductions (no big difference though).

More information about the Haskell-Cafe mailing list