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.
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
