Re: stack overflow in tail recursive function

-----Urspr=C3=BCngliche Nachricht-----
Von: Neil Mitchell <[email protected]>
Gesendet: 23.03.2010 21:40:39
An: Bruno Schneider=20
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 a=
nswers in the cafe.
Nevertheless, Neil, I'm not sure he'd get a much more detailed answer to th=
is 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 =3D 1
>> factorial n =3D fat' n 1 where
>> =C2=A0 =C2=A0fat' 1 fat =3D fat
>> =C2=A0 =C2=A0fat' n fat =3D 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 actu=
ally accumulate the product so far, it accumulates the way to obtain that p=
roduct, because the multiplication isn't carried out but deferred until rea=
lly needed.
So the evaluation of factorial 4 goes

fat' 4 1
(4 /=3D 1)
fat' (4-1) (4*1)
(4-1 =3D 3 /=3D 1)
fat' (3-1) (3*(4*1))
(3-1 =3D 2 /=3D 1)
fat' (2-1) (2*(3*(4*1)))
(2-1 =3D 1 =3D=3D 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 deferre=
d until the very end.
Here, the only sensible way is to explicitly tell the Haskell system to eva=
luate the product immediately,

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

The ($!) says "evaluate now (to the outermost constructor)", for Integers t=
hat's complete evaluation, so you have no thunks building up and you can ca=
lculate 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 o=
f 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
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/hugs-users
>>
>_______________________________________________
>Hugs-Users mailing list
>[email protected]
>http://www.haskell.org/mailman/listinfo/hugs-users