我是函数式编程的新手,我想知道是否存在某种形式模式/数据类型,其中1)我们用幺半群折叠/约简,2)运行一次函数以从约简后的值中获得一些摘要。例如,要获得数组的平均值,我们可以将其约简为一个[count, sum]
元组,然后在约简完成后,将总和除以计数。(将为空数组放大):
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
像这样的图案有名字吗?
2条答案
按热度按时间6vl6ewon1#
我得到的印象是,虽然这个问题被标记为 * typescript *,但其他语言的解决方案可能也是可以接受的。我可能错了,在这种情况下,我道歉,你可以简单地忽略答案,但我会用Haskell回答,但链接到我写的各种文章,其中有C#,F#和Haskell(重点是C#)的代码示例。
Haskell通常被认为是函数式编程的黄金标准,原因很多,我在这里就不一一介绍了...
一般来说,折叠或缩减的函数被命名为 * fold 、 reduce * 或类似的名称。像往常一样,C#中的函数被命名为Aggregate。对于列表/数组/有限序列,通常可以从左 * 或 * 右折叠,因此一些语言会提供名为 * foldLeft 、 foldRight * 或类似名称的函数。
Haskell称之为foldl和foldr。到目前为止,我还没有回答任何明确的问题,但我们正在接近。
现在让我们暂时忽略 * right fold *,而关注 * left fold *。
foldl
的实际Haskell类型比下面的类型更一般,但经过简化,类型如下所示:这里,
a
和b
是泛型类型(在TypeScript中通常表示为T
、U
、V
或类似的)。第一部分(b -> a -> b)
是一个函数,它与列表中的每个a
值一起使用。b
值是开始时的初始值。举个例子,假设你想把一个数字列表简化为这些数字的总和,虽然这个函数已经内置在大多数语言中(包括Haskell),但是我们可以从
foldl
中实现它,以便于教学:在Haskell中,可以将运算符作为函数传递,因此
(+)
只是普通的加法运算符,用0
初始化约简,然后将列表[3,7,2]
中的每个x
与累加值相加,最终得到结果12
。虽然
foldl
的一般类型包含 * 两个 * 泛型类型a
和b
,但没有什么可以阻止它们是相同的,在这种情况下,你有一个类型的函数,如下所示:看上去很有希望。
幺半群
如果我们对列表中的值有更多的了解,如果我们知道这些值是产生幺半群的集合的成员,会怎么样呢?
在这种情况下,我们可以使用幺正恒等式来开始,这就是上面表达式中
0
的作用,此外,我们还可以使用幺正"append"来累加一个运行总和,将每个值加到它上面。如何建模取决于语言。一些语言可能使用接口来建模幺半群,而Haskell使用类型类。基于类型系统的行为通常工作得很好,但对于幺半群,我们面临的问题是,对于某些类型,有无限多个可能的幺半群。例如,对于数字,你不能只谈论"数字幺半群",因为即使在这里,有无穷多个加法和乘法只是其中的两个。
在Haskell中,我们把值 Package 在新类型中以消除歧义。因此,一个'naked'
Integer
没有固有的幺半群性质,因为语言不知道程序员想要使用哪一个。如果我们想要加法幺半群,我们把数字 Package 在一个名为Sum
的类型中,现在我们可以使用幺半群<>
(* append *)运算符把它们加在一起:如您所见,结果是另一个
Sum
值,其中包含数字3
。您可以使用getSum
函数轻松地提取该值:然而,我不会一直这样做,只要知道这是可能的。
如果你有一个“裸”数的列表,你可以将它们Map到一个
Sum
值的列表:很抱歉我用了一种迂回的方式来处理这个问题,但是现在我们可以继续了,作为下一步,我们可以使用Haskell的
Monoid
类型类和Sum
示例来重写加法表达式:其中
mempty
是幺正恒等式,此处为Sum {getSum = 0}
。取一个幺半群的列表并将其简化为一个值是common enough,这是一个可重用的函数,在Haskell中称为mcconat,你可以进一步泛化它,并在每个支持迭代的数据结构上定义它,在这种情况下,你会得到一个简单称为fold的函数。
以下是使用
fold
"实现"的数字总和:到目前为止,我们讨论了如何对一系列数字求和,但在我们完成之前还有更多的挑战。
计数
我们如何计算列表中元素的数量?使用内置函数吗?
当然,我们可以这样做,但是如果我们只使用幺半群,而没有内置的长度函数呢?
我们可以使用另一个幺半群来计算值。本质上,计数只是意味着为你看到的每个值加上 * 1 *。这意味着加法的特殊化...
本质上,我们需要一个任意的列表,例如
并将每个值替换为
1
:如果我们这样做,我们就可以把所有的加在一起。
通过定义一个名为
count
的小辅助函数(令人惊讶的是,这个名字还没有被使用),这很容易做到:这是一个忽略(
_
)输入并总是返回Sum 1
的函数,这意味着我们可以用它来计算单个值:有多少个
42
值?1
。有多少个"foo"
字符串?1
。这也许微不足道,但这意味着我们有办法用一个特殊的“计数么半群”来替换列表中的每个值:
因为
Sum
是一个Monoid
示例,所以我们可以fold
它:如果我们有一个空列表呢?那也行:
这是因为
Sum
的幺正恒等式是Sum 0
。元组
我们如何折叠到一个元组的值,如OP计数和总和?
幸运的是,tuples of monoids are also monoids,我们现在有了一个可以计数的幺半群和一个可以相加的幺半群。下一步,就是把列表中的每个值转换成一个元组。
幸运的是,Haskell定义了一个&&& fanout操作符可以做到这一点:
结果是一个元组,其中第一个元素是我们的计数幺半群,第二个元素是标准加法幺半群。
这意味着我们有办法将每个“裸”数提升为这样的元组:
因为幺半群的元组是幺半群,我们也可以
fold
这个列表:如果你担心所有的 Package 器,我们可以很容易地打开数字,你可以使用标准的模式匹配,或者使用元组的Bifunctor特性:
记住,结果是一个数字的元组,而不是一个数字的列表。
分部
给定一个数组,我们如何划分它们呢?这是一个相当琐碎的问题,但我们还是要讨论一下。
OP需要中间结果
[count, sum]
,JavaScript/TypeScript(我认为)不区分列表和元组,Haskell区分,元组的大小在编译时是固定的,而列表可以有任何大小(长度)。到目前为止,我们有一个元组
(count, sum)
,我们想用sum
除以count
;也就是sum / count
。我们可以使用正规除法运算符,但是我们必须交换值。不用担心,Haskell也有交换功能:
很好,但是我们可以将
(12,3)
应用于除法运算符/
吗?不完全可以,因为Haskell函数和运算符是curried,所以我们需要解开它:和除法的情况一样,如果除数是
0
,这就不起作用了,但是我将把这个细节留到以后再讨论。组成
让我们总结一下:
fold
任何Foldable
数据结构包含幺正值。我们如何组成它们?
具体地说,让我们用这些函数中的每一个来构造一个函数:
如何组合它们,以便首先执行
countSum
,然后将其输出传递给avg
,这是标准的function composition:avg . countSum
。Haskell从右到左组合函数,因此此语法意味着:首先运行countSum
,然后运行avg
:总而言之,如果我对OP的理解正确,答案是:* 标准功能组成 *。
vzgqcmou2#
另一个答案的TL正确;DR(“函数组合",以防它被编辑掉),但对我来说,它的其余部分看起来并不像是这个问题的好答案。
对于提问者来说,解释一下为什么使用Typescript就能满足函数组合的要求可能会更好,所以这就是我要做的。我们可以将函数组合定义为高阶函数(与Haskell中的相同):
然后,我们可以仅使用
compose
来构建平均函数:(The类型Assert对于使用我能想到的最具限制性的类型进行类型检查是必要的;您可以内联
specificFold
和divideTuple
,但这样代码看起来会故意混淆。)这告诉我们,函数组合是一个包含我们要做的事情的一般概念,学习函数式编程通常是学习如何在同一个一般概念下有数量惊人的事物;如果函数组合足以表达你的问题,你应该注意到它很漂亮,然后就这样了,它 * 是 * 漂亮,我想它可能被称为deep,但是没有理由去想太多。
顺便说一下,我认为任何人都不应该在生产TS代码库中定义上面的
compose
。Typescript不是Haskell。泛型高阶函数的语法是痛苦的,所以你应该通过重复的函数调用来表达组合,就像你最初做的那样。没有什么能让你像Haskell那样表达幺半群的概念,所以我甚至不会尝试--事实上,我不认为我会写你的非常通用的函数;我只需要处理我之前的具体类型,然后继续我的一天。将你的原始代码(或者上面我的代码块中的混乱)与并考虑可读性。