[Haskell-cafe] Flattening tail recursion?

[Daniel Fischer]

Hi everyone,

I had the idea that, instead of using 'seq', one might check for parity:

countLines2 aux (_:l)
      | even aux = ...
      | odd aux  = ...

that prevents stack overflow, but is much slower than
countLines1 aux (_:l)
     | aux `seq` False = ...
     | otherwise          = ...

I also tried
countLines3 aux (_:l)
     | even aux || odd aux = ...
     | otherwise                 = ...
and
countLines4 aux (_:l)
     | even aux || True = ...
     | otherwise            = ...
which also are slower than countLines1.
Well, checking for parity takes time, so that is no real surprise. 
What somehow puzzles me is that, compiling with -O, all versions of countLines 
are equally fast, if I give the type

countLines :: Int -> [a] -> Int,

but if I replace Int with Integer, the plain version without guards and the 
'seq' version are equally fast whereas the parity-check versions are equally 
fast among themselves but slower than plain. 
If I omit the type-declaration, all versions perform differently, plain 
producing stack overflow, countLines1 being by far the fastest, countLines4 
coming in second, then countLines3 and last countLines2.

If I give the type Int -> [a] -> Int and use interpreted code, plain 
overflows, countLines1 is by far the fastest, but then things change. Now 
countLines2 comes in second, third is countLines4, relatively close, last, at 
a distance, is countLines3. (Qualitatively the same, but slower, without 
type-declaration).

With type Int -> [a] -> Int, but compiled without -O, the results are (for 
countLinesX 0 [1 .. 1500000])
plain : stack overflow,
1  : 0.43 secs,
2  : 1.10 secs,
3  : 1.26 secs,
4  : 0.93 secs.

Now obviously -O does a good job (though 'seq' isn't so bad even without -O), 
but why does checking for parity take extra time for Integer and not for Int?

And why does compilation without -O change the order of versions 2-4 ?

If anybody knows, mind telling me?

Thanks in advance,
Daniel

Am Freitag, 10. Dezember 2004 22:37 schrieb Jules Bean:
> On 10 Dec 2004, at 20:33, GoldPython wrote:
> > Just compiled this with -O and it ran with no stack overflow.
> > Evidently, no `seq` needed for this one. Using ghc 6.2.2.
> >
> > countLines l = countLines' 0 l
> > countLines' n [] = n
> > countLines' n (_:ls) = countLines' (n + 1) ls
>
> That's presumably the answer. GHC's strictness analyser *can* cope with
> this situation but only under -O... whereas most of us where testing
> under ghci...
>
> Confirmation from one of the Simons?
>
> Jules
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe