Hi Patrick,
On Thu, Mar 12, 2009 at 10:35 PM, Patrick LeBoutillier
*Main> maximum [1..1000000] *** Exception: stack overflow
It seems to me like maximum should just be going through the list one by one and keeping track on the largest element seen do far. Why does in need to keep the entire list around (I presume), causing the stack overflow?
This is due to non-strict evaluation. The Prelude defines maximum xs = foldl1 max xs for non-empty xs and foldl1 f (x:xs) = foldl f x xs. Instead of just maintaining an integer in its first argument, foldl constructs a chain of thunks, i.e. expressions awaiting evaluation. You can use the strict version of foldl1 (called foldl1') to avoid this problem: *Main> import Data.List *Main Data.List> foldl1' max [1..1000000] 1000000 A more detailed explanation can be found here: http://www.haskell.org/haskellwiki/Stack_overflow Why is maximum not defined in terms of foldl1'? Probably because situations in which non-strictness is beneficial are thought to be more common. Also, the two are not equivalent: *Main Data.List> foldl1 (flip (||)) [undefined,False,True] True *Main Data.List> foldl1' (flip (||)) [undefined,False,True] *** Exception: Prelude.undefined Best, Roland -- http://roland.zumkeller.googlepages.com/