[Haskell-cafe] Why does this blow the stack?

Brad Larsen brad.larsen at gmail.com
Fri Dec 21 12:48:09 EST 2007


On Fri, 21 Dec 2007 12:13:04 -0500, Justin Bailey <jgbailey at gmail.com>  
wrote:

> Given this function:
>
>   dropTest n = head . drop n $ [1..]
>
> I get a stack overflow when n is greater than ~ 550,000 . Is that
> inevitable behavior for large n? Is there a better way to do it?
>
> Justin

I'm curious as well.  My first thought was to try the (!!) operator.   
Typing

   Prelude> [1..] !! 550000

overflows the stack on my computer, as does dropTest 550000.


The code for (!!) is apparently as follows:

xs     !! n | n < 0 =  error "Prelude.!!: negative index"
[]     !! _         =  error "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)

Isn't this tail recursive?  What is eating up the stack?


Brad Larsen


More information about the Haskell-Cafe mailing list