クィックソートを並列で。

正規形(NF),頭部正規形(HNF),弱頭部正規形(WHNF)を理解した。

Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。

module Sorting where

import Control.Parallel (par, pseq)

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs) = force greater `par` (force lesser `pseq`
                                     (lesser ++x:greater))
    where lesser  = parSort [y|y <- xs, y<x]
          greater = parSort [y|y <- xs, y>=x]
parSort _ = []

force :: [a] -> ()
force xs = go xs `pseq` ()
    where go (_:xs) = go xs
          go [] = 1

sort :: (Ord a) => [a] -> [a]
sort (x:xs) = lesser ++ x:greater
    where lesser  = sort [y|y <- xs, y<x]
          greater = sort [y|y <- xs, y>=x]
sort _ = []

parSort2 :: (Ord a) => Int -> [a] -> [a]
parSort2 d list@(x:xs) 
   | d <= 0 = sort list
   | otherwise = force greater `par` (force lesser `pseq`
                                     (lesser ++x:greater))
       where lesser  = parSort2 d' [y|y <- xs, y<x]
             greater = parSort2 d' [y|y <- xs, y>=x]
             d' = d - 1
parSort2 _ _ = []

で実際に時間を測ってみると

-- parSort2
kzfm:ch24 kzfm$ ./SortMain +RTS -N2 -RTS 1000000
we have 1000000 elements to sort.
sorted all 1000000 elements.
11.419152s elapsed.

-- sort
kzfm:ch24 kzfm$ ./SortMain 1000000
we have 1000000 elements to sort.
sorted all 1000000 elements.
6.212093s elapsed.

-- parSort -N2
kzfm:ch24 kzfm$ ./SortMain +RTS -N1 -RTS 1000000
we have 1000000 elements to sort.
sorted all 1000000 elements.
6.188667s elapsed.

-- parSort -N2
kzfm:ch24 kzfm$ ./SortMain +RTS -N2 -RTS 1000000
we have 1000000 elements to sort.
sorted all 1000000 elements.
35.960397s elapsed.

GCのせいかな、よくわからん。