Bộ lọc song song danh sách vô hạn trong Haskell

Question

Tôi muốn tìm phần tử khớp đầu tiên trong danh sách vô hạn trong Haskell.

Mã này đang làm việc:

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

checkPassword thực sự là dài (vì đó là một băm SHA1)

checkPassword hash string = (sha1 string) == hash 

allStrings chỉ là danh sách của tất cả các chuỗi có thể:

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

Tôi muốn mã này được chạy song song nhưng nếu tôi thay thế bộ lọc theo parFilter:

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

Nó không hoạt động ... Bạn có ý tưởng không? Mã này cũng đang sử dụng rất nhiều bộ nhớ nhưng đó là một vấn đề khác. Toàn bộ tập lệnh có sẵn tại đây https://github.com/ThibaudDauce/habreaker

Answer 1

Tôi chắc chắn bạn muốn sử dụng parBuffer thay vì evalBuffer.

Xem này SO câu trả lời cho một lời giải thích tốt:

How to choose between parList and parBuffer?

Dưới đây là một số mã demo:

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 

Ví dụ chạy:

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