To Tail Recurse or Not - Part 2 (A follow up for Haskell)

In an earlier post, I had talked about tail recursion and tail call optimization and we saw that it really needs hard benchmarking before deciding to transform a body recursive call to a tail recursive one. The entire discussion was based on strict evaluation, where the arguments to a function are always evaluated completely before the function is applied. Languages like Haskell offer laziness as the default order of evaluation. Also called non-strict evaluation, in Haskell, arguments to a function are not evaluated unless they are actually used in the evaluation of the function body. In this post, we will see some of the non obvious impacts that lazy evaluation can have on tail recursive functions. And we conclude this post validating an earlier suggestion that I made on my preference to use combinators instead of bare recursion.

Here are the implementations of foldl and foldr in Haskell ..

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

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs



foldl is tail recursive, while foldr is not. But throw in Haskell's non strict evaluation strategy in the mix and we find some non-obvious consequences in using the supposedly optimized foldl against foldr.

In case of foldl, Haskell will defer the evaluation of the entire result till the end of the list is reached. And this can lead to a stack overflow if the final expression is big enough. Hence foldr, despite not being tail recursive is a better option in many cases. And Haskell also offers a strict version of foldl (fold') that forces the evaluation of the initial parameter before making the recursive call.

Here is an example of summing over a list, that uses accumulator based summing and tail recursion ..

sumList acc [] = acc
sumList acc (x:xs) = sumList (acc+x) xs


When I try ..

Main> print . sumList 0 . take 1000000 $ [1..]
*** Exception: stack overflow


It's tail recursive, but lazy evaluation keeps accumulating the result till the end of the list is reached, and ultimately results in a stack overflow.

Instead try the foldl' combinator ..

sumList’ xs = foldl’ (+) 0 xs


and you will be happy !!

Let us take a look at how exactly Haskell evaluates an expression lazily. Instead of evaluating a value directly, Haskell uses a machinery called *thunk* to abstract the computation of the expression. Thunks contain instructions to compute the value, which will be activated when the evaluation is forced. Let us consider the following snippet, which takes out every third element from the input list ..

thirds [] = []
thirds [x] = []
thirds (_:_:x:xs) = x : thirds xs


Consider the interesting recursive case above. Haskell produces a thunk that contains a list cons cell. The cons cell contains the element value (x) and another yet unevaluated thunk for the rest of the list. The function thirds is lazy and will consume only that part of the input which is required to produce the result. Hence if we request for the first element of the result list, it gets back instantly without evaluating the rest of the list. Hence if we compute

head $ thirds [1..10000000]


we get the first element 3 in constant time. Another important advantage of lazy evaluation is that Haskell can handle infinite data structures seamlessly. In the above example, we can change the invocation to

head $ thirds [1..]


and will get back 3 instantly and in constant time.

Now consider what happens if we implement the same function using tail recursion .

thirds_tc :: [Int] -> [Int] -> [Int]
thirds_tc acc [] = reverse acc
thirds_tc acc [x] = reverse acc
thirds_tc acc (_:_:x:xs) = thirds_tc (x:acc) xs


Nice and tail recursive .. but to get the first element the function takes O(n) time. Try .

head $ thirds_tc [] [1..10000000]


and compare the difference in time with the earlier implementation.

So, as we find, tail recursion is not a be-all and end-all with respect to optimization even in case of non strict languages like Haskell. And use combinators like foldl' or foldr depending on your application requirements. Combinators abstract away many of the language semantics and can make lots of high level optimizations that may not be obvious while programming with bare recursion.