haskell - Haskell parMap 中的共享变量

Question

我有一个基本上执行以下操作的计算:

f :: [a] -> ([b],Bool)

这个函数其实可以写

f = foldr h ([],False) . map g
    where h (b,bool) (bs,boolSoFar) = (b:bs,bool || boolSoFar)

在哪里 g :: a -> (b,Bool)是一些需要大量时间的功能。 f 通常在小列表上调用，因此尝试并行计算 map 似乎很有趣。这可以通过 Control.Parallel.Strategies parMap 来完成。所以现在我们使用

f = foldr h ([],False) . parMap rseq g
    where h (b,bool) (bs,boolSoFar) = (b:bs, bool || boolSoFar)

这一切都很好。现在，您会注意到可以在 f 的第一个定义中执行顺序优化。 .即，我可以使用 map-fold fusion 将其编写为单个折叠，因此循环遍历列表。但是，这样我就失去了做并行的好处。

现在，有人可能会说，在 f 的第二个定义中，再次循环遍历列表并不是那么糟糕，所以为什么不这样做呢。我想我在想的是，如果 Haskell 有可变变量，那么可以在 map 的主体中更新这个 bool 变量(我想你必须锁定和解锁它)。做这样的事情有什么建议吗？

Answer 1

这实际上是在惰性写入器 Applicative 下的遍历，写入器状态为 Bool ，因为 (False, (||)) 形成一个幺半群。您还需要 unamb 包，因此您可以在 g 的任何并行调用第一次返回 True 时获取该值。

import Control.Parallel.Strategies
import Data.Unamb

newtype EvalWB a = EvalWB { runEvalWB :: Eval (a, Bool) }

instance Functor EvalWB where
  fmap f (EvalWB m) = EvalWB $ fmap (\ ~(a, b) -> (f a, b)) m

instance Applicative EvalWB where
  pure a = EvalWB $ pure (a, False)

  EvalWB mf <*> EvalWB ma = EvalWB $ (\ ~(f, bf) ~(a, ba) -> (f a, por bf ba)) <$> mf <*> ma

然后你有

f :: [a] -> ([b], Bool)
f l = runEval $ runEvalWB $ traverse (\a -> EvalWB $ rpar $ g a) l

这将并行传递整个列表，懒惰地累积值和标志。它使用 por 在第一个 True 返回时短路。