[Haskell-cafe] A question about stack overflow
Huazhi (Hank) Gong
hankgong at nm.gist.ac.kr
Tue Jun 27 07:30:56 EDT 2006
Thank you very much for introducing tail recursion.
It's my first time to hear this. :)
However, I'm wondering whether every loop structure from C like language can
be translated to this kind of tail recursion?
From: Chris Kuklewicz [mailto:haskell at list.mightyreason.com]
Sent: Tuesday, June 27, 2006 5:34 PM
To: Huazhi (Hank) Gong
Cc: haskell-cafe at haskell.org
Subject: Re: [Haskell-cafe] A question about stack overflow
Huazhi (Hank) Gong wrote:
> Hi, all
> I'm just a newbie for Haskell and functional programming world. The idea
> I currently read is quite different and interesting.
> I have one general question about the recursively looping style. For
> myMax [ ] = error "empty list"
> myMax [x] = x
> myMax [x:xs] = if x>= (myMax xs) then x else (myMax xs)
> I just list out this kind of very simple program. However, if the list
> size if a big number such as 10000000, the Winhug will report that the
> stack is overflow.
> Does it mean that the functional programming is lacking of scalability?
> I do know that we can manually change the stack size for it. But that's
> not a good solution according to my opinion.
> Yours, Hank
The function is not "tail recursive"
Think about unfolding the recursion:
mymax [1,2,3,4] =
if 1 >= (if 2 >= (if 3 >= (4)
then 3 else (4))
then 2 else (<above>))
then 1 else (<above>)
If 4 is a long list, then the chain of "if" statements gets larger than size
the stack that the runtime will allow. The definition you have looks like a
"right fold" where compare the head to the function applies to the remaining
list and what you need is a "left fold" where you process the list so far
operate on the next element.
More information about the Haskell-Cafe