Hi,
Yves Parès wrote:
A question recently popped into my mind: does lazy evaluation reduce the
need to "proper" tail-recursion?
I mean, for instance :
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs
Here fmap is not tail-recursive, but thanks to the fact that operator (:) is
lazy, I think that it may still run in constant space/time, am I right?
In a sense, that definition of fmap is tail-recursive.
To see that, consider how a non-strict list could be encoded in a strict
language:
data EvaluatedList a
= Cons a (List a)
| Empty
type List a
= () -> EvaluatedList a
map :: (a -> b) -> (List a -> List b)
map f xs
= \_ -> case xs () of
Cons x xs -> Cons (f x) (\_ -> map f xs ())
Empty -> Empty
Here, the call to map is more visibly in tail position.
So I would say that in Haskell, tail-call optimization is just as
important as, for example, in Scheme. But tail positions are not defined
syntactically, but semantically, depending on the strictness properties
of the program.
Tillmann
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
