Параллельное «любое» или «все» в Haskell

Шаблон, с которым я сталкивался несколько раз, - это тот, в котором список значений должен быть проверен путем сопоставления некоторого теста и проверки, прошел ли какой-либо или все элементы. Типичное решение - просто использовать удобные встроенные функции allи any.

Проблема в том, что они оцениваются в сериале. Во многих случаях было бы намного быстрее выполнять оценку параллельно с завершением процесса, если какой-либо поток найдет «False» для allили «True» для any. Я почти уверен, что поведение короткого замыкания не может быть реализовано с помощью Control.Parallel, поскольку оно требует межпроцессного взаимодействия, и я пока не понимаю достаточно близко к Control.Concurrent, чтобы реализовать это.

Это довольно распространенный паттерн в математике (например, Миллер-Рабин Прималити), поэтому я чувствую, что кто-то, возможно, уже нашел решение для этого, но по понятным причинам делает поиск в Google "параллельно или / и / любой / все в списке". haskell "не возвращает много релевантных результатов.

Во многих реалистичных программах вы можете использовать параллельные стратегии для этой цели. Это потому, что, хотя нет явного механизма отмены ненужных вычислений, это будет происходить неявно при запуске сборщика мусора. В качестве конкретного примера рассмотрим следующую программу:

import Control.Concurrent
import Control.Parallel.Strategies
import Data.Int
import System.Mem

lcgs :: Int32 -> [Int32]
lcgs = iterate lcg
  where lcg x = 1664525 * x + 1013904223

hasWaldo :: Int32 -> Bool
hasWaldo x = waldo `elem` take 40000000 (lcgs x)

waldo :: Int32
waldo = 0

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)

При этом используется стратегия параллельного списка для поиска waldo = 0(который никогда не будет найден) в выходных данных 100 потоков PRNG по 40 миллионов номеров в каждом. Скомпилируйте и запустите:

ghc -threaded -O2 ParallelAny.hs
./ParallelAny +RTS -s -N4

и он привязывает четыре ядра к 16 секундам, в конце концов печатая False. Обратите внимание на статистику, что все 100 искр "преобразованы" и поэтому работают до завершения:

SPARKS: 100(100 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

Теперь измените waldoзначение, которое можно найти раньше:

waldo = 531186389   -- lcgs 5 !! 50000

и изменить, mainчтобы сохранить поток в течение 10 секунд:

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  threadDelay 10000000

Вы заметите, что он печатает Trueпочти сразу, но 4 ядра остаются привязанными на 100% CPU (по крайней мере, на некоторое время), показывая, что ненужные вычисления продолжают работать и не закорачиваются, как вы, возможно, опасались.

НО , все изменится, если вы заставите сборщик мусора после получения ответа:

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  performGC
  threadDelay 10000000

Теперь вы увидите, что ЦП вскоре после печати переключается в режим ожидания True, а статистика показывает, что большинство вычислений были собраны мусором перед запуском:

SPARKS: 100(9 converted, 0 overflowed, 0 dud, 91 GC'd, 0 fizzled)

В реалистичных программах явное указание performGCне потребуется, поскольку GC будут выполняться регулярно, как само собой разумеющееся. Некоторые ненужные вычисления будут продолжать выполняться после того, как ответ найден, но во многих реалистичных сценариях доля ненужных вычислений не будет особенно важным фактором.

В частности, если список большой и каждый отдельный тест элемента списка быстр, параллельные стратегии будут иметь отличную производительность в реальном мире и их легко внедрить в сделку.