Tail recursion, should I use it in Haskell

Question

I know that tail recursion in Haskell is subject to some difficulties due to its being lazy. That is, is it sensible to use tail recursion in Haskell?

Answer 1

The answer, as usual with these big questions, is "it depends".

When you're programming in a lazy style, you can often get away with naive recursion, for example

 map f (x:xs) = f x : map f xs
 map _ []     = []

Is actually how map is defined in the standard libs. And this is good, since a tail recursive function yields the result generally can't be nicely lazy, a tail recursive map won't terminate if you did something like head . map (+1) $ [1..].

However, sometimes we don't want to be lazy. The classic example is when we're too lazy and start to build up thunks that we really just want evaluated, like when summing a list.

sum xs = someFold (+) 0 xs

Now since + is strict in it's arguments and associative, there's no reason to use foldr but foldl' is perfect, it's tail recursive and evaluates strictly which gives noticeable space improvements. The ' is important, in many tail recursive functions, there's an accumulator that's modified on each recursive step, foldl' will force it's evaulation which prevents our tail recursive function from being too lazy and building up thunks.

So the moral of the story, when you're programming lazily and producing lazy datastructures, tail recursion isn't as big a deal. But when you're programming strictly and using functions strict in both arguments, then tail recursion is very important for maintaining good performance.

Answer 2

Tail recursion isn't as straightforward or as big of a deal in Haskell as it is in strict languages. Usually, instead, you should aim to write productive functions. For instance, foldr is often productive

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

If the combining function f is able to produce a partial result lazily then whatever is consuming the results from foldr can demand them lazily as well. A typical example is "foldr identity"

foldr (:) [] [1,2,3]          -- "force" it once
1 : {{ foldr (:) [] [2,3] }}

where the {{...}} is a lazy thunk. If the calling context of this foldr is, say, head then we're done

head (foldr (:) [] [1,2,3])
head (1 : {{ foldr (:) [] [2,3] }})
1

However, if the f in foldr is strict then foldr can create linearly many calling frames

foldr (+) 0 [1,2,3]
1 + {{ foldr (+) 0 [2,3] }}           -- we know it's one more than *something*
1 + (2 + {{ foldr (+) 0 [3] }})       -- ...
1 + (2 + (3 + {{ foldr (+) 0 [] }}))
1 + (2 + (3 + 0))                     -- and now we can begin to compute
1 + (2 + 3)
1 + 5
6

While foldl' lets the strict combining function operate immediately

foldl' f z []     = z
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

where that seq noise forces Haskell to evaluate like this

foldl' (+) 0 [1,2,3]
foldl' (+) (1+0) [2,3]
foldl' (+) 1 [2,3]
foldl' (+) (1+2) [3]
foldl' (+) 3 [3]
foldl' (+) (3+3) []
foldl' (+) 6 []
6

Which looks a lot like a tail recursive call.

See the wiki for a bit more detail.