haskell - 比这更通用的 parfoldr

Question

我的目标是有一个并行的 foldr 功能。起初，似乎
相当直接地实现，这就是我的想法:

首先根据输入列表的数量将输入列表分解为分区
核心 (numCapabilities)。然后将 foldr 应用于每个分区，这
将导致每个分区的折叠值列表。然后做一个
foldr 再次在该列表上以获得最终值。

    listChunkSize = numCapabilities

    chunk n [] = []
    chunk n xs = ys : chunk n zs
      where (ys,zs) = splitAt n xs

    parfoldr f z [] = z
    parfoldr f z xs = res
      where
            parts = chunk listChunkSize xs
            partsRs = map (foldr f z) parts `using` parList rdeepseq
            res = foldr f z partsRs

上面的代码不起作用，因为显然定义
文件夹， (a -> b -> b) -> b -> [a] -> b , 意味着输入列表
类型(嗯，可以)不同于累加器和结果类型。

例如，

1) foldr (+) 0 [1..10] => 列表类型 = 累加器类型(整数)

2) foldr (\i acc -> (i>5) && acc) True [1..10] => 列表类型(整数)!
= 累加器类型 (Bool)

所以，看看我上面的代码， map 会生成一个 b 类型的列表。
然后将其作为参数传递给第二个文件夹。但是第二个
foldr 接受类型列表 a .所以，那是行不通的。

一个丑陋的解决方案是为
parfoldr，例如 parfoldr :: (NFData a) => (a -> a -> a) -> a -> [a] -> a
这将起作用，但它并不完全等同于 foldr。例子
上面的 1 就可以了，但不是示例 2。
所以，问题 1 是:如何定义 parfoldr 以具有相同的类型签名
作为文件夹？

比较2折:

    input = [1..1000000]
    seqfold = foldr (+) 0
    parfold = parfoldr (+) 0

我明白了。双核机器上的时间:
(无线程标志)

    $ ./test
    seqfold: 4.99s
    parfold: 25.16s

(-线程标志打开)

    $ ./test
    seqfold: 5.32s
    parfold: 25.55s
    $ ./test +RTS -N1
    seqfold: 5.32s
    parfold: 25.53s
    $ ./test +RTS -N2
    seqfold: 3.48s
    parfold: 3.68s
    $ ./test +RTS -N3
    seqfold: 3.57s
    parfold: 2.36s
    $ ./test +RTS -N4
    seqfold: 3.03s
    parfold: 1.70s

从这些测量中观察到:

当核心数量增加时，foldr 似乎会降低运行时间。
这是为什么？

parfold 为 N => 3 提供更好的运行时间。

任何改进的建议和想法表示赞赏:)

Answer 1

foldr通常不可并行化，因为它的接口(interface)允许顺序依赖。为了能够以您描述的方式重新排列计算，您需要将自己限制为具有标识元素的关联运算符。这被称为 monoid ，而您实现的基本上是并行的 mconcat .