11

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

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 通常在小列表上调用，因此尝试并行计算地图似乎很有趣。这可以通过 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 的主体中更新这个布尔变量（我想你必须锁定和解锁它）。做这样的事情有什么建议吗？

4

2 回答 2

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

于 2017-03-02T20:23:05.140 回答
-1

你不能使用 State Monad 吗？更改功能f：

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

至：

f :: [a] -> State Bool [b]

您只需要通过列表的折叠来更新您的状态值，不是吗？不过，我不确定你是否可以将它与并行的东西一起应用。我对 Haskell 的了解有些有限。

于 2013-11-25T14:00:11.640 回答