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

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