[Haskell-beginners] maximum: stack overflow?
roland.zumkeller at gmail.com
Fri Mar 13 00:33:18 EDT 2009
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
*Main> import Data.List
*Main Data.List> foldl1' max [1..1000000]
A more detailed explanation can be found here:
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]
*Main Data.List> foldl1' (flip (||)) [undefined,False,True]
*** Exception: Prelude.undefined
More information about the Beginners