Working with running totals in F#

This post is an expanded version of February’s F# Gazette.

A common issue that developers that come from an OO background struggle with is how to effectively create accumulations over sequences of data without resorting to mutable state in an effective and succinct style.

Let’s start with a fictional set of results for a sports team, and a function to convert from the outcome to a points earned: –

let results = [ "W"; "L"; "L"; "D"; "W"; "W"; "L"; "D" ]
let convertToPoints = function | "W" -> 3 | "D" -> 1 | _ -> 0

We would like to graphically show the form of the team by accumulating the points earned over the series: –

So the question is really, how can we easily go from a series of singular results to one that maintains a running total of all the results previously as well? Let’s look at some alternatives that you might come up with.

Managing accumulation with mutation

The implementation that you might initially consider doing is one which uses a mutable variable to track the running total.

	let calculateFormMutable results =
	let output = ResizeArray [ 0 ]
	for result in results do
	output.Add((result |> convertToPoints) + output.[output.Count – 1])
	output |> Seq.toList

view raw

RunningTotals1.fs

hosted with ❤ by GitHub

This code is not terrible – it’s not that hard to infer its meaning, particuarly if you come from an imperative background. And although this code doesn’t use the mutable keyword anywhere, it’s still of course mutating the output collection through the call to .Add(). So because we’re functional programmers and we’ve been told that mutation is the spawn of satan, we have to find another way around this. Let’s try recursion – that’s usually a good trick.

Managing accumulation with recursion

	let calculateFormRec results =
	let rec calculateFormRec' output results =
	match results, output with
	| [], _ -> output |> List.rev
	| result :: results, output ->
	let result = (result |> convertToPoints) + output.Head
	calculateFormRec' (result :: output) results
	results |> calculateFormRec' [ 0 ]

view raw

RunningTotals2.fs

hosted with ❤ by GitHub

Ehhhhh. I’m not fond of this solution. I find it hard to reason about recursion sometimes, and this is a good example – I need to think about the “end case” of the recursive function; the code doesn’t look particularly nice. We have to manually manage the output list, and remember to reverse it at the end (because in F#, it’s more efficient to add to the head than tail of a list) etc. etc. But at least we got rid of that mutable variable, which is all important, right?

Improving readability through higher order functions

This sort of dogmatic approach is guaranteed to turn people off to FP. Yes, mutation is best avoided (although in a case like this I would argue it’s not that dangerous as the mutable state is short lived – just a few lines of code) but I would argue that in this case, the cost of the recursive version in terms of readability is too high. So we can improve this by using the fold() function that exists in the collection libraries (I’ve put type annotations in for illustrative purposes, but they’re not necessary).

	let calculateFormFold results =
	([ 0 ], results)
	||> List.fold(fun (output:int list) result ->
	let result = (result |> convertToPoints) + output.Head
	result :: output)
	|> List.rev

view raw

RunningTotals3.fs

hosted with ❤ by GitHub

fold() is nice! It generalises the problem of managing state for us across iterations of a collection, so we don’t have to pattern match or manually pass items into a recursive function. This code is certainly less than the recursive version, and once you know how fold works, it’s much easier to reason about. So we start with a list of [ 0 ], and then manually calculate the next item in the list by manually adding the head of the list with the next result we’re passed by fold(), and then pushing that answer onto the head of the list: –

[0], W - add 3 points.
[3; 0], L - add 0 points.
[3; 3; 0], L - add 0 points.
[3; 3; 3; 0], D - add 1 points.
[4; 3; 3; 3; 0], W - add 3 points.
[7; 4; 3; 3; 3; 0], W - add 3 points.
[10; 7; 4; 3; 3; 3; 0], L - add 0 points.
[10; 10; 7; 4; 3; 3; 3; 0], D - add 1 points.
val it : int list = [0; 3; 3; 3; 4; 7; 10; 10; 11]

However, we’re still having to manually maintain the output list ourselves and then reverse it with that ugly List.rev at the end.

Using higher-level folds

So it turns out that there’s a derivative, constrained version of fold() that is designed for exactly what we need – generating output lists based on accumulations – and it’s called scan(). Scan works exactly like fold, except it generates a list automatically based on the result of each iteration. Here’s the code: –

	let calculateFormScan results =
	(0, results)
	||> List.scan(fun (runningTotal:int) result -> (result |> convertToPoints) + runningTotal)

view raw

RunningTotals4.fs

hosted with ❤ by GitHub

That’s it. In this version, we don’t need to manage state across calls, just like fold – but we also don’t need to generate a list either – that’s done by scan as well! In addition, we don’t need to reverse the list – again, this is taken care for us. The same sort of logging as above now yields the following: –

Current form is 0, result is W - add 3 points.
Current form is 3, result is L - add 0 points.
Current form is 3, result is L - add 0 points.
Current form is 3, result is D - add 1 points.
Current form is 4, result is W - add 3 points.
Current form is 7, result is W - add 3 points.
Current form is 10, result is L - add 0 points.
Current form is 10, result is D - add 1 points.
val it : int list = [0; 3; 3; 3; 4; 7; 10; 10; 11]

Notice that this time, we never actually see the output list within each iteration – instead we’re just given the current running total.

Taking it even further

If you want to be one of the cool kids you can reorder the transformations so that you can make the code even more succinct: –

	let calculateFormScan results =
	(0, results |> List.map convertToPoints)
	||> List.scan (+)

view raw

RunningTotals5.fs

hosted with ❤ by GitHub

And this can be simplified further still by taking advantage of curried functions as: –

let calculateFormScan = List.map convertToPoints >> List.scan (+) 0

view raw

RunningTotals6.fs

hosted with ❤ by GitHub

Conclusion

I daresay that you might not necessarily want to go as far as this last version, depending on your experience with currying and composition in F#, but you can see that by delegating the “boilerplate” of iteration with state, and outputting a running total, we can reduce even the mutating version to just: –

• our original function to go from W | D | L -> points
• two higher order functions that we compose together
• an addition operator
• a starting state of 0

No mutation, for loops, recursion or list manipulation.

And just to come full circle – I believe that many of the accumulation functions within the collections library in FSharp.Core (include fold()) actually use mutable variables!