Haskell的推测性并行执行

Question

我正在考虑为我正在尝试解决的一个问题利用并行性。该问题大致如下：给定输入（一系列点），找到最佳输出（由这些点组成的最大三角形，最长线等）。在序列中有3种不同的“形状”，但我只对其中得分最高的那个感兴趣（通常是某种“长度”乘以系数的形式）。我们将这些形状称为S1、S2、S3。

我有两种不同的算法来解决S1 - 'S1a'的时间复杂度为O(n²)，而'S1b'的表现大多更好，但最坏情况下约为O(n⁴)。

第一个问题：是否有一种简单的方法可以并行运行S1a和S1b，使用先完成的算法并停止另一个算法？据我所读的文档，这可以使用一些forkIO编程并在获得结果时终止线程来实现 - 只是询问是否有更简单的方法？

第二个问题 - 更棘手：我是这样调用优化函数的：

optimize valueOfSx input

valueOfSx是针对每个形状具体的，并返回一个“分数”（或得分的猜测），以确定可能的解决方案。优化调用此函数以找到最佳解决方案。我感兴趣的是：

s1 = optimize valueOfS1 input
s2 = optimize valueOfS2 input
s3 = optimize valueOfS3 input
<- maximum [s1,s2,s3]

然而，如果我知道S1的结果，我可以丢弃所有比它更小的解决方案，如果不存在更好的解决方案，则使s2和s3更快地收敛（或者至少丢弃最差的解决方案，从而更节省空间）。我现在正在做的是：

zeroOn threshold f = decide .f
    where decide x = if (x < threshold) then 0 else x
s1 = optimize valueOfS1 input
s2 = optimize (zeroOn s1 valueOfS2) input
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input

问题是：我能否并行运行S2和S3，以便先完成的线程会更新在另一个线程中运行的分数函数的“threshold”参数？类似于以下方式：

threshold = 0
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3))
update threshold from firstSolution
wait for second solution

- ondra

Answer 1

最终，任何解决方案都将在幕后使用ForkIO，因为您希望多个事务并行发生。即使是Conal的unamb也是这样实现的。

对于后者，您可能需要一个更复杂的monad，它会批量处理一段时间，然后偶尔检查一个MVar以获取单调发布的改进值，但是交错（在一个线程内）的最简单答案就是编写一个Partiality monad。

data Partial a = Return a | Partial (Partial a)

instance Monad Partial where
    return = Return
    Return a >>= f = f a
    Partial m >>= f = Partial (m >>= k)


run :: Partial a -> a
run (Partial m) = run m
run (Return a) = a

race :: Partial a -> Partial a -> Partial a
race (Return a) _ = a
race _ (Return b) = b
race (Partial m) (Partial n) = race m n

yield :: Partial ()
yield = Partial (Return ())

通过适当的MonadFix实例来处理递归或自由地添加“yield”调用，您可以在Partial monad中执行这两个操作并进行比赛以获得确定性结果。

但在实际应用中，如果您想充分利用并行处理，则需要定期更新和检查某种“improving”MVar。

类似以下内容（随意编写，抱歉，没有编译器方便！）：

import Control.Concurrent.MVar (newMVar, readMVar)
import Control.Parallel.Strategies (using, parList)
import GHC.IOBase (unsafeDupablePerformIO, unsafePerformIO)

diag x = (x,x)

parMax :: (Bounded a, Ord a) => [a] -> a
parMax xs = unsafePerformIO $ do
    threshold <- newMVar minBound
    let optimize x = unsafeDupablePerformIO $
        x `seq` modifyMVar threshold (return . diag . max x)
    return . maximum $ map optimize xs `using` parList

当然，这应该能够被重写以支持任何幂等可交换的单子，不仅仅是最大值。

- Edward Kmett

---

我想要的是并行处理方法，但这仍然非常有趣。必须更深入地研究单子 :) - ondra

我有点想到了。这就是为什么我都包括进去的原因。=) - Edward Kmett

当然，这应该能够被重写以支持任何幂等交换单子群，而不仅仅是max。 - LarsH

Answer 2

针对第一个问题，请查看Conal Elliott的unamb：http://hackage.haskell.org/package/unamb

- GS - Apologise to Monica