我是函数式编程的新手,我想知道是否有任何形式的模式/数据类型:1)我们使用幺半群进行折叠/缩减,2)运行一次函数以从缩减的值中得到一些摘要。例如,为了得到一个数组的平均值,我们可以将其归约为一个<code>[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
像这样的图案有名字吗?
TL;DR:功能构成。
我得到的印象是,虽然这个问题被标记为typescript,但其他语言的解决方案可能是可以接受的。我可能错了,在这种情况下,我道歉,你可以忽略这个答案,但我会用Haskell回答,但链接到我写的各种文章,这些文章有C#、F#和Haskell(重点是C#)的代码示例。
Haskell经常被认为是函数式编程的黄金标准,因为各种原因,我在这里不打算讨论。。。
通常,折叠或减少的函数被命名为折叠、减少或类似的东西。像往常一样,奇怪的人是C#,它被称为聚合。对于列表/数组/有限序列,您通常可以从左侧或右侧折叠,因此某些语言将提供称为foldLeft,foldRight或类似内容的函数。
Haskell称这些为foldl和foldr。到目前为止,我还没有回答任何明确的问题,但我们正在努力。
让我们暂时忘记右折叠,而是专注于左折叠。< code>foldl的实际Haskell类型比以下类型更通用,但经过简化,类型如下所示:
(b -> a -> b) -> b -> [a] -> b
这里,< code>a和< code>b是泛型类型(在TypeScript中通常表示为< code>T 、< code>U 、< code>V或类似的类型)。第一部分<代码>(b -
例如,假设您要将数字列表简化为这些数字的总和。虽然这个函数倾向于内置到大多数语言(包括 Haskell)中,但我们可以从 foldl
实现它以用于教学目的:
ghci> foldl (+) 0 [3,7,2]
12
在Haskell中,可以将运算符作为函数传递,因此()
只是普通的加法运算符。你用 0
初始化归约,然后将列表 [3,7,2]
中的每个 x
添加到累积值,最后得到结果 12
。
虽然< code>foldl的一般类型包含两个泛型类型< code>a和< code>b,但是没有什么可以阻止它们是相同的,在这种情况下,您有一个这样类型的函数:
(a -> a -> a) -> a -> [a] -> a
这看起来很有希望。
如果我们对列表中的值了解更多呢?如果我们知道这些值是产生幺半群的集合的成员呢?
在这种情况下,我们将使用幺半恒等式来启动事情。这就是 0
在上述表达式中的作用。此外,我们将使用幺半“追加”来累积一个运行总和,将每个值添加到其中。
如何建模取决于语言。一些语言可能使用接口来建模幺半群,而Haskell使用类型类。将行为建立在类型系统上通常很好,但是对于幺半群,我们面临的问题是对于某些类型有无限多种可能的幺半群。例如,对于数字,你不能只谈论“数字幺半群”,因为即使在这里,也有无限多——加法和乘法只是其中的两个。
在 Haskell 中,我们将值包装在新类型中以消除歧义。因此,“裸”整数
没有固有的幺半性质,因为语言不知道程序员想要使用哪一个。如果我们想要加法幺半群,我们将数字包装在一个名为 Sum
的类型中,我们现在可以使用幺半群将它们相加
ghci> Sum 1 <> Sum 2
Sum {getSum = 3}
如您所见,结果是另一个< code>Sum值,其中包含数字< code>3。您可以使用< code>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
这是一个忽略(_
)输入并始终返回Sum1
的函数。这意味着我们可以使用它来计算单个值:
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}]
由于< code>Sum是< code>Monoid实例,因此我们可以< code>fold它:
ghci> fold (fmap count [3,7,2])
Sum {getSum = 3}
如果我们有一个空列表呢?这也行得通:
ghci> fold (fmap count [])
Sum {getSum = 0}
这是因为< code>Sum的幺半群身份是< code>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})]
由于幺半群的元组是幺半群,我们也可以<code>折叠</code>这个列表:
ghci> fold (fmap (count &&& Sum) [3,7,2])
(Sum {getSum = 3},Sum {getSum = 12})
如果你担心所有的包装纸,我们可以很容易地打开数字。您可以使用标准的模式匹配,或者使用元组的双功能特性:
ghci> bimap getSum getSum (fold (fmap (count &&& Sum) [3,7,2]))
(3,12)
记住,结果是数字的元组,而不是数字的列表。
给定一组数字,我们如何划分它们?这是相当微不足道的,但让我们继续讨论它。
OP需要中间结果[count, sum]
,虽然JavaScript/TypeScript不(我认为)区分列表和元组,但Haskell可以。元组的大小在编译时是固定的,而列表可以有任何大小(长度)。
到目前为止,我们有一个元组(count,sum)
,我们希望将sum
除以count
;即sum/count
。我们可以使用正规除法运算符,但我们必须交换值。
不用担心,Haskell也有一个交换功能:
ghci> swap (3,12)
(12,3)
太好了,但是我们可以将(12,3)
应用于除法运算符/
吗?不完全是,因为 Haskell 函数和运算符是柯里化的,所以我们需要取消它:
ghci> uncurry (/) (swap (3,12))
4.0
与除法的情况一样,如果除数是0
,这是行不通的,但我将把这个细节留待下次讨论。
让我们总结一下:
我们如何构成它们?
具体来说,让我们从以下每一项中创建一个函数:
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,答案是:标准函数组合。