IO loops with tail call
Hello! I wrote a simple echo program which end up with input "q": echo = do str <- getLine if (str == "q") then return () else putStrLn str >> echo then I thought it is not tail call because if expressions return a value. (is it right?) So I changed a code: echo "q" = return () echo xs = do putStrLn xs xs' <- getLine echo xs' but Monad connections are too complicated so that I'm not sure it is tail call. Am I wrong? Thank you! -------------------------------------- Get the new Internet Explorer 8 optimized for Yahoo! JAPAN http://pr.mail.yahoo.co.jp/ie8/
On Sun, Nov 07, 2010 at 01:54:26AM +0900, Yasuyuki Ogawa wrote:
Hello!
I wrote a simple echo program which end up with input "q":
echo = do str <- getLine if (str == "q") then return () else putStrLn str >> echo
This is a tail call. Yes, if expressions return a value, but here nothing more is done with that value so the memory used by the current call to echo can be garbage collected once the recursive call is made. However, the real answer is: don't worry about it! Because of Haskell's lazy evaluation, the notion of "tail call" is not very important. And even if it were, you still shouldn't worry about it: just write your Haskell programs in the most natural, beautiful style you can think of. Maybe at some point down the road you will have to start worrying about optimization. But you should put it off as long as possible. -Brent
Hi Brent, (2010/11/07 4:26), Brent Yorgey wrote:
However, the real answer is: don't worry about it! Because of Haskell's lazy evaluation, the notion of "tail call" is not very important. And even if it were, you still shouldn't worry about it: just write your Haskell programs in the most natural, beautiful style you can think of. Maybe at some point down the road you will have to start worrying about optimization. But you should put it off as long as possible.
Thank you for your helpful advice. In fact, I was wondering how coding styles affect optimization! I'll forget it a while. -------------------------------------- Get the new Internet Explorer 8 optimized for Yahoo! JAPAN http://pr.mail.yahoo.co.jp/ie8/
Hi Yasuyuki,
Here is some resource Brent produced, why tail-recursion isn't that
important in haskell:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html
(http://www.haskell.org/haskellwiki/Tail_recursion)
I think it is nice to have some background (and it is pretty interesting).
Greets,
Edgar
On Sun, Nov 7, 2010 at 4:16 AM, Yasuyuki Ogawa
Hi Brent,
(2010/11/07 4:26), Brent Yorgey wrote:
However, the real answer is: don't worry about it! Because of Haskell's lazy evaluation, the notion of "tail call" is not very important. And even if it were, you still shouldn't worry about it: just write your Haskell programs in the most natural, beautiful style you can think of. Maybe at some point down the road you will have to start worrying about optimization. But you should put it off as long as possible.
Thank you for your helpful advice. In fact, I was wondering how coding styles affect optimization! I'll forget it a while.
-------------------------------------- Get the new Internet Explorer 8 optimized for Yahoo! JAPAN http://pr.mail.yahoo.co.jp/ie8/ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Hi Edgar, Thank you for interesting wiki pages! Roughly speaking, because of laziness, tail recursion is not always necessary, modulo cons but useful enough...or something like that? I'll study! -- Yasuyuki (2010/11/08 19:21), edgar klerks wrote:
Hi Yasuyuki,
Here is some resource Brent produced, why tail-recursion isn't that important in haskell:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html (http://www.haskell.org/haskellwiki/Tail_recursion)
I think it is nice to have some background (and it is pretty interesting).
Greets,
Edgar
-------------------------------------- Get the new Internet Explorer 8 optimized for Yahoo! JAPAN http://pr.mail.yahoo.co.jp/ie8/
Hi Yasuyuki,
I must admit, It is not clear to me. But I think a reference to the head of
the list is somehow used as an argument to the recursive function, which
adds the next value to the list. So that it is tail-recursive again. Or
something like that.
But I may also be completely off.
Greets,
Edgar
On Tue, Nov 9, 2010 at 1:17 PM, Yasuyuki Ogawa
Hi Edgar,
Thank you for interesting wiki pages! Roughly speaking, because of laziness, tail recursion is not always necessary, modulo cons but useful enough...or something like that? I'll study!
-- Yasuyuki
(2010/11/08 19:21), edgar klerks wrote:
Hi Yasuyuki,
Here is some resource Brent produced, why tail-recursion isn't that important in haskell:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html (http://www.haskell.org/haskellwiki/Tail_recursion)
I think it is nice to have some background (and it is pretty interesting).
Greets,
Edgar
-------------------------------------- Get the new Internet Explorer 8 optimized for Yahoo! JAPAN http://pr.mail.yahoo.co.jp/ie8/ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
On Wednesday 10 November 2010 18:25:37, edgar klerks wrote:
Hi Yasuyuki,
I must admit, It is not clear to me. But I think a reference to the head of the list is somehow used as an argument to the recursive function, which adds the next value to the list. So that it is tail-recursive again. Or something like that.
One point is that a tail-recursive function can't deliver anything until it has reached the end of the recursion, but laziness allows to deliver partial results before that (not always, however; sum :: [Int] -> Int needs to traverse the entire list, so there's a point where tail-recursion [with a strict accumulator] is the way to go). Consider map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs Not being tail-recursive, it can deliver its result (almost) immediately. The result is a constructor, (:), applied to two thunks. If the caller consumes the result appropriately, the computation can run in constant space. The important thing is that the recursive call is in a lazy argument position of the overall result, so the recursion may end prematurely if the caller doesn't need the full result. If you define map with a tail-recursive worker, the entire result list has to be constructed before the caller can inspect any of it, so it would require at least O(length list) space - particularly wasteful if the caller is "take k" for sufficiently small k and doesn't work at all on infinite lists. Tail-recursion has its uses in Haskell, but since Haskell's evaluation model is different from e.g. Lisp's, it's not so important. As a catch- phrase: "(non-tail-)recursion doesn't eat stack frames in Haskell".
But I may also be completely off.
Greets,
Edgar
Thanks for your clear explanation. I understand the role of laziness now.
On Wed, Nov 10, 2010 at 7:53 PM, Daniel Fischer
On Wednesday 10 November 2010 18:25:37, edgar klerks wrote:
Hi Yasuyuki,
I must admit, It is not clear to me. But I think a reference to the head of the list is somehow used as an argument to the recursive function, which adds the next value to the list. So that it is tail-recursive again. Or something like that.
One point is that a tail-recursive function can't deliver anything until it has reached the end of the recursion, but laziness allows to deliver partial results before that (not always, however; sum :: [Int] -> Int needs to traverse the entire list, so there's a point where tail-recursion [with a strict accumulator] is the way to go).
Consider
map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs
Not being tail-recursive, it can deliver its result (almost) immediately. The result is a constructor, (:), applied to two thunks. If the caller consumes the result appropriately, the computation can run in constant space. The important thing is that the recursive call is in a lazy argument position of the overall result, so the recursion may end prematurely if the caller doesn't need the full result.
If you define map with a tail-recursive worker, the entire result list has to be constructed before the caller can inspect any of it, so it would require at least O(length list) space - particularly wasteful if the caller is "take k" for sufficiently small k and doesn't work at all on infinite lists.
Tail-recursion has its uses in Haskell, but since Haskell's evaluation model is different from e.g. Lisp's, it's not so important. As a catch- phrase: "(non-tail-)recursion doesn't eat stack frames in Haskell".
But I may also be completely off.
Greets,
Edgar
participants (4)
-
Brent Yorgey -
Daniel Fischer -
edgar klerks -
Yasuyuki Ogawa