Data.Sequence.Seq懶惰並行函數實例

Question

我需要012KB的Seq版本的包的並行（但是懶惰）版本。但包不會導出任何Seq數據構造函數。因此，我不能將它包裝在newtype中，並且直接爲newtype實施Functor。

我可以在不重寫整個包的情況下做到嗎？

Answer 1

你能做的最好的可能是序列splitAt成塊，fmap在每個塊，然後將作品追加重新走到一起。 Seq表示爲finger tree，所以它的底層結構並不是特別適合並行算法 - 如果按其自然結構分割它，相繼的線程將會變得越來越大。如果您想放棄它，可以從Data.Sequence源複製FingerTree類型的定義，並使用unsafeCoerce在它與Seq之間進行轉換。您可能需要將第一批Deep節點發送到一個線程，但是您必須仔細考慮其餘部分。手指樹可能離重量平衡很遠，主要是因爲3^n漸近地快於2^n;您需要考慮這些以平衡線程間的工作。

有至少兩個明智的方式來分割的順序，假設你使用splitAt：

1. 斯普利特這一切打破了之前的計算成線。如果你這樣做，你應該從左到右或從右到左分開它，因爲分割小塊比分割大塊更便宜，然後分割它們。您應該以類似的方式追加結果。

2. 在多個線程中遞歸地分割它。這可能是有意義的，如果你想要很多件或更多的潛在懶惰。拆分中間附近的列表並將每個片段發送到一個線程以進一步分割和處理。

有可能是更好的，使用目前用於實現zipWith（見GitHub的票我申請請求chunksOf）機械另一個分裂的做法，但我不知道你會得到一個巨大的好處這個應用程序。

您尋求的非嚴格行爲似乎不太可能一般工作。你可以讓它在很多或者特定的情況下工作，但我不太樂觀，你會找到一個完全一般的方法。

Answer 2

我找到了一個解決方案，但實際上效率並不高。

-- | 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