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? -- Bruno Schneider http://www.dcc.ufla.br/~bruno/ _______________________________________________ Hugs-Users mailing list [hidden email] http://www.haskell.org/mailman/listinfo/hugs-users |
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 On Tue, Mar 23, 2010 at 12:01 PM, Bruno Schneider <[hidden email]> 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? > > -- > Bruno Schneider > http://www.dcc.ufla.br/~bruno/ > _______________________________________________ > Hugs-Users mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/hugs-users > Hugs-Users mailing list [hidden email] http://www.haskell.org/mailman/listinfo/hugs-users |
-----Ursprüngliche Nachricht-----
Von: Neil Mitchell <[hidden email]> 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 >> [hidden email] >> http://www.haskell.org/mailman/listinfo/hugs-users >> >_______________________________________________ >Hugs-Users mailing list >[hidden email] >http://www.haskell.org/mailman/listinfo/hugs-users Hugs-Users mailing list [hidden email] http://www.haskell.org/mailman/listinfo/hugs-users |
On Wed, Mar 24, 2010 at 7:27 AM, Daniel Fischer wrote:
[...] > > 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. > So it goes to the stack, hum? It thought it would be just a pointer to some computation type on the heap. Anyway, thanks for the detailed answer. I asked here because I didn't test that code on any other compiler/interpreter, so it could be something related to hugs implementation. -- Bruno Schneider http://www.dcc.ufla.br/~bruno/ _______________________________________________ Hugs-Users mailing list [hidden email] http://www.haskell.org/mailman/listinfo/hugs-users |
-----Ursprüngliche Nachricht-----
Von: Bruno Schneider Gesendet: 24.03.2010 13:56:32 An: [hidden email] Betreff: Re: [Hugs-users] stack overflow in tail recursive function >On Wed, Mar 24, 2010 at 7:27 AM, Daniel Fischer wrote: >[...] >> >> 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. >> > >So it goes to the stack, hum? It thought it would be just a pointer to >some computation type on the heap. Well, the thunk is built on the heap, that's correct, but when it's evaluated, things go on the stack. > >Anyway, thanks for the detailed answer. I asked here because I didn't >test that code on any other compiler/interpreter, so it could be >something related to hugs implementation. > That's okay, but as a rule of thumb, if you don't know that it's implementation-specific, haskell-cafe or beginners (depending on what sort of answer you want) is the better choice; hugs-users or glasgow-haskell-users are less frequented. In this case, the behaviour is a little implementation-dependent, if you use GHC and compile with optimisations, the strictness-analyser should see that the result of the multiplication is needed and the compiler should make it strict by itself. (I currently have no access to a computer with GHC installed, so I can't check that it does indeed.) > >-- >Bruno Schneider >http://www.dcc.ufla.br/~bruno/ Cheers, Daniel _______________________________________________ Hugs-Users mailing list [hidden email] http://www.haskell.org/mailman/listinfo/hugs-users |
Free forum by Nabble | Edit this page |