[Haskell-cafe] A question about stack overflow
Donald Bruce Stewart
dons at cse.unsw.edu.au
Tue Jun 27 04:34:20 EDT 2006
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
More information about the Haskell-Cafe
mailing list