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
bhurt:
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..]
Now I'm really intrigued, since the standard list-index function also fails: Prelude> [1..] !! (10^6) *** Exception: stack overflow It's implemeeted roughly as: nth xs n | n < 0 = Nothing nth [] _ = Nothing nth (x:_) 0 = Just x nth (_:xs) n = xs `nth` (n-1) main = print $ [1..] `nth` (10^6) -- Don
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
At Fri, 05 Jan 2007 17:58:14 -0800, Jeremy Shaw wrote:
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), .. ]
I should clarify that this is the list that will be built by:
makelist i = i : (makelist (i-1))
[1..] will be building something like:
[ 1, succ 1, succ (succ 1), succ (succ (succ 1)), ...]
j.
On Fri, 5 Jan 2007, Jeremy Shaw wrote:
Hi,
In this case, the stack overflow you are seeing is due to laziness not tail recursion.
Aha. I knew it was something stupid.
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.
Actually, this makes sense to me. Recursively forcing lazy thunks is not tail recursive, it needs to allocate stack frames. So if a million-deep recursive thunk, forcing it is a problem.
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 This looks to be a typo, not sure if it's mine or yours. The definition I was playing with was (or should be):
nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs Brian
On Fri, 5 Jan 2007, Jeremy Shaw wrote:
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
Even better, if I define: nth 0 (x:_) = Just x nth i (_:xs) = if i < 0 then Nothing else nth (i-1) xs nth i [] = Nothing makelist i = i `seq` i : (makelist (i+1)) nth 10000000 (makelist 1) This works like a charm. Thanks. Brian
Am Samstag, 6. Januar 2007 05:12 schrieb Brian Hurt:
Even better, if I define:
nth 0 (x:_) = Just x nth i (_:xs) = if i < 0 then Nothing else nth (i-1) xs nth i [] = Nothing
makelist i = i `seq` i : (makelist (i+1))
nth 10000000 (makelist 1)
Hi Brian. i just like to mention another tricky solution: you can apply seq in such a way to the list, so that each element will be evaluated before advancing deeper into the list. ghci -fglasgow-exts -fbang-patterns Prelude> :t foldr foldr :: forall a b. (a -> b -> b) -> b -> [a] -> b Prelude> let strict = foldr (\x xs ->x `seq` (x:xs)) [] Prelude> let strict = foldr (\(!x) xs -> (x:xs)) [] -- using bang patterns instead, this is easier to read Prelude> let strict = foldr ((:) $!) [] -- or complete pointfree Prelude> let lazy = foldr ((:) $) [] Prelude> :t strict strict :: forall a. [a] -> [a] Prelude> lazy [1..] !! 1000000 *** Exception: stack overflow Prelude> strict [1..] !! 1000000 1000001 - marc
At Fri, 05 Jan 2007 20:59:16 -0800, Mike Gunter wrote:
pps. I didn't explain why [1..1000000] works, but [1..] fails, because I don't know :) It's a bit suprising to me...
With [1..1000000], the generated values have to be tested against 1000000 as you go. So, they get evaluated. In the [1..] case, they don't.
Ah, that makes a lot of sense. Thanks! j.
On 06/01/2007, at 12:58 PM, Jeremy Shaw wrote:
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.
Right. And to clarify, the reason is that the thunk is one big chain of applications of (-). Imagine what will happen when the topmost application is evaluated. Because (-) is strict in its arguments they must be evaluated before the minus can proceed. So the left and right arguments are evaluated. The left argument is itself an application of (-) and so on. The whole left branch eventually gets pushed onto the stack. Because the left branch is so long, the stack eventually overflows. This is one of those examples where optimistic evaluation would be a win. Cheers, Bernie.
On Fri, Jan 05, 2007 at 08:17:33PM -0500, 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)
My apologies if you knew this already, (I don't know whether your "Reimplementing the wheel" comment refers to this type or the "nth" function) but this is the Maybe data type in Prelude: data Maybe a = Nothing | Just a ...which is the same as yours, except it's spelled differently, is an instance of several handy classes (eg, Monad), and has a handful of helper functions predefined: http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Maybe.html Jason Creighton
On Fri, 5 Jan 2007, Jason Creighton wrote:
On Fri, Jan 05, 2007 at 08:17:33PM -0500, 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)
My apologies if you knew this already, (I don't know whether your "Reimplementing the wheel" comment refers to this type or the "nth" function) but this is the Maybe data type in Prelude:
data Maybe a = Nothing | Just a
Both, actually. I did the Option a definition to get some experience with defining symbolic data types, and probably should have removed it in my example.
...which is the same as yours, except it's spelled differently, is an instance of several handy classes (eg, Monad), and has a handful of helper functions predefined: http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Maybe.html
Thanks for the link. Brian
Brian Hurt wrote:
nth 0 (x:xs) = Some x nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs nth i [] = Empty [blows stack on large i]
As other people have pointed out, this is due to laziness. I'd write it like: nth 0 (x:_) = Some x nth i (_:xs) = of i < 0 then Empty else (nth $! i-1) xs nth _ [] = Empty where a general rule of thumb is always to replace (fun intexp) by (fun $! intexp) whenever intexp is just a trivial arithmetic expression that doesn't involve traversing (ie forcing of) any other data structure. Brian. -- http://www.metamilk.com
Brian Hulley wrote:
Brian Hurt wrote:
nth 0 (x:xs) = Some x nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs nth i [] = Empty [blows stack on large i]
As other people have pointed out, this is due to laziness. I'd write it like:
nth 0 (x:_) = Some x nth i (_:xs) = of i < 0 then Empty else (nth $! i-1) xs ^^^ -- oops!
nth _ [] = Empty
I think the above code would be more efficient written as: nth n xs = if n < 0 then Empty else nth' n xs where nth' 0 (x:_) = Some x nth' i (_:xs) = (nth' $! i - 1) xs nth' _ _ = Empty since the first 2 cases deal with every situation where we've got a non-empty list and an index >= 0 (so no need to keep checking that the index is >= 0 in the second case - instead the test can be moved outside the "loop") and there's no need to pattern match against [] in the last case because we already know this must be an empty list. (Though in general it's probably a good idea to make each pattern as independent as possible when writing a function so that if some cases of a function are later edited there's more chance of the compiler being able to lead you to errors via the "incomplete patterns" warning - hopefully the compiler can optimize out any redundant checks) Brian. -- http://www.metamilk.com
Brian Hulley wrote:
Brian Hulley wrote:
Brian Hurt wrote:
nth 0 (x:xs) = Some x nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs nth i [] = Empty [blows stack on large i]
As other people have pointed out, this is due to laziness. I'd write it like:
nth 0 (x:_) = Some x nth i (_:xs) = of i < 0 then Empty else (nth $! i-1) xs ^^^ -- oops!
nth _ [] = Empty
Actually I see I should have read Jeremy Shaw's answer more carefully before giving my own since I'd missed the point about the problem being with the list itself not the decrementing of (i) (which wouldn't be a problem since it is immediately forced on the next iteration by the comparison of i to 0). The answer therefore lies in the laziness of the makelist function which could be solved by: makelist i = i : (makelist $! i - 1) Jeremy Shaw wrote:
pps. I didn't explain why [1..1000000] works, but [1..] fails, because I don't know :) It's a bit suprising to me...
I think this might be because the code that produces the list [1..1000000] would have to be something like: produce n i = if i < n then i : produce n (i +1) else [] so each element of the list is now forced by the comparison with n, so even though the end of the list will be a thunk when 1000000 has not yet been reached, none of the elements are thunks. Anyway it was certainly not a "stupid" question - thanks for asking it. Best regards, Brian. -- http://www.metamilk.com
participants (8)
-
Bernie Pope -
Brian Hulley -
Brian Hurt -
dons＠cse.unsw.edu.au -
Jason Creighton -
Jeremy Shaw -
Marc A. Ziegert -
Mike Gunter