knuthBendix algorithm cannot be parallelized by Control.Parallel?

haskell, knuth, multithreading, parallel-processing

Solution

I believe the problem is that you're calling `as' `pseq``. This evaluates `as'` to WHNF, which means that it only determines whether the list is empty or not. But you want the lists to be fully evaluated:

import Control.Parallel.Strategies    

forceList :: [a] -> [a]
forceList = withStrategy (evalList rseq)
-- or use rdeepseq to force the evaluation of everything

knuthBendixOptimized rs =        forceList as'
                          `par`  forceList bs'
                          `pseq` as' ++ bs'
  where
    (as, bs) = splitAt 3000 rs
    as' = knuthBendix as
    bs' = knuthBendix bs

Note that Haskell's usual term for this is parallelism. And concurrency is used for explicit work in `IO` with threads and their communication. See the GHC manual.

Problem

I am trying to apply knuthBendix to large sets of rewriting rules. Thus, I try to let it work on different sets in parallel. As en example, I try to run: ``` import Control.Parallel import Control.Parallel.Strategies import Math.Algebra.Group.StringRewriting knuthBendixOptimized rs = as' `par` bs' `pseq` as' ++ bs' where (as, bs) = splitAt 3000 rs as' = knuthBendix as bs' = knuthBendix bs ``` I compile using `ghc -threaded` and I execute via `+RTS -N`. If I run other algorithms in parallel, it works. But for knuthBendix, it does not. Does someone know a solution? Thanks, Franz

Original source