Data.Sequence.Seq 惰性并行 Functor 实例

Question

我需要 Seq from Data.Sequence 包的 fmap 并行（但懒惰）版本。但是包不导出任何 Seq 数据构造函数。所以我不能只将它包装在 newtype 中并直接为 newtype.

实现 Functor

我可以不用重写整个包吗？

Answer 1

我找到了解决办法，但实际上效率不高。

-- | A combination of 'parTraversable' and 'fmap', encapsulating a common pattern:
--
-- > parFmap strat f = withStrategy (parTraversable strat) . fmap f
--
parFmap         :: Traversable t => Strategy b -> (a -> b) -> t a -> t b
parFmap strat f = (`using` parTraversable strat) . fmap f

-- | Parallel version of '<$>'
(<$|>) :: Traversable t =>  (a -> b) -> t a -> t b
(<$|>) = parFmap rpar

Answer 2

你能做的最好的事情可能是 splitAt 将序列分成块，fmap 遍历每个块，然后将这些块重新组合在一起。 Seq 表示为 finger tree，因此它的底层结构并不是特别适合并行算法——如果您按其自然结构将其拆分，连续的线程将得到越来越大的块。如果您想试一试，可以从 Data.Sequence 源中复制 FingerTree 类型的定义，并使用 unsafeCoerce 在它和 Seq 之间进行转换。您可能希望将前几个 Deep 节点发送到一个线程，但您必须非常仔细地考虑其余部分。手指树可能与权重平衡相去甚远，主要是因为 3^n 比 2^n 渐近增长得更快；您需要考虑到这一点以平衡线程之间的工作。

假设您使用 splitAt:

，至少有两种拆分序列的明智方法

在将计算分解为线程之前将其全部拆分。如果你这样做，你应该从左到右或从右到左拆分它，因为拆分小块比拆分大块然后再拆分更便宜。您应该以类似的方式附加结果。
在多个线程中递归拆分它。如果您想要很多块或更多潜在的懒惰，这可能是有道理的。在靠近中间的位置拆分列表，并将每个部分发送到线程以进一步拆分和处理。

还有另一种拆分方法可能更好，使用当前用于实现 zipWith 的机制（请参阅我提交的请求 chunksOf 的 GitHub 票），但我没有知道你会在这个应用程序中获得巨大的好处。

您寻求的非严格行为通常不太可能奏效。您可能可以在许多或大多数特定情况下使用它，但我不太乐观地认为您会找到一种完全通用的方法。

Data.Sequence.Seq 惰性并行 Functor 实例

Data.Sequence.Seq lazy parallel Functor instance

parallel-processing

haskell

lazy-evaluation

finger-tree