# laziness in `length'

Serge D. Mechveliani mechvel at botik.ru
Mon Jun 14 10:25:06 EDT 2010

```Dear people and GHC team,

I have a naive question about the compiler and library of  ghc-6.12.3.
Consider the program

import List (genericLength)
main = putStr \$ shows (genericLength [1 .. n]) "\n"
where
n = -- 10^6, 10^7, 10^8 ...

(1) When it is compiled under  -O,  it runs in a small constant space
in  n  and in a time approximately proportional to  n.
(2) When it is compiled without -O,  it takes at the run-time the
stack proportional to  n,  and it takes enormousely large time
for  n >= 10^7.
(3) In the interpreter mode  ghci,   `genericLength [1 .. n]'
takes as much resource as (2).

Are the points (2) and (3) natural for an Haskell implementation?

Independently on whether  lng  is inlined or not, its lazy evaluation
is, probably, like this:
lng [1 .. n] =
lng (1 : (list 2 n)) =  1 + (lng \$ list 2 n) =
1 + (lng (2: (list 3 n))) = 1 + 1 + (lng \$ list 3 n) =
2 + (lng (3: (list 4 n)))   -- because this "+" is of Integer
= 2 + 1 + (lng \$ list 4 n) =
3 + (lng \$ list 4 n)
...
And this takes a small constant space.
Thank you in advance for your explanation,

-----------------
Serge Mechveliani
mechvel at botik.ru
```