I apologize if this is a bit off-topic -- I'm asking it here because if what I want to do is possible, it may only be possible with ghc extensions, as opposed to vanilla Haskell......
In many types of applications, it's common to have a loop which loops infinitely, of at least until some condition is met. For example, in C-like syntax:
for (;;;) { a = get_input(); if (a == GET_OUT) break; do_comthing(); }
You can paraphrase this in Haskell, in the IO monad, like this: loop = do { a <- get_input; if (a == gET_OUT) then return () else loop; } In GHC this won't grow any stack each time around the loop, even with optimisation off. It depends on the actual implementation of the IO monad, but I imagine the other Haskell implementations will also have this property. Cheers, Simon
Simon writes:
You can paraphrase this in Haskell, in the IO monad, like this:
loop = do { a <- get_input; if (a == gET_OUT) then return () else loop; }
In GHC this won't grow any stack each time around the loop, even with optimisation off. It depends on the actual implementation of the IO monad, but I imagine the other Haskell implementations will also have this property.
It's worth adding that Mark's initial code,
f a
| a == GET_OUT = a
| otherwise = f ( g a)
will also not grow the stack, on any decent Haskell implementation. Tail recursion is always implemented properly here - tail recursion simply means that the result of the function is the result of the recursive call to the function, i.e., no more computation need be done once the result of the recursive call is known.
http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?tail+recursion
Of course, laziness may well bite you and you may run out of *heap*, but that's another story for another evening!
--KW 8-)
--
Keith Wansbrough
On Tue, Nov 13, 2001 at 05:59:19PM +0000, Keith Wansbrough wrote:
It's worth adding that Mark's initial code,
f a | a == GET_OUT = a | otherwise = f ( g a)
will also not grow the stack, on any decent Haskell implementation. Tail recursion is always implemented properly here - tail recursion simply means that the result of the function is the result of the recursive call to the function, i.e., no more computation need be done once the result of the recursive call is known.
Yep, I've verified that the stack stays manageable. Thanks for the pointer to tail recursion -- it's nice to know *why* something works ;-)
Of course, laziness may well bite you and you may run out of *heap*, but that's another story for another evening!
Heap usage *is* something I've come up against before. Forcing strictness has done wonders, and ghc's profiling capabilities are invaluable for figuring out where the leaks may be happening (at least for someone who hasn't developed the intuition to see those things intuitively.
On Tue, Nov 13, 2001 at 05:02:54PM -0000, Simon Marlow wrote:
You can paraphrase this in Haskell, in the IO monad, like this:
loop = do { a <- get_input; if (a == gET_OUT) then return () else loop; }
I follow, but I've never seen brackets used in Haskell code. Are they included for clarity, or do they have syntactic value? Is this the same as loop = do a <- get_input if (a == GET_OUT) then return () else loop ? --Mark
participants (3)
-
Keith Wansbrough -
Mark Conway Wirt -
Simon Marlow