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 |
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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
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 |
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 |
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 (<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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Huazhi (Hank) Gong
--- Huazhi (Hank) Gong" <[hidden email] wrote:
> 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? Yes, as discovered by John McCarthy almost 50 years ago in "Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184-195, 1960". Ciao, Janis Voigtlaender. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Udo Stenzel
On 6/27/06, Udo Stenzel <[hidden email]> wrote:
> 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. How about this: maximum (a:b:xs) = maximum ((: xs) $! max a b) --ihope _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |