Haskell笔记4

 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]))