Beautiful folds in F# - Part 2

When we left off, we had created a mechanism for applying multiple arbitrary functions to a sequence while enumerating the sequence only once. The only problem is that the result is a nest of tuples that we'd like to flatten out.

Extractor functions

To make this work, we need a final step in the process that transforms the completed accumulator into whatever form the caller would like. Each of our primitive computations will continue to return its completed accumulator unchanged, so let's make this explicit by specifying the id function (id x = x) in the tuple that defines the computation:

let composableSum =
    (fun acc item -> acc + item),
    0,
    id   // new

let composableLength =
    (fun acc item -> acc + 1),
    0,
    id   // new

let composableMin =
    (fun acc item -> min acc item),
    Int32.MaxValue,
    id   // new

let composableMax =
    (fun acc item -> max acc item),
    Int32.MinValue,
    id   // new

Now we need to modify the compose function to take these "extractor" functions into account:

/// Creates a new computation that's composed of the two given computations.
let compose (step1, init1, extract1) (step2, init2, extract2) =
    let step (acc1, acc2) item =
        step1 acc1 item, step2 acc2 item
    let init = init1, init2
    let extract (acc1, acc2) =   // new
        let result2 = extract2 acc2
        extract1 acc1 result2
    step, init, extract

Let's walk through the new extract function carefully. The input to this function contains the completed accumulators of the two computations we're combining, acc1 and acc2. First we extract the result of the right-hand computation by applying its extractor function, as normal:

let result2 = extract2 acc2

The next line is the key to the entire process, so make sure it makes sense to you. The "obvious" thing to do is to apply the left-hand computation's extractor to its completed accumulator in the same way:

// WRONG - doesn't help
let result1 = extract1 acc1

However, this would leave us right back where we started, with two separate values (result1 and result2) that haven't been combined meaningfully. What if we instead assume that the left-hand extractor actually takes two inputs and knows how to combine them in whatever way is desired by the caller:

// RIGHT!
extract1 acc1 result2

Note what we're passing to this extractor: the final result of the right-hand computation (obtained by extract2 acc2) with the completed accumulator of the left-hand computation (acc1).

Composable combiners

This seems promising, but it assumes that the left-hand computation contains, in its "extractor", a function that takes the results of two computations and knows how to combine them. Our toMean function, as an example, is such a function:

let toMean (sum : int) (length : int) =
    float sum / float length

But to create a computation, we also need to specify a "step" function and initial value:

let composableToMean =
    (* step function? *),
    (* initial value? *),
    (* something that supplies "toMean" *)

Strangely, it doesn't matter much what we do here, as long as the extract function supplies toMean to compose, so let's create the simplest computation we can think of that the compiler will accept: a step function that always answers the unit value () regardless of its input. This means that we can also use () as the initial value. The extract function will then ignore the final accumulator, which will always be (), and simply return toMean:

let composableToMean =
    (fun () item -> ()),
    (),
    (fun () -> toMean)

You can think of this value as a setup that has to be in this form in order to prepare for the rest of the computation. Note that the type of the extractor is unit -> int -> int -> float, so it's actually a function that takes three arguments. It ignores the first one and sends the other two to toMean. Now we can compose and run our computation as follows:

let comp = composableToMean <*> composableSum <*> composableLength
run comp <| unrepeatable [ 1 .. 10 ]

The result is 5.5, as desired, but let's rewind a bit and think about what's going on when compose has to combine the completed accumulator of composableToMean with the completed accumulator of composableSum. First it applies composableSum's extractor (which is just id) to composableSum's completed accumulator (which is 55), producing 55. Next it invokes composableToMean's extractor with two parameters. The first is composableToMean's completed accumulator, which is just () and the second is the result of composableSum's computation, which we now know is 55. So we have something like this:

(fun () -> toMean) () 55

The first argument is consumed and ignored, and the second becomes a partial function application, toMean 55, which is itself a function that takes an argument (the length of the sequence) and returns the actual mean. This final function application occurs during the second invocation of compose.

This approach can be used to create arbitrary computations with a final step that combines the result of each component however desired. A single argument to the "combiner" function is supplied by each component, as we just saw.

For example, let's say that we wanted to again compute sum, length, min, and max in a single pass and combine them into a custom record type:

let createRecord sum length min max =
    {|
        Sum = sum
        Length = length
        Min = min
        Max = max
    |}

Let's create a helper function that turns any custom "combiner" function into a computation definition, just like we did for toMean:

/// Creates a composable version of the given function.
let composableCombiner combiner =
    (fun () item -> ()),
    (),
    (fun () -> combiner)

Our final computation is then defined as:

(composableCombiner createRecord)
    <*> composableSum
    <*> composableLength
    <*> composableMin
    <*> composableMax

I'm going to pause here again and follow up soon with a final installment that wraps up the idea of "beautiful folds". If you're still with me, thanks for reading!

Now available: Beautiful folds in F# - Part 3: Applicatives