Wednesday January 27th 2016

Edition 002

Running titles and
accumulators with F#

by Isaac Abraham

Consultant at Compositional I.T.

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.

Managing accumulation through recursion

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 form = [ "W"; "L"; "L"; "D"; "W"; "W"; "L"; "D" ]
let convertToPoints = function | "W" -> 3 | "D" -> 1 | _ -> 0

We want to end up with a “running total” of points based on this input set i.e. a list of cumulative points for e.g. charting purposes, something like this:
[0; 3; 3; 3; 4; 7; 10; 10; 11]

We might start with a recursive function.

let getRunningTotalRec data =
    let rec getRunningTotalRec' runningTotal results =
        match results with
        | [] -> runningTotal |> List.rev
        | result :: remainder ->
            let result = (result |> convertToPoints) + runningTotal.Head
            getRunningTotalRec' (result :: runningTotal) remainder
    data |> getRunningTotalRec' [ 0 ]

// Get running total
form |> getRunningTotalRec

This works, but isn’t necessarily the easiest code to understand: –
– Recursion is often difficult to reason about
– We have to manually maintain the output i.e. the running total list
– We also need to manually reverse the output at the end

Collection functions to the rescue

Luckily, F# has some handy functions in the collections module that can simplify this. We can firstly look to port our code over to the fold function: –

let rec getRunningTotalFold results =
    ([ 0 ], results)
    ||> List.fold(fun runningTotal result ->
        let result = (result |> convertToPoints) + runningTotal.Head
        result :: runningTotal)
    |> List.rev

// Get running total
form |> getRunningTotalFold

Fold can be thought of as a generalised solution for many problems as it maintains the issue of state tracking across multiple calls without you needing to resort to recursive. So whilst we still have to manage the list and reverse it here, we don’t need a nested recursive function here, nor do we have to supply the “remainder” of the list to the next call – fold does that for us.
But there’s a more succinct way to encapsulate this “accumulate a growing output list from a source list”, which is the scan function. Scan behaves like Fold, but instead of returning just the accumulated final state, it returns all intermediate states as well. Using scan, we can simplify our code to just this: –

let rec getRunningTotalScan results =
    (0, results)
    ||> List.scan(fun runningTotal result ->
        (result |> convertToPoints) + runningTotal)

// Get running total
form |> getRunningTotalScan

Here, we don’t even need to worry about maintaining the list as scan handles that for us. In this case, we simply return the next item in the running total, which is then passed to the next iteration. We don’t need to manage the list, or reverse it at the end – scan does all of that for us.

Conclusion

Managing state and accumulation can be easily handled through the collection modules without resorting to recursion. We can use the standard fold function, which outputs any arbitrary state, and will suffice for most cases. However, if we’re trying to output some state which is itself a list, you may find that scan is a better fit.

The F# Gazette

Relax and enjoy a curated selection of the best F# content straight to your inbox.

Including:
  • F# news round-up
  • Interviews with industry professionals
  • Guest articles from F# experts
  • Latest F# jobs
  • F# tools, tips, tutorials and more.