[Haskell-cafe] A question about stack overflow

[Donald Bruce Stewart]

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