Beautiful folds in F# - Part 2
Tags: fsharp, dotnet, functional
Published: 2020-01-20 18:11:41

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:

```fsharp
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:

```fsharp
/// 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:

```fsharp
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:

```fsharp
// 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:

```fsharp
// 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:

```fsharp
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:

```fsharp
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`:

```fsharp
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:

```fsharp
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:

```fsharp
(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:

```fsharp
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`:

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

Our final computation is then defined as:

```fsharp
(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](https://dev.to/shimmer/beautiful-folds-in-f-part-3-applicatives-4d1b)