Tail recursion and accumulators

The accumulator shape

The recursion of the last lesson keeps a frame per element, because the work after the call needs the result of the call. An accumulator turns that around: the partial answer travels down as an argument, and the recursive call is the whole right-hand side, so nothing is left to do on the way back.

sumList :: [Int] -> Int sumList [] = 0 sumList (x : xs) = x + sumList xs sumAcc :: [Int] -> Int sumAcc xs = go 0 xs where go acc [] = acc go acc (y : ys) = go (acc + y) ys

The second version is longer and, for a list of ten million elements, it is the one that finishes. go is the loop body: the accumulator acc is the loop variable, the list is the counter, and go (acc + y) ys is the tail call. The call is in tail position, so the frame of the current call can be reused instead of kept.

A go helper

The helper is called go by convention, and it lives in a where block so that the public function keeps its simple signature. go takes one more argument than the public function and that argument is the accumulator; the public function supplies the starting value.

module Main (main) where sumAcc :: [Int] -> Int sumAcc = go 0 where go acc [] = acc go acc (y : ys) = go (acc + y) ys countLong :: [String] -> Int countLong = go 0 where go acc [] = acc go acc (w : ws) = go (if length w > 3 then acc + 1 else acc) ws main :: IO () main = do print (sumAcc [1, 2, 3, 4]) print (countLong ["a", "four", "seven", "it"])

ghc -Wall -O1 -o accum accum.hs
./accum

10
2

Both functions are written as f = go start, which leaves the list argument implicit and is the shape the Prelude uses for foldl. The second one shows that the accumulator does not have to be a number: it is whatever the loop carries, here a count. Two words are longer than three letters, so the answer is 2.

Why the accumulator is still lazy

In a strict language, go (acc + y) ys would add immediately and the accumulator would be a number at every step. In Haskell the argument is not evaluated at the call: acc + y is passed as an unevaluated expression, a thunk, and the addition happens only when something needs the value.

So go 0 [1, 2, 3] builds ((0 + 1) + 2) + 3 and evaluates it at the end, when the result is printed. The stack of calls is small, because each frame is reused; the chain of thunks is not, and it grows with the list. For a sum the chain is one addition per element, which is cheap, but the same shape with a list accumulator (go (acc ++ [y]) ys) is quadratic for the reason the lesson on lists gave.

seq forces the step

seq takes two values and returns the second, after forcing the first to weak head normal form: enough to know its outermost constructor. Put it before the recursive call and the accumulator is added at every step instead of at the end:

module Main (main) where sumLazy :: [Int] -> Int sumLazy = go 0 where go acc [] = acc go acc (y : ys) = go (acc + y) ys sumStrict :: [Int] -> Int sumStrict = go 0 where go acc [] = acc go acc (y : ys) = let acc' = acc + y in acc' `seq` go acc' ys main :: IO () main = do print (sumLazy [1 .. 10]) print (sumStrict [1 .. 10])

ghc -Wall -O1 -o strict strict.hs
./strict

55
55

The two lines are the same because the answer is the same; the difference is in space, not in output, and it shows on a list long enough for the thunk chain to matter. The strict version is what foldl' does, and the lesson on folds uses it: the prime marks the strict fold, and the reason it exists is exactly this seq.

The rule that follows: an accumulator is only an optimisation of space when the step forces it. A lazy accumulator fixes the stack and can still build a large structure, so the two questions are separate, and both have the same answer in the standard library: foldl' for a strict accumulator, the plain recursion for a lazy one.

Exercises

  1. Rewrite myLength from the last lesson with an accumulator and compare the two definitions.
  2. Write myReverse with an accumulator and explain why it is linear, while the version with ++ was not.
  3. Add seq to the accumulator of countLong and say whether the output changes.
  4. Print sumStrict [1 .. 100000] and sumLazy [1 .. 100000]; both answer, and only the space differs. Explain where the difference is.
  5. Write a go helper that carries a tuple of two accumulators, for the count and the sum of a list.
  6. Explain in one sentence why foldl' has a prime in its name.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What makes a recursive call a tail call?

    Answer

    Its result is returned directly, with no work after it

    A call in tail position is the whole right-hand side, so the frame of the caller is no longer needed.

  2. What does sumAcc [1, 2, 3, 4] print?

    Answer

    10

    The accumulator starts at 0 and adds each element in turn.

  3. Why is sumList (x : xs) = x + sumList xs not a tail call?

    Answer

    The addition needs the result of the call, so the frame stays

    The work after the call means the caller cannot return until the call returns, so one frame per element is kept.

  4. What does go (acc + y) ys pass to the next call in a lazy language?

    Answer

    An unevaluated expression, a thunk

    Arguments are evaluated on demand, so acc + y is passed as a thunk and forced later.

  5. What does seq do?

    Answer

    It forces its first argument to weak head normal form and returns the second

    seq a b evaluates a enough to know its outer constructor, then yields b.

  6. What does this program print? module Main (main) where sumAcc :: [Int] -> Int sumAcc = go 0 where go acc [] = acc go acc (y : ys) = go (acc + y) ys main :: IO () main = print (sumAcc [1, 2, 3, 4])

    Answer

    10

    The accumulator adds 1, 2, 3 and 4 to zero and returns 10.

  7. What does an accumulator replace in a recursive function?

    Answer

    The work that would be done after the recursive call

    The partial answer travels down instead of being combined on the way back, which is what makes the call a tail call.

  8. What does foldl' have that foldl does not?

    Answer

    A strict accumulator, forced with seq at every step

    The prime marks the strict version, which forces the accumulator so the thunk chain does not grow.

  9. What does this program print? module Main (main) where countLong :: [String] -> Int countLong = go 0 where go acc [] = acc go acc (w : ws) = go (if length w > 3 then acc + 1 else acc) ws main :: IO () main = print (countLong ["a", "four", "seven", "it"])

    Answer

    2

    four and seven are longer than three letters, so the accumulator ends at 2.

  10. Does a tail-recursive accumulator automatically use constant space in Haskell?

    Answer

    No: the calls are cheap, but a lazy accumulator still builds thunks

    Tail calls fix the call stack, and laziness can still build an unevaluated chain, which seq or a strict fold removes.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev