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.