[Haskell-cafe] Stupid newbie question

[Jeremy Shaw]

Hi,

In this case, the stack overflow you are seeing is due to laziness not
tail recursion.

Because you never demand the value of any element in the list, Haskell
never bothers to calculate it. So you have a list that looks like:

 [ i,  i - 1, (i - 1) - 1, ((i - 1) - 1 - 1), .. ]

So, by the time you get up to some big numbers, you have built up a
very large thunk. For some reason this is causing a stack overflow.

The easiest solution is to make things a little more strict. For
example, if you change:

nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs

to:

nth i (x:xs) = x `seq` (if i < 0 then Empty else nth (i-1) xs)

This will force x enough that things do not overflow.

j.

ps. just a warning, seq is not entirely straightforward to use, so
while it works in this case, it may not always work for you. I think
there might be a wiki page somewhere that explains how to avoid space
leaks in greater detail, but I can't seem to find it.

Another solution that does not involve using seq would be to replace
the above line with these two lines:

nth i (0:xs) = if i < 0 then Empty else nth (i-1) xs
nth i (_:xs) = if i < 0 then Empty else nth (i-1) xs

In order to decide which case to use, the first element of the list
has to be fully evaluated -- so we don't get a huge thunk building
up. I don't think I have ever seen anyway take this approach in real
code -- but I thought it might help illuminate things a bit.

pps. I didn't explain why [1..1000000] works, but [1..] fails, because
I don't know :) It's a bit suprising to me...

j.




At Fri, 5 Jan 2007 20:17:33 -0500 (EST),
Brian Hurt wrote:
> 
> 
> My apologies for wasting bandwidth on what I'm sure is a stupid newbie 
> question.
> 
> Given:
> 
> -- Reimplementing the wheel here, I know
> 
> data Option a = Some a | Empty
>  	deriving (Eq,Ord,Show,Read)
> 
> nth 0 (x:xs) = Some x
> nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs
> nth i [] = Empty
> 
> That:
> 
> nth 1000000 [1..10000000]
> 
> returns the right answer, while:
> 
> nth 1000000 [1..]
> 
> blows stack.  Furthermore, given:
> 
> makelist i = i : (makelist (i-1))
> 
> Why is it that:
> nth 1000000 (makelist 1)
> 
> blows stack?  What are the rules for being tail recursive in Haskell?  I'm 
> an Ocaml programmer, so I'm familiar with this problem, I just don't see 
> the solution.  Some help would be appreciated.
> 
> Thanks in advance,
> Brian
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe