laziness in `length'

[Roman Beslik]

On 14.06.10 17:25, Serge D. Mechveliani wrote:
>   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)
>    
Actually matters are more complicated. In the highlighted steps you 
implicitly used associativity of (+). Of course, Haskell can not do 
this. Also 'lng' and 'genericLength' *are not tail recursive*. This 
explains stack overflow. If you compute length with 'foldl' 
(tail-recursively) and without "-O" flag, than you will see excessive 
heap usage. Also, GHC's 'length' and 'foldl'' are tail recursive and 
eagerly computes length/accumulator, so they are effective without "-O" 
flag. See for explanation
http://www.haskell.org/haskellwiki/Stack_overflow

-- 
Best regards,
   Roman Beslik.