# A question about stack overflow

8 messages
Open this post in threaded view
|

## A question about stack overflow

 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: 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  > 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 ())      then 1 else () 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: A question about stack overflow

 In reply to this post by Huazhi (Hank) Gong hankgong: > >    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 >    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. > No, your code is just really inefficient (think about how many times its traversing the list). Try rewriting it as a simple accumulating pass over the list, carrying the largest element you've seen so far.     mymax []     = undefined     mymax (x:xs) = f x xs         where           f x [] = x           f x (y:ys) | y > x     = f y ys                      | otherwise = f x ys However, 'f' is just a foldl inlined:     import Data.List     mymax []     = undefined     mymax (x:xs) = foldl' (\a b -> if b > a then b else a) x xs And the lambda is just 'max':     import Data.List     mymax []     = undefined     mymax (x:xs) = foldl' max x xs Now, we already check for the empty list, so avoid checking again:     import Data.List     mymax [] = undefined     mymax xs = foldl1' max xs And that'll do. -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: A question about stack overflow

 Hi, >   mymax []     = undefined >   mymax (x:xs) = f x xs >       where >         f x [] = x >         f x (y:ys) | y > x     = f y ys >                    | otherwise = f x ys Or if you don't want to go for a fold next, in a style more similar to the original: maximum [] = undefined maximum [x] = x maximum (a:b:xs) = maximum (max a b : xs) Thanks Neil _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: A question about stack overflow

 Neil Mitchell wrote: > Or if you don't want to go for a fold next, in a style more similar to > the original: > > maximum [] = undefined > maximum [x] = x > maximum (a:b:xs) = maximum (max a b : xs) It even reproduces the stack overflow, though for a different reason. Better write it this way: maximum [] = undefined maximum [x] = x maximum (a:b:xs) = let m = max a b in m `seq` maximum (m : xs) Udo. -- "The condition of man is already close to satiety and arrogance, and there is danger of destruction of everything in existence."         -- a Brahmin to Onesicritus, 327 BC,            reported in Strabo's Geography _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe signature.asc (196 bytes) Download Attachment
Open this post in threaded view
|

## RE: A question about stack overflow

 In reply to this post by haskell-2 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? Yours, Hank -----Original Message----- From: Chris Kuklewicz [mailto:[hidden email]] Sent: Tuesday, June 27, 2006 5:34 PM To: Huazhi (Hank) Gong Cc: [hidden email] 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  > 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 ())      then 1 else () 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe