[Haskell-cafe] A question about stack overflow

[Chris Kuklewicz]

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
 > example:
 >
 > 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 of 
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 then 
operate on the next element.

-- 
Chris