Functional programming pattern for performing a function once after fold/reduce?

Question

I'm new to functional programming and was wondering if there is any kind of formal pattern/data type where 1) we fold/reduce with a monoid, 2) run a function once to get some summary out of the reduced value. For example, to get the mean of an array, we could reduce into a [count, sum] tuple and then finally divide the sum by the count once the reduce is done. Here's my implementation in TypeScript (will blow up for empty array):

const reduceSummarize = <T, U, V>(
  array: T[],
  reducefn: (result: U, nextValue: T) => U,
  initialValue: U,
  afterfn: (result: U) => V
) => {
  return afterfn(array.reduce(reducefn, initialValue));
};

const incrementCountSum = (
  countSumTuple: [number, number],
  nextValue: number
): [number, number] => [countSumTuple[0] + 1, countSumTuple[1] + nextValue];

const tupleRatio = (tuple: [number, number]) => tuple[1] / tuple[0];

reduceSummarize([1, 2, 3, 4], incrementCountSum, [0, 0], tupleRatio) // 2.5

Does a pattern like this have a name?

Answer 1

TL;DR: function composition.

I'm getting the impression that, while this question is tagged typescript, solutions in other languages may be acceptable. I may be wrong, in which case I apologise and you can simply ignore the answer, but I'll answer with Haskell but link to various articles I've written which has code examples in C#, F#, and Haskell (with an emphasis on C#).

Haskell is often considered the gold standard for functional programming, for various reasons that I'm not going to cover here...

Generally, functions that fold or reduce are named fold, reduce, or something along those lines. The odd man out is, as usual, C# where it's called Aggregate. For a list/array/finite sequence you can typically fold from the left or the right, so some languages will provide functions called foldLeft, foldRight, or something to that effect.

Haskell calls these foldl and foldr. So far, I haven't answered any of the explicit questions, but we're getting there.

Let's forget right fold for now and instead concentrate on the left fold. The actual Haskell type of foldl is more general than the following, but simplified, the type is something like this:

(b -> a -> b) -> b -> [a] -> b

Here, a and b are generic types (in TypeScript typically denoted T, U, V, or similar). The first part (b -> a -> b) is a function which is used with every a value in the list. The b value is an initial value to get started.

As an example, say that you want to reduce a list of numbers to the sum of those numbers. While this function tends to be built into most languages (including Haskell), we can implement it from foldl for didactic purposes:

ghci> foldl (+) 0 [3,7,2]
12

In Haskell it's possible to pass operators around as functions, so (+) is just the normal addition operator. You initialise the reduction with 0 and then add each x in the list [3,7,2] to the accumulated value, finally arriving at the result 12.

While the general type of foldl involves two generic types a and b, nothing prevents them from being the same, in which case you have a function of a type like this:

(a -> a -> a) -> a -> [a] -> a

This looks promising.

Monoid

What if we knew something more about the values in the list? What if we knew that the values are members of a set that gives rise to a monoid?

In that case, we'd use monoidal identity to kick things off. That's the role of the 0 in the above expression. Furthermore, we'd use monoidal 'append' in order to accumulate a running sum, adding each of the values to it.

How you'd model that depends on the language. Some languages might use interfaces to model monoids, while Haskell uses type classes. Basing behaviour on the type system often works well, but with monoids we're faced with the problem that for some types there are infinitely many possible monoids. For example, for numbers, you can't just talk about 'the number monoid', because even here, there are infinitely many - addition and multiplication being just two of them.

In Haskell, we wrap values in new types to disambiguate. Thus, a 'naked' Integer has no inherent monoidal nature, because the language doesn't know which one the programmer wants to use. If we want the addition monoid, we wrap numbers in a type called Sum, and we can now add them together using the monoidal <> (append) operator:

ghci> Sum 1 <> Sum 2
Sum {getSum = 3}

As you can see, the result is another Sum value with the number 3 inside. You can easily extract the value with the getSum function:

ghci> getSum (Sum 1 <> Sum 2)
3

I'm not, however, going to consistently do that here. Just know that it's possible.

If you have a list of 'naked' numbers, you can map them to a list of Sum values:

ghci> fmap Sum [3,7,2]
[Sum {getSum = 3},Sum {getSum = 7},Sum {getSum = 2}]

I apologise for approaching the question in such a roundabout manner, but now we're ready to move on. As the next step, we can rewrite our addition expression using Haskell's Monoid type class and the Sum instance:

ghci> foldl (<>) mempty (fmap Sum [3,7,2])
Sum {getSum = 12}

where mempty is the monoidal identity, here Sum {getSum = 0}.

Taking a list of monoids and reducing it to a single value is common enough that it's a reusable function. In Haskell it's called mconcat. You can generalise it further and define it over every data structure that supports iteration, in which case you arrive at a function simply called fold.

Here's the sum of numbers 'implemented' with fold:

ghci> fold (fmap Sum [3,7,2])
Sum {getSum = 12}

So far, this covers how to sum a list of numbers, but there are more challenges before we're done.

Counting

How do we count the number of elements in a list? Use the built-in function for that?

Sure, we could do that, but what if we only had monoids to work with? And no built-in length function?

It's possible to count values using another monoid. Essentially, counting just means adding 1 for every value you see. This suggests a specialisation of addition...

Essentially, we want to take an arbitrary list like

[3,7,2]

and replace each value with 1:

[1,1,1]

If we did that, we could then add all the ones together.

That's easy to do by defining a little helper function called count (surprisingly enough not a name that's already taken):

count _ = Sum 1

This is a function that ignores (_) the input and always returns Sum 1. This means that we can use it to count single values:

ghci> count 42
Sum {getSum = 1}
ghci> count "foo"
Sum {getSum = 1}

How many 42 values are there? 1. How many "foo" strings are there? 1.

Trivial, perhaps, but this means that we have a way to replace each value in a list with a special 'counting monoid':

ghci> fmap count [3,7,2]
[Sum {getSum = 1},Sum {getSum = 1},Sum {getSum = 1}]

Since Sum is a Monoid instance, it follows that we can fold it:

ghci> fold (fmap count [3,7,2])
Sum {getSum = 3}

What if we have an empty list? That works, too:

ghci> fold (fmap count [])
Sum {getSum = 0}

This works because the monoidal identity of Sum is Sum 0.

Tuples

How do we fold to a tuple of values, like the OPs count and sum?

Fortunately, tuples of monoids are also monoids, and we now have a monoid that can count, and one that can add. The next step, then, is to turn each value in a list into a tuple.

Fortunately, Haskell defines a &&& fanout operator that can do this:

ghci> (count &&& Sum) 3
(Sum {getSum = 1},Sum {getSum = 3})

The result is a tuple where the first element is our 'counting monoid', and the second one is the standard addition monoid.

This means that we have a way to elevate each 'naked' number to such a tuple:

ghci> fmap (count &&& Sum) [3,7,2]
[(Sum {getSum = 1},Sum {getSum = 3}),
 (Sum {getSum = 1},Sum {getSum = 7}),
 (Sum {getSum = 1},Sum {getSum = 2})]

Since tuples of monoids are monoids, we can fold this list as well:

ghci> fold (fmap (count &&& Sum) [3,7,2])
(Sum {getSum = 3},Sum {getSum = 12})

If you're worried about all the wrappers, we can easily unwrap the numbers. You could use standard pattern matching, or use the Bifunctor nature of tuples:

ghci> bimap getSum getSum (fold (fmap (count &&& Sum) [3,7,2]))
(3,12)

The result, mind, is a tuple of numbers, not a list of numbers.

Division

Given a tuple of numbers, how do we divide them? This is fairly trivial, but let's still go over it.

The OP wanted the intermediary result [count, sum], and while JavaScript/TypeScript doesn't (I think) distinguish between lists and tuples, Haskell does. A tuple's size is fixed at compile time, whereas a list can have any size (length).

So far we have a tuple (count, sum) and we want to divide sum by count; i.e. sum / count. We can use the normal division operator for this, but we have to swap the values around.

No worries, Haskell has a swap function too:

ghci> swap (3,12)
(12,3)

Great, but can we apply (12,3) to the division operator /? Not quite, because Haskell functions and operators are curried, so we need to uncurry it:

ghci> uncurry (/) (swap (3,12))
4.0

As is always the case with division, this is not going to work if the divisor is 0, but I'll leave that detail for another time.

Composition

Let's summarise:

• We have a way to fold any Foldable data structure that contains monoidal values.
• We have a way to further produce a value from the result of the first step.

How do we compose them?

Specifically, let's make a function out of each of these:

countSum xs = bimap getSum getSum (fold (fmap (count &&& Sum) xs))
avg tpl = uncurry (/) (swap tpl)

How do you compose them so that first you execute countSum and then you pass the output from that to avg. That's standard function composition: avg . countSum. Haskell composes functions from right to left, so this syntax means: first run countSum and then avg:

ghci> (avg . countSum) [3,7,2]
4.0

To conclude, if I understand the OP right, the answer is: standard function composition.