[Hugs-users] stack overflow in tail recursive function

[Daniel Fischer]

-----Ursprüngliche Nachricht-----
Von: Neil Mitchell <ndmitchell at gmail.com>
Gesendet: 23.03.2010 21:40:39
An: Bruno Schneider 
Betreff: Re: [Hugs-users] stack overflow in tail recursive function

>Hi Bruno,
>
>I suggest you ask this question on the haskell-cafe@ mailing list -
>it's a general Haskell question, and you'll get a much more detailed
>answer there.
>
>Thanks, Neil
>


Yes, this sort of general Haskell questions will receive earlier and more answers in the cafe.
Nevertheless, Neil, I'm not sure he'd get a much more detailed answer to this question there ;)

Okay, so

>On Tue, Mar 23, 2010 at 12:01 PM, Bruno Schneider  wrote:
>> Hi all,
>>
>> I have this tail recursive factorial function:
>>
>> factorial :: Integer -> Integer
>> factorial 0 = 1
>> factorial n = fat' n 1 where
>>    fat' 1 fat = fat
>>    fat' n fat = fat' (n-1) (n*fat)
>>
>> Whenever I run it with a number of 20000 or more I get a stack
>> overflow error. It doesn't seem a problem with the large resulting
>> number because, if so, the message should be something like "Garbage
>> collection fails to reclaim sufficient space". Other functions seem to
>> able to handle a larger number of recursive calls.
>>
>> So, what is the problem with this particular function?


Laziness is more pervasive than you expected. Your accumulator doesn't actually accumulate the product so far, it accumulates the way to obtain that product, because the multiplication isn't carried out but deferred until really needed.
So the evaluation of factorial 4 goes

fat' 4 1
(4 /= 1)
fat' (4-1) (4*1)
(4-1 = 3 /= 1)
fat' (3-1) (3*(4*1))
(3-1 = 2 /= 1)
fat' (2-1) (2*(3*(4*1)))
(2-1 = 1 == 1)
(2*(3*(4*1)))

and this expression is only evaluated if necessary. factorial 20000 builds a thunk of 20000 nested multiplications, this is tried to evaluate when the value is demanded for printing, but the expression is too deeply nested to fit on the stack.

You have to make sure the multiplications in the accumulator aren't deferred until the very end.
Here, the only sensible way is to explicitly tell the Haskell system to evaluate the product immediately,

factorial :: Integer -> Integer
factorial n
  | n < 0      = error "factorial of negative argument"
  | n == 0    = 1
  | otherwise = fac' n 1
    where
      fac' 1 acc = acc
      fac' k acc = fac' (k-1) $! k*acc

The ($!) says "evaluate now (to the outermost constructor)", for Integers that's complete evaluation, so you have no thunks building up and you can calculate factorials of far larger numbers (though it's slow this way).

A stack overflow most of the time signals a laziness leak, that some part of a function built up a thunk where it shouldn't and you have to force some level of evaluation manually.

>>
>> --
>> Bruno Schneider
>> http://www.dcc.ufla.br/~bruno/
>> _______________________________________________
>> Hugs-Users mailing list
>> Hugs-Users at haskell.org
>> http://www.haskell.org/mailman/listinfo/hugs-users
>>
>_______________________________________________
>Hugs-Users mailing list
>Hugs-Users at haskell.org
>http://www.haskell.org/mailman/listinfo/hugs-users