Proof of concept abstraction of divide and conquer. Doesn't really work very well...

DnC.hs

-- In Divide and Conquer, we solve a problem recursively, applying three steps at each level of recursion.



dnc :: (a -> [a]) -> (a -> b) -> ([b] -> b) -> a -> b
dnc divide con comb x = case divide x of
                        [] -> con x
                        xs -> comb $ map (dnc divide con comb) xs


split :: [a] -> ([a], [a])
split []        = ([], [])
split [x]       = ([x], [])
split (x:y:zs)  = (x:xs, y:ys) where (xs, ys) = split zs


merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x < y       = x : merge xs (y:ys)
  | otherwise   = y : merge (x:xs) ys

mergesort :: Ord a => [a] -> [a]
mergesort = dnc split' id merge'
    where
        split' xs = case split xs of
            ([], []) -> []
            ([], r) -> []
            (l, []) -> []
            (l, r) -> [l, r]
        merge' :: Ord a => [[a]] -> [a]
        merge' [] = []
        merge' [x] = x
        merge' (x:y:zs) = merge' (merge x y:zs)

main = undefined

This is just map reduce.