haskell - 比这更通用的 parfoldr

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

首先根据输入列表的数量将输入列表分解为分区
核心( 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

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

例如，

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

(-threaded 标志打开)

    $ ./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 提供了更好的运行时间。

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

最佳答案

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

关于haskell - 比这更通用的 parfoldr，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6801351/