Performance/Accumulating parameter

Haskell Performance Resource Constructs: Data Types - Functions Overloading - FFI - Arrays Strings - Integers - I/O Floating point - Concurrency Modules - Monads Techniques: Strictness - Laziness Avoiding space leaks Accumulating parameter Implementation-Specific: GHC - nhc98 - Hugs Yhc - JHC

Accumulating Paramaters: Getting rid of the 'almost' in "almost tail recursive"

Often times you will write a recursive function which is almost tail recursive. Consider this naïve implementation of a reverse function.

 rev :: [a] -> [a]
 rev [] = []
 rev (x:xs) = rev xs ++ [x]

Compile and run a simple program like the following:

 main = putStrLn $ show $ rev [1..10000]

Profiling the above, I found that it took 13.86 seconds to run, allocating 1,202,138,892 bytes of memory! That rev function took over 99% of both the program's time and space.

Looking at the function, we see it is recursive. The base step handles the case of reversing an empty list. The inductive step reverses the tail of the list, and adds the first element of the list onto the end of the list. By adding an accumulating parameter, we can make this tail recursive.

 rev' :: [a] -> [a] -> [a]
 rev' [] acc = acc
 rev' (x:xs) acc = rev' xs (x:acc)

Here's how the new version works. acc is an accumulating parameter. The base case simply returns the accumulating parameter. The inductive step takes the head of the list and puts it on the front of the accumulator. Then it tail recurses with the tail of the list and the new accumulator value. In order to reverse a list, the accumulator should have an initial value of []. It's a good idea to provide a wrapper for functions written this way, so that the users don't have to deal with the accumulator.

 rev xs = rev' xs []

Profiling this new tail recursive reverse function yields impressive results. The run time of the program is now 0.02 seconds! The reversal operation takes an immeasurably small time, most of the time was occupied with constructing that list of numbers.

The real performance gain came from the tail recursive implementation. Accumulating parameters is merely a means to turn an almost tail recursive implementation into a tail recursive implementation. The pattern to apply this technique to are ones which involve a tail recursion and a cons step. This latter step is performed on the accumulator and then passed into the tail recursive step.