Infinite list parallel filter in Haskell

Question

I want to find the first matching element in a infinite list in Haskell.

This code is working:

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

checkPassword is really long (because it's a SHA1 hash)

checkPassword hash string = (sha1 string) == hash

allStrings is just the list of all possible strings:

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

I want this code to be run in parallel but if I replace filter by parFilter:

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

It doesn't work… Do you have an idea? This code is also using a lot of memory but it's another problem. The full script is available here https://github.com/ThibaudDauce/habreaker

Answer 1

I'm pretty sure you want to use parBuffer instead of evalBuffer.

See this SO answer for a good explanation:

How to choose between parList and parBuffer?

Here is some 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

Example runs:

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