(Different example, same efficiency in both cases.)
Revision as of 02:26, 29 June 2006
|Haskell Performance Resource|
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 function to compute the length of a list.
len :: [a] -> Int len  = 0 len (x:xs) = len xs + 1
Compile and run a simple program like the following:
main = putStrLn $ show $ len [1..200000]
Profiling the above, I found that it took 0.20 seconds to run. Increasing that number to 1000000 results in a stack overflow.
The above function seems to delegate most of the actual work to the recursive case. The only thing keeping it from being tail recursive is the requirement to increment the length of the remainder of the list.
We can move this increment step into an accumulating parameter. This is an extra parameter that allows us to carry information along in the computation.
len' :: [a] -> Int -> Int len'  acc = acc len' (x:xs) acc = len' xs (1 + acc)
Now the function is tail recursive. The accumulating parameter is returned in some form by the base case, and in the inductive case, we perform the step that prevented us from being truly tail recursive. We should provide a wrapper function that hides the detail of that accumulating parameter from users of the function.
len xs = len' xs 0
Running the above program with the new definition gives me a runtime of 0.02 seconds. What's more, increasing the upper limit of the list to one million doesn't overflow the stack!
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.