# Q：分而治之：归并排序

I'm fairly new to Haskell and don't understand the following divide and conquer construct:

``````{-     trivial        solve       split        combine       input/output-}
dc :: (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
dc trivial solve split combine = x
where
x y = if trivial y then solve y
else (\_ z -> combine z) y (map x (split y))
``````

Now I need to implement a merge-sort function based on this construct. I tried to implement some functions but I'm pretty sure that's not how it should work:

``````trivial :: (Ord a, Num a) => [a] -> Bool
trivial [] = True
trivial (x:[]) = True
trivial (x:x':xs) = if x<=x' then trivial (x':xs) else False

split :: [a] -> [[a]]
split (x:[]) = [[x]]
split (x:xs) = [x] : split xs

combine :: [[a]] -> [a]
combine [[]] = []
combine ([]:ys) = combine ys
combine ((x:xs):ys) = x : combine (xs:ys)
``````

So how does the construct above work ? What does "x" and "y" stand for ? What should "trivial" and "solve" (and split/combine) do ?

``````{-     trivial        solve       split        combine       input/output-}
dc :: (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
dc trivial solve split combine = x
where
x y = if trivial y then solve y
else (\_ z -> combine z) y (map x (split y))
``````

``````trivial :: (Ord a, Num a) => [a] -> Bool
trivial [] = True
trivial (x:[]) = True
trivial (x:x':xs) = if x<=x' then trivial (x':xs) else False

split :: [a] -> [[a]]
split (x:[]) = [[x]]
split (x:xs) = [x] : split xs

combine :: [[a]] -> [a]
combine [[]] = []
combine ([]:ys) = combine ys
combine ((x:xs):ys) = x : combine (xs:ys)
``````

So, the signature of dc can be read as "this function takes 4 arguments and returns a function from a to b". In the definition, this function is called x. x is defined in the where clause, as:

``````x y = if trivial y then solve y
else (\_ z -> combine z) y (map x (split y))
``````

You could add a type signature for x:

``````x :: a -> b
``````

The definition of x (which is the function that performs your actual divide and conquer computation) is somewhat obfuscated, but can be read as:

• If x is a trivial case, just solve it
• Otherwise, split it, divide-and-conquer it (with `x`), then combine the result.

Note: It could be written a bit more clearly as:

``````x y = if trivial y then solve y
else (combine . map x . split) y
``````

This function does all the recursivity you need, so your functions don't need to care about that. Your functions should be:

• `trivial`: True if the problem can be solved with `solve` in this case. For the merge sort, the trivial case is the list that contains only one item.
• `solve`: solves the trivial case. For the merge sort, it's just the identity (since it's just a one item list).
• `split`: split the big problem into smaller problems (which will be done many times, until they are trivial. For the merge sort, it's just about splitting the list in half.
• `combine`: takes a list of stuff that were previously splitted, and combine them. For the merge sort, that's where the merging magic happens :)

Note: the merge sort algorithm can be a bit different from what I mentioned. For example, a sorted list can also be a trivial case.

``````x y = if trivial y then solve y
else (\_ z -> combine z) y (map x (split y))
``````

``````x :: a -> b
``````

• If x is a trivial case, just solve it
• Otherwise, split it, divide-and-conquer it (with `x`), then combine the result.

``````x y = if trivial y then solve y
else (combine . map x . split) y
``````

• `trivial`: True if the problem can be solved with `solve` in this case. For the merge sort, the trivial case is the list that contains only one item.
• `solve`: solves the trivial case. For the merge sort, it's just the identity (since it's just a one item list).
• `split`: split the big problem into smaller problems (which will be done many times, until they are trivial. For the merge sort, it's just about splitting the list in half.
• `combine`: takes a list of stuff that were previously splitted, and combine them. For the merge sort, that's where the merging magic happens :)