CodeWa!
找到你要的答案

## Q：Divide and conquer: Merge sort |
## Q：分而治之：归并排序 |

I'm fairly new to Haskell and don't understand the following divide and conquer construct:
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:
So how does the construct above work ? What does "x" and "y" stand for ? What should "trivial" and "solve" (and split/combine) do ? |
我不明白下面Haskell和分而治之的构建相当新的：
现在我需要实现一个基于这个构造的归并排序函数。我试图实现一些功能，但我敢肯定，这不是它应该如何工作：
那么上面的结构是如何工作的呢？“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:
You could add a type signature for x:
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:
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添加类型签名：
定义x（即函数执行实际分治计算）有点模糊，但可以读作： - If x is a trivial case, just solve it
- Otherwise, split it, divide-and-conquer it (with
`x` ), then combine the result.
注：它可以写得更清楚一点：
这个功能是所有递归你需要的，所以你的函数不需要在乎。你的功能应该是： -
`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 |