Recursion with Accumulators | CodeSignal Learn

Recursion with Accumulators | CodeSignal Learn

Introduction to the Accumulator Pattern

In our previous lesson, we learned how to use plain recursion to process lists item by item. With plain recursion, a function calls itself until it reaches a base case, and then it builds up the final result step by step on the way back up. However, in many programs, it is helpful to keep track of a "running result" as we move forward through the data. If you have ever written a loop in another programming language where you updated a variable at each step, you already know why this is useful. In Haskell, we do not have loops or variables that we can update. Instead, we use a concept called an accumulator . An accumulator is simply an extra parameter that we pass to our recursive function. It carries our running total (or running structure) through each step of the recursion. To use an accumulator cleanly, we follow a standard Haskell pattern: We write a top-level wrapper function to provide a " starting seed " (like starting a total at 0). We write a helper function inside a where block (traditionally named go) that does the actual recursive work and updates the accumulator . This beginner version demonstrates the accumulator shape. For very large lists, Haskell programmers often use strict accumulation to avoid building delayed work, and we will discuss that later. Let's look at how we can build functions using this pattern.

Example 1: Summing a List (sumList)

We will start by rewriting a function to sum a list of integers, but this time we will use an accumulator . First, we define our top-level function. It takes a list of integers and returns an integer. Inside, it immediately calls a helper function named go, passing 0 as the starting value of our running total, along with the list xs . Haskell sumList :: [Int] -> Int sumList xs = go 0 xs Next, we need to define go . We use a where block to attach go directly to sumList so that it stays neatly hidden as an internal helper. go will take two parameters: our accumulator (an Int) and our list (a [Int]). Haskell sumList :: [Int] -> Int sumList xs = go 0 xs where go :: Int -> [Int] -> Int Now, let's add our base case to go . When the list is empty [], it means we have finished looking at all the numbers. Unlike plain recursion where an empty list might return 0, here our final answer is already stored in our accumulator . So, we simply return the accumulator acc . Haskell sumList :: [Int] -> Int sumList xs = go 0 xs where go :: Int -> [Int] -> Int go acc [] = acc Finally, we write the recursive case. When the list has a head y and a tail ys, we call go again. This time, we update the accumulator by adding the current item y to it (acc + y), and we pass the rest of the list ys to continue the process. Here is the complete code, including a main function to print the result: Haskell sumList :: [Int] -> Int sumList xs = go 0 xs where go :: Int -> [Int] -> Int go acc [] = acc go acc (y:ys) = go (acc + y) ys main :: IO () main = print (sumList [1, 2, 3, 4]) When you run this code, it will output: text 10 Notice how 0 becomes 1, then 3, then 6, and finally 10 as the accumulator is passed forward through each recursive call.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Example 2: Reversing a List (reverseList)

Accumulators are not just for calculating numbers; they are extremely powerful for building new data structures. Let's see how we can use an accumulator to reverse the order of items in a list. We start with our top-level wrapper. Our starting seed this time is an empty list [], because that is how our "running list" should initially start. Haskell reverseList :: [Int] -> [Int] reverseList xs = go [] xs Next, we set up go in a where block. Notice that our accumulator is now a list of integers [Int] . If we reach the end of our input list, we return the accumulated list. Haskell reverseList :: [Int] -> [Int] reverseList xs = go [] xs where go :: [Int] -> [Int] -> [Int] go acc [] = acc For the recursive step, we match on (y:ys) . To reverse the list, we take the current item y and attach it to the front of our accumulator list using the cons operator (:) . Then, we recurse on ys . Haskell reverseList :: [Int] -> [Int] reverseList xs = go [] xs where go :: [Int] -> [Int] -> [Int] go acc [] = acc go acc (y:ys) = go (y : acc) ys main :: IO () main = print (reverseList [1, 2, 3, 4]) The output of this code will be: text [4,3,2,1] Because we take the first item of the original list and push it into our accumulator, the first item ends up at the very bottom of the new list. As we move forward, the list is naturally built backwards!

Example 3: Counting Elements (countList)

Let's reinforce this pattern with one final, fresh example: counting how many items are in a list. Our wrapper function looks very similar to sumList . We start our running count at 0 . Haskell countList :: [Int] -> Int countList xs = go 0 xs Inside our where block, the base case also looks familiar. If the list is empty, we return the running count acc . Haskell countList :: [Int] -> Int countList xs = go 0 xs where go :: Int -> [Int] -> Int go acc [] = acc For the recursive case, we do not actually need to know the value of the current item; we only care that an item exists. As a reminder from our first lesson, we can use the wildcard_to ignore the head value. For every item we encounter, we simply add 1 to the accumulator . Here is the complete function: Haskell countList :: [Int] -> Int countList xs = go 0 xs where go :: Int -> [Int] -> Int go acc [] = acc go acc (_:ys) = go (acc + 1) ys main :: IO () main = print (countList [10, 20, 30, 40, 50]) The output here will be: text 5 By passing acc + 1 into each recursive step, we successfully count the items without ever needing a traditional loop.