Google Groups

how to write this with Control.Conurrent.Strategies ?


Johannes Waldmann Jan 24, 2012 1:54 AM
Posted in group: parallel-haskell
Dear all, I have this straightforward mergesort program
using par/pseq:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys ; merge xs [] = xs
merge (x:xs) (y:ys) =
    if x < y then x : merge xs (y:ys)
             else y : merge (x:xs) ys

split :: [a] -> ([a],[a])
split xs = splitAt ( div ( length xs ) 2 ) xs

msort :: Ord a => [a] -> [a]
msort [] = [] ; msort [x] = [x]
msort xs =
    let ( here, there ) = split xs
        mshere = msort here
        msthere = msort there
    in  par ( last mshere )
        $ pseq ( last msthere )
        ( merge mshere msthere  )

and it gives reasonable speed-ups with +RTS -N1,2,4,8  
(OK, going from 4 to 8 does not help).

Now - what is the Right Way to write this with strategy annotations?
(`using` rpar? ...)

I want to tell my students 1. "mergesort already *is* an inherently parallel
algorithm" and 2. "you can execute it as such - you just need to annotate
the source text".

Thanks - J.W.