divide and conquer
这一部分主要是对作业中divideAndConquer的解释，因为我觉得这个...一开始就没怎么理解。
divideAndConquer ::
(a -> Bool) ->
(a -> b) ->
(a -> (a,a)) ->
(b -> b -> b) ->
a -> b
divideAndConquer simpleEnough simpleCases splitFunction combineFunction =
recursively
where
recursively input =
if simpleEnough input then simpleCases input
else
let
(left,right) = splitFunction input
in
combineFunction (recursively left) (recursively right)
sort :: [Integer] -> [Integer]
sort =
divideAndConquer
(\list -> length list <=1)
id
(\list-> splitAt(length list`div`2) list)
merge
merge::[Integer]->[Integer]->[Integer]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) ys | x
这里我们尝试使用divideAndConquer方法来进行merge sort。
首先divideAndConquer的定义：
divideAndConquer ::
(a -> Bool) ->
(a -> b) ->
(a -> (a,a)) ->
(b -> b -> b) ->
a -> b
它接受4个函数加一个任意类型的参数返回一个任意类型的参数。
在后面recursivly给出来具体的定义。
recursively
where
recursively input =
if simpleEnough input then simpleCases input
else
let
(left,right) = splitFunction input
in
combineFunction (recursively left) (recursively right)
我们结合后面的具体定义一起来看:
divideAndConquer
(\list -> length list <=1)
id
(\list-> splitAt(length list`div`2) list)
merge
simpleEnough检查list是否被分解到长度为1或者0，如果是它返回simpleCase，在这里，由于元素少于两个，所以没有作排序的必要，我们直接返回它本身即 identity function -- id。
如果不是，那么我们首先将list分为两半然后merge这两半。对于每个要merge的对象，我们再应用recursivly。迭代将于长度为1终止。例如：
[2,1,4,3] = merge [2,1] [4,3] = merge (merge [2] [1]) (merge [4] [3])
对于[1],[2],[3],[4]来说，它们都simpleEnough也所以应用了simpleCases即返回它们本身。然后进行了merge。
[2,1,4,3,5] = merge [2,1] [4,3,5] = merge (merge [2] [1]) (merge [4] [3,5]) = merge (merge [2] [1]) (merge [4] (merge [3] merge [5]))
