Reduce space usage of genericLength for common Num instances

[thorkilnaur]

There is a space leak in genericLength:

$ ghc/stage2-inplace/ghc --interactive
GHCi, version 6.11.20090116: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :module +List
Prelude List> genericLength [1..600000]
*** Exception: stack overflow
Prelude List>
Prelude List> length [1..600000]
600000
Prelude List>

The attached patch against the base library provides a fix.

Best regards Thorkil

[thorkilnaur]

Patch to fix space leak in genericLength

[NeilMitchell]

The patch is incorrect. If the (+) function isn't strict in both arguments then you are too strict.

You could always add genericLength', and add specialisation rules for genericLength on Int/Integer/Float/Double, which gets you all the benefits in the common cases but still preserves the semantics.

[thorkilnaur]

Thank you very much. I will look into this.

Best regards Thorkil

[thorkilnaur]

I attach a patch that adds rules for genericLength::[a]->Int and genericLength::[a]->Integer. Adding rules for Float and Double seems excessive, but it is of course easily done.

That the result is as intended is witnessed by:

$ ghc-6.11.20090211 --version
The Glorious Glasgow Haskell Compilation System, version 6.11.20090211
$ cat R.hs
import List
import IO
main = do hSetBuffering stdout NoBuffering
          print $ map ($ [1..4000000])
            [ genericLength :: [a] -> Int
            , fromIntegral . (genericLength :: [a] -> Integer)
            , round . (genericLength :: [a] -> Double)
            ]
$ ghc-6.11.20090211 -fforce-recomp --make R -O
[1 of 1] Compiling Main             ( R.hs, R.o )
Linking R ...
$ ./R
[4000000,4000000,Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
$

Interestingly, this patch only solves the problem for compiled code. I don't know if it is possible to solve it for interpreted code also.

Best regards Thorkil

[thorkilnaur]

Patch to add rules to make genericLength strict for Int/Integer lengths

[dons]

In general we need rules for left folds on atomic types not being 'foldl'.

sum, product, length, maxium, minimum, etc.

There are open tickets relating to this already, iirc.

[igloo]

Applied, thanks!