Haskell推测并行执行

Question

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

我有解决S1 2种不同的算法 - '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 = 0 
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3)) 
update threshold from firstSolution 
wait for second solution 

Answer 1

归根结底，任何解决方案会倒闭，因为你要多个事务中发生的引擎盖下使用ForkIO平行。即使康纳尔的unamb以这种方式工作。

对于后者，你可能需要一个更复杂的monad，它可以批量并运行一段时间，然后偶尔检查一个MVar单调递增的值，但交织（在一个线程中）的最简单答案是只写一个偏爱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实例来处理递归或宽松洒“产量”呼叫，可以在部分单子执行这两个您的运营和种族他们获得一个确定的结果。

但是在实践中，如果你想获得并行性的全部好处，你需要定期更新和检查某种'改进'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 

当然，这应该能够被重写以支持任何幂等性交换幺半群，而不仅仅是最大值。

Answer 2

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