[Haskell-beginners] maximum: stack overflow?

[Roland Zumkeller]

Hi Patrick,

On Thu, Mar 12, 2009 at 10:35 PM, Patrick LeBoutillier
<patrick.leboutillier at gmail.com> wrote:
> *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/