提问者:小点点

用于在折叠/缩小后执行一次函数的函数式编程模式?


我是函数式编程的新手,我想知道是否有任何形式的模式/数据类型: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

像这样的图案有名字吗?


共1个答案

匿名用户

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}

有多少421。有多少“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,这是行不通的,但我将把这个细节留待下次讨论。

让我们总结一下:

    < li >我们有一种方法可以< code>fold任何< code>Foldable包含单值的数据结构。 < li >我们有办法从第一步的结果中进一步得出一个值。

我们如何构成它们?

具体来说,让我们从以下每一项中创建一个函数:

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,答案是:标准函数组合。