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

Ответы

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

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

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