Parallelizing algorithms in Haskell
I’ve been working through Parallel and Concurrent Programming in Haskell. In my last post, I demonstrated the facilities Haskell provides for lightweight concurrency. In this post, let’s take a look at Haskell facilities for parallelism.
As a brief example, let’s parallelize Quicksort1.
> import Control.Parallel.Strategies
Strategies provide a means to tell the run-time system how to evaluate objects. We’ll be using
rseq is the sequential evaluation strategy, and
parList takes a strategy for list items, and uses that strategy for each list element in parallel.
Here’s our non-parallelized Quicksort implementation:
> quicksort :: Ord a => [a] -> [a] > quicksort  =  > quicksort (x:xs) = > let leftPartition = [y | y <- xs, y < x] > rightPartition = [y | y <- xs, y >= x] > left = quicksort leftPartition > right = quicksort rightPartition > in left ++ [x] ++ right
Quicksort partitions a list around a pivot, sorts each partition, and then combines the partitions and the pivot.
Our parallelized version is almost the same:
> parallelsort :: Ord a => [a] -> [a] > parallelsort  =  > parallelsort (x:xs) = > let leftPartition = [y | y <- xs, y < x] `using` parList rseq > rightPartition = [y | y <- xs, y >= x] `using` parList rseq > left = parallelsort leftPartition > right = parallelsort rightPartition > in left ++ [x] ++ right
We simply tell the run-time system what strategy to use for the list comprehensions.
This doesn’t really improve much in this case, but when used judiciously, extending your existing code with parallelism is straight-forward in Haskell.
This post is also available as a literate Haskell file.
This isn’t the best algorithm to parallelize, nor is this an efficient implementation, but it shows how to add parallelism to your code.↩