# maximum: stack overflow?

5 messages
Open this post in threaded view
|

## maximum: stack overflow?

 Hi all, Why does finding the maximum element of a big list cause a stack overflow: In ghci, if I print out a big list: *Main> [1..1000000] it takes a while but it prints. However, looking for the maximum element fails: *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? Patrick -- ===================== Patrick LeBoutillier Rosem?re, Qu?bec, Canada
Open this post in threaded view
|

## maximum: stack overflow?

 Hi Patrick, On Thu, Mar 12, 2009 at 10:35 PM, Patrick LeBoutillier <[hidden email]> 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_overflowWhy 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/
Open this post in threaded view
|

## maximum: stack overflow?

 On Thu, Mar 12, 2009 at 9:33 PM, Roland Zumkeller <[hidden email]> wrote: > Why is maximum not defined in terms of foldl1'? Probably because > situations in which non-strictness is beneficial are thought to be > more common. How did this get established? Isn't maximum always (semantically) strict anyway? I.e. maximum [1,2,undefined] = undefined Alex