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 is 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
Top comments (0)