在折叠/归约后执行一次函数的函数式编程模式？

Question

我是函数式编程的新手，想知道是否存在任何形式的正式模式/数据类型，其中 1）我们用幺半群折叠/减少，2）运行一次函数以从减少的值中获取一些摘要。例如，为了获得数组的平均值，我们可以归约为一个[count, sum]元组，然后在归约完成后将总和除以计数。这是我在 TypeScript 中的实现（空数组会爆炸）：

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

像这样的图案有名字吗？

Answer 1

TL;DR：函数组合。

我的印象是，虽然这个问题被标记为typescript，但其他语言的解决方案可能是可以接受的。我可能是错的，在这种情况下，我道歉，你可以忽略答案，但我会用 Haskell 回答，但链接到我写的各种文章，其中包含 C#、F# 和 Haskell 的代码示例（重点是C＃）。

Haskell 通常被认为是函数式编程的黄金标准，出于各种原因，我不会在这里讨论......

一般来说，折叠或归约的函数被命名为fold、reduce或类似的名称。像往常一样，奇怪的是 C#，它被称为Aggregate。对于列表/数组/有限序列，您通常可以从左侧或右侧折叠，因此某些语言将提供称为FoldLeft、FoldRight或类似效果的函数。

Haskell 称这些为foldl和foldr。到目前为止，我还没有回答任何明确的问题，但我们已经做到了。

现在让我们忘记右折叠，而是专注于左折叠。实际的 Haskell 类型foldl比下面的更通用，但经过简化，类型是这样的：

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

这里，a和b是泛型类型（在 TypeScript 中通常表示为T、U、V或类似的）。第一部分是与列表中的(b -> a -> b)每个值一起使用的函数。a该b值是开始时的初始值。

举个例子，假设您想要将数字列表减少到这些数字的总和。虽然这个函数往往内置于大多数语言（包括 Haskell）中，但我们可以出于foldl教学目的来实现它：

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

在 Haskell 中，可以将运算符作为函数传递，因此(+)只是普通的加法运算符。您可以使用 初始化归约0，然后将x列表中的每个值添加[3,7,2]到累加值中，最终得到结果12。

虽然 的通用类型foldl涉及两个泛型类型a和b，但没有什么可以阻止它们相同，在这种情况下，您将拥有如下类型的函数：

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

这看起来很有希望。

幺半群

如果我们对列表中的值了解更多怎么办？如果我们知道这些值是产生幺半群的集合的成员怎么办？

在这种情况下，我们将使用幺半群恒等式来开始。0这就是上面表达式中the 的作用。此外，我们将使用幺半群“追加”来累积运行总和，将每个值添加到其中。

如何建模取决于语言。某些语言可能使用接口来建模幺半群，而 Haskell 使用类型类。基于类型系统的行为通常效果很好，但对于幺半群，我们面临着这样的问题：对于某些类型，可能有无限多个可能的幺半群。例如，对于数字，你不能只谈论“数字幺半群”，因为即使在这里，也有无限多个 - 加法和乘法只是其中的两个。

在 Haskell 中，我们将值包装在新类型中以消除歧义。因此，“裸”Integer没有固有的幺半群性质，因为该语言不知道程序员想要使用哪一种。如果我们想要加法幺半群，我们将数字包装在名为 的类型中，现在我们可以使用幺半群（追加Sum）运算符将它们加在一起：<>

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

正如你所看到的，结果是另一个Sum值，里面有数字3。您可以使用以下函数轻松提取值getSum：

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

然而，我不会一直在这里这样做。只要知道这是可能的。

如果您有“裸”数字列表，则可以将它们映射到Sum值列表：

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

我很抱歉以如此迂回的方式处理这个问题，但现在我们准备好继续前进。下一步，我们可以使用 Haskell 的Monoid类型类和Sum实例重写我们的加法表达式：

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

这里 是幺mempty半群恒等式Sum {getSum = 0}。

获取幺半群列表并将其减少为单个值是很常见的，因此它是一个可重用的函数。在 Haskell 中，它称为mconcat。您可以进一步概括它，并在支持迭代的每个数据结构上定义它，在这种情况下，您将得到一个简单地称为Fold 的函数。

这是“实现”的数字总和fold：

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

到目前为止，这涵盖了如何对数字列表求和，但在完成之前还有更多挑战。

数数

我们如何计算列表中元素的数量？使用内置函数吗？

当然，我们可以做到这一点，但是如果我们只使用幺半群呢？并且没有内置长度函数？

可以使用另一个幺半群来计算值。本质上，计数只是意味着为您看到的每个值加1。这表明加法的专业化......

本质上，我们想要获取一个任意列表，例如

[3,7,2]

并将每个值替换为1：

[1,1,1]

如果我们这样做了，我们就可以将所有的加在一起。

count这很容易通过定义一个名为（令人惊讶的是不是已经使用的名称）的小辅助函数来实现：

count _ = Sum 1

这是一个忽略 ( _) 输入并始终返回的函数Sum 1。这意味着我们可以用它来计算单个值：

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

42有多少个值？1。"foo"有多少根弦？1。

也许很简单，但这意味着我们有办法用特殊的“计数幺半群”替换列表中的每个值：

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

由于Sum是一个Monoid实例，因此我们可以fold：

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

如果我们有一个空列表怎么办？这也有效：

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

这是有效的，因为 的幺半群恒等式Sum是Sum 0。

元组

我们如何折叠为值的元组，例如 OP 计数和总和？

幸运的是，幺半群的元组也是幺半群，我们现在有了一个可以计数的幺半群，以及一个可以加法的幺半群。那么下一步是将列表中的每个值转换为元组。

幸运的是，Haskell 定义了一个&&&扇出运算符可以做到这一点：

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

结果是一个元组，其中第一个元素是我们的“计数幺半群”，第二个元素是标准加法幺半群。

这意味着我们有办法将每个“裸”数字提升为这样的元组：

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})]

由于幺半群的元组是幺半群，我们fold也可以列出这个列表：

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

如果您担心所有包装纸，我们可以轻松拆开数字。您可以使用标准模式匹配，或使用元组的Bifunctor性质：

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

请注意，结果是一个数字元组，而不是一个数字列表。

分配

给定一个数字元组，我们如何划分它们？这是相当微不足道的，但我们仍然回顾一下。

OP 想要中间结果[count, sum]，虽然 JavaScript/TypeScript 不（我认为）区分列表和元组，但 Haskell 会区分。元组的大小在编译时是固定的，而列表可以具有任意大小（长度）。

到目前为止，我们有一个元组(count, sum)，我们想sum除以count；IE sum / count。为此，我们可以使用普通的除法运算符，但我们必须交换值。

不用担心，Haskell 也有交换功能：

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

很好，但是我们可以申请(12,3)除法运算符/吗？不完全是，因为 Haskell 函数和运算符是柯里化的，所以我们需要将其取消柯里化：

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

与除法的情况一样，如果除数是 ，则此方法将不起作用0，但我将在下次再讨论该细节。

作品

我们总结一下：

• 我们有办法处理fold任何Foldable包含幺半群值的数据结构。
• 我们有办法从第一步的结果进一步产生一个值。

我们如何组合它们？

具体来说，让我们为每个函数创建一个函数：

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

如何组合它们，以便首先执行countSum，然后将输出传递给avg. 这是标准函数组合：avg . countSum。Haskell 从右到左组合函数，因此此语法意味着：先运行countSum，然后avg：

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

总而言之，如果我理解OP正确的话，答案是：标准函数组合。

Answer 2

另一个答案有一个正确的 TL;DR （“函数组合”，以防它被编辑掉），但对我来说，它的其余部分看起来并不是这个问题的一个很好的答案。

对于提问者来说，使用 Typescript 解释为什么函数组合就足够了，这可能会更好，所以这就是我要做的。我们可以将函数组合定义为高阶函数（与 Haskell 中相同）：

function compose<A,B,C>(f1: (val: B) => C, f2: (val: A) => B): (val: A) => C {
    return val => f1(f2(val));
}

然后我们可以仅使用以下函数构建平均函数compose：

const specificFold = (arr: number[]) => arr.reduce(([sum, count], elt) => [sum + elt, ++count] as [number, number], [0, 0] as [number, number]);
const divideTuple = ([a, b]: [number, number]) => a / b;

console.log(compose(divideTuple, specificFold)([1, 2, 3, 4])) // 2.5

（类型断言对于使用我能想到的最严格的类型进行类型检查是必要的；您可以内联specificFoldand divideTuple，但随后代码开始看起来故意混淆。）

这告诉我们，函数组合是一个通用概念，它包含了我们想要做的事情。学习函数式编程通常是为了了解大量令人惊讶的事物如何属于同一个一般概念；如果函数组合足以表达你的问题，你应该只是注意到这很漂亮，然后就不用管它了。很漂亮！我想这可以称为深度。但没有理由进一步考虑它。

顺便说一句，我认为任何人都不应该compose在生产 TS 代码库中定义上述内容。Typescript 不是 Haskell。通用高阶函数的语法很痛苦，因此您应该像最初那样通过重复函数调用来表达组合。没有什么可以让你像 Haskell 那样表达幺半群的概念，所以我什至不会尝试——事实上，我认为我根本不会编写你的非常通用的函数；我只是用我之前的具体类型做事，然后继续我的一天。将您的原始代码（或上面我的代码块中的混乱）与

function average(array: number[]): number {
   let total = array.reduce((a, b) => a + b);
   return total / array.length;
}

并考虑可读性。