Общая переменная в Haskell parMap

У меня есть вычисление, которое имеет в основном следующее:

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 были переменные переменные, то можно было бы просто в теле карты обновить эту логическую переменную (я думаю, вам нужно было бы ее заблокировать и разблокировать). Есть ли какие-либо предложения для таких действий?

Ответ 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.

Ответ 2

Вы не можете использовать государственную монаду? меняя функцию f на:

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

в

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

Вам просто нужно будет обновить значение своего состояния с помощью одного сгибания вашего списка, нет? Я не уверен, если вы можете применить его с параллельной штукой. Мои знания о Haskell несколько ограничены.