---
title: Parallelizing algorithms in Haskell
tags: haskell
description: I demonstrate parallelizing existing code in Haskell
---

I've been working through [*Parallel and Concurrent Programming in
Haskell*](http://chimera.labs.oreilly.com/books/1230000000929/index.html). In
my [last
post](/posts/2014-08-26-concurrent-implementation-of-the-daytime-protocol-in-haskell.html),
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](https://en.wikipedia.org/wiki/Quicksort)[^1].

[^1]: This isn't the best algorithm to parallelize, nor is this an
efficient implementation, but it shows how to add parallelism to your
code.


> import Control.Parallel.Strategies

[Strategies](http://hackage.haskell.org/package/parallel-3.2.0.4/docs/Control-Parallel-Strategies.html)
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](/files/parallelsort.lhs) as a [literate
Haskell](http://www.haskell.org/haskellwiki/Literate_programming) file.
