Let us consider the parallel behaviour of pfib, a very simple divide-and-conquer program.
pfib :: Int -> Int
pfib n
| n <= 1 = 1
| otherwise = n1 `par` n2 `seq` n1+n2+1
where
n1 = pfib (n-1)
n2 = pfib (n-2)
If n is greater than 1, then
pfib (n-1) is sparked, and the thread continues to
evaluate pfib (n-2). The figure below
shows a process
diagram of the execution of pfib 15. Each node in the diagram is
a function application, and each arc carries the data value, in this case
an integer, used to communicate between the invocations. Brackets can
safely be omitted because seq has a higher precedence than par.
Parallel quicksort is a more realistic example, and we might write the following as a first attempt to introduce parallelism.
quicksortN :: (Ord a) => [a] -> [a]
quicksortN [] = []
quicksortN [x] = [x]
quicksortN (x:xs) = losort `par`
hisort `par`
losort ++ (x:hisort)
where
losort = quicksortN [y|y <- xs, y < x]
hisort = quicksortN [y|y <- xs, y >= x]
The intention is that two threads are created to sort the lower and higher halves of the list in parallel with combining the results. Unfortunately quicksortN has almost no parallelism because threads in GpH terminate when the sparked expression is in WHNF. In consequence, all of the threads that are sparked to construct losort and hisort do very little useful work, terminating after creating the first cons cell. To make the threads perform useful work a "forcing" function, such as forceList below, can be used. The resulting program has the desired parallel behaviour, and a process network similar to pfib, except that complete lists are communicated rather than integers.
forceList :: [a] -> ()
forceList [] = ()
forceList (x:xs) = x `seq` forceList xs
quicksortF [] = []
quicksortF [x] = [x]
quicksortF (x:xs) = (forceList losort) `par`
(forceList hisort) `par`
losort ++ (x:hisort)
where
losort = quicksortF [y|y <- xs, y < x]
hisort = quicksortF [y|y <- xs, y >= x]
|