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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe