GHC Data.List.sort performance question

[Bertram Felgenhauer]

Judah Jacobson wrote:
> > This means that the library version produces a stack overflow on
> > lists generated in an iterate like fashion (say, take 1000000 [0..]).
> > The modified version produces a stack overflow on the reverse of
> > that list, but I believe such lists are much rarer in practice.
>
> Bertram, are you sure that's right?

Yes.

> There's already a stack overflow
> in "take 1000000 [0..]" itself (try just "last $ take 1000000 [0..]").
>  See the bug http://hackage.haskell.org/trac/ghc/ticket/1997

No, that's not quite right. The stack overflow happens on evaluating
the last element of that list *without evaluating the previous elements
first*.

To wit,

Prelude Data.List> foldl' (+) 0 $ take 1000000 [0..]
499999500000
Prelude Data.List> last $ take 1000000 [0..]
*** Exception: stack overflow

or

Prelude> let t = take 1000000 [0..]
Prelude> last t
*** Exception: stack overflow
Prelude> t !! 500000
500000
Prelude> last t
999999

Bertram