[Haskell-cafe] Lazy evaluation and tail-recursion
rendel at informatik.uni-marburg.de
Wed Mar 16 19:19:48 CET 2011
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
data EvaluatedList a
= Cons a (List a)
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.
More information about the Haskell-Cafe