Unendliche Liste parallel Filter in Haskell

Question

Ich möchte das erste übereinstimmende Element in einer unendlichen Liste in Haskell finden.

Dieser Code arbeitet:

findPassword passwordHash = (head . filter (checkPassword passwordHash)) allStrings 

check wirklich lang ist

checkPassword hash string = (sha1 string) == hash 

allStrings ist (weil es ein SHA1-Hash ist) nur die Liste aller möglichen Zeichenketten:

allStrings = [ c : s | s <- "" : allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ] 

Ich möchte, dass dieser Code parallel ausgeführt wird, aber wenn ich Filter durch parFilter ersetzen:

import qualified Control.Parallel.Strategies as S 
parFilter p = S.withStrategy (S.evalBuffer 1000 S.rseq) . filter p 

Es funktioniert nicht ... Haben Sie eine Idee? Dieser Code verwendet auch viel Speicher, aber es ist ein anderes Problem. Das vollständige Skript finden Sie hier https://github.com/ThibaudDauce/habreaker

Answer 1

Ich bin ziemlich sicher, Sie parBuffer statt evalBuffer verwenden möchten.

Sehen Sie diese SO Antwort für eine gute Erklärung:

How to choose between parList and parBuffer?

Hier finden Sie einige Demo-Code:

import qualified Data.Map.Strict as M 
import Control.Parallel.Strategies 
import System.Environment 
import Debug.Trace 

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-2) + fib (n-1) 

fib' n | trace "calling fib" False = undefined 
fib' n = fib n 

theList = cycle [30,31,32] 

firstN :: Int -> [Int] 
firstN n = take n $ filter even $ map fib' theList 

firstNpar :: Int -> Int -> [Int] 
firstNpar n k = take n $ filter even $ runEval $ parBuffer k rseq $ map fib' theList 

main = do 
    (argn : argk : _) <- getArgs 
    let n = read argn 
    case argk of 
    "" -> print $ firstN n 
    _ -> let k = read argk in 
      print $ firstNpar n k 

Beispiel läuft:

prog 20 2 +RTS -N2   -- I only have two cores 
prog 20 ''     -- run single threaded