找到你要的答案

Q:Divide and conquer: Merge sort

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 ?

我不明白下面Haskell和分而治之的构建相当新的:

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

那么上面的结构是如何工作的呢?“X”和“Y”代表什么?什么应该“琐碎”和“解决”(分裂/组合)呢?

answer1: 回答1:

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.

因此,DC的签名可以被视为“这个函数需要4个参数,并返回一个函数从A到B”。在定义中,这个函数被称为x。x在WHERE子句中定义为:

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

可以为x添加类型签名:

x :: a -> b

定义x(即函数执行实际分治计算)有点模糊,但可以读作:

  • 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 :)

注意:合并排序算法可能与我提到的有点不同。例如,排序的列表也可以是一个琐碎的情况下。

haskell