maximum: stack overflow?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

maximum: stack overflow?

Patrick LeBoutillier
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
Reply | Threaded
Open this post in threaded view
|

maximum: stack overflow?

Roland Zumkeller-2
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_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/
Reply | Threaded
Open this post in threaded view
|

maximum: stack overflow?

Alexander Dunlap
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
Reply | Threaded
Open this post in threaded view
|

maximum: stack overflow?

Roland Zumkeller-2
Hi Alex,

On Fri, Mar 13, 2009 at 12:43 AM, Alexander Dunlap
<[hidden email]> wrote:
> Isn't maximum always (semantically) strict anyway? I.e.
>
> maximum [1,2,undefined] = undefined

If max is (semantically) strict, then so is maximum.
On the other hand, both may be non-strict:

> data Switch = Off | On deriving (Eq, Show)

> instance Ord Switch where
>   On <= Off = False
>   _  <= _   = True
>   max _ On  = On
>   max a Off = a

*Main> maximum [undefined,Off,On]
On
*Main> foldl1' max [undefined,Off,On]
*** Exception: Prelude.undefined

Best,

Roland

--
http://roland.zumkeller.googlepages.com/
Reply | Threaded
Open this post in threaded view
|

maximum: stack overflow?

Chaddaï Fouché
On Fri, Mar 13, 2009 at 6:05 AM, Roland Zumkeller
<[hidden email]> wrote:

> Hi Alex,
>
> On Fri, Mar 13, 2009 at 12:43 AM, Alexander Dunlap
> <[hidden email]> wrote:
>> Isn't maximum always (semantically) strict anyway? I.e.
>>
>> maximum [1,2,undefined] = undefined
>
> If max is (semantically) strict, then so is maximum.
> On the other hand, both may be non-strict:

The case where max is not strict seldom happen and anyway in those
cases foldr1 would be more appropriate than foldl1 (which won't allow
fast termination, though a non-strict max may save you from stack
overflow)...
Note that with -O or -O2 you may have a specialization of maximum to
foldl1' if you're working on Int or Integer or ...

I guess the report really dropped the ball on this one with its
failure to settle on either lazyness or strictness.

--
Jeda?