Using Scans to Accumulate

In last week's article we talked about how fold is one of the fundamental for-loop functions you'll want to use in Haskell. It relies on a folding function, which incorporates each new list item into a result value. There's one potential drawback though: you won't get any intermediate results, at least without some effort. Sometimes, you want to know what the "result" value was each step of the way.

This is where "scan" comes in. Let's start with a C++ example for accumulated sums:

std::vector<int> addWithSums(const std::vector<int>& inputs) {
  std::vector<int> results = {0};
  int total = 0;
  for (int i = 0; i < inputs.size(); ++i) {
    total += inputs[i];
    results.push_back(total);  
  }
  return results;
}

Let's consider a simple folding sum solution in Haskell:

sum :: [Int] -> Int
sum = foldl (+) 0

We could adapt this solution to give intermediate results. But it would be a little bit tricky. Instead of using (+) by itself as our folding function, we have to make a custom function that will store the list of accumulated values. In order to make it efficient, we'll also have to accumulate it in reverse and add an extra step at the end.

accumulatedSum :: [Int] -> [Int]
accumulatedSum inputs = reverse (foldl foldingFunc [0] inputs)
  where
    foldingFunc :: [Int] -> Int -> [Int]
    foldingFunc prev x = x + head prev : prev

However, we can instead perform this job with the idea of a "scan". There are scan functions corresponding to the fold functions, so we have scanl, scanr, and scanl'.

scanl :: (b -> a -> b) -> b -> [a] -> [b]

scanl' :: (b -> a -> b) -> b -> [a] -> [b]

scanr :: (a -> b -> b) -> b -> [a] -> [b]

Let's focus on scanl. Once again, I'll re-write the type signatures to be more clear with "items" and "results".

scanl :: (result -> item -> result) -> result -> [item] -> [result]

This is almost identical to foldl, except that the final result is a list of results, rather than a single result. And it does exactly what you would expect! Each time it calculates a result value in the folding function (scanning function?) it will include this in a list at the end. This makes it much easier for us to write our accumulated sum function!

accumulatedSum :: [Int] -> [Int]
accumulatedSum inputs = scanl (+) 0 inputs

...

>> scanl (+) 0 [5, 3, 8, 11]
[0, 5, 8, 16, 27]

As a curiosity, you can use this pattern to provide an infinite list of all the triangle numbers:

triangleNumbers :: [Int]
triangleNumbers = scanl' (+) 0 [1..]

…

>> triangleNumbers !! 4
10
>> triangleNumbers !! 7
28

Next week we'll be back with more loop alternatives! In the meantime, you should subscribe to our newsletter so you can stay up to date with the latest news!