[Haskell-cafe] ghc has problems with 'zipWith' ?
Daniel Fischer
daniel.is.fischer at web.de
Tue Dec 7 12:44:33 EST 2004
Hi,
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
where
pStep :: Integer -> Integer -> [Integer] -> [Integer]
pStep _ _ [] = []
pStep x y (a:as) = z:pStep y z as
where
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?
Greetings,
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