kms

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 Quicksort¹.

> 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.