分而治之：合并排序

Question

我是相当新的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”代表什么？ “微不足道”和“解决”（以及分裂/合并）应该做什么？

Answer 1

因此，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的定义（这是执行实际的分而治之的计算功能）有些混淆，但可以理解为：

• 如果x是一个微不足道的情况，就解决它
• 否则，将其分开，分而治之（与x），然后合并结果。

注：可以多一点清楚地写为：

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

此功能，所有你需要的递归性，所以你的功能并不需要关心这个。你的职责应该是：

• trivial：如果真正的问题可以用solve在这种情况下得到解决。对于合并排序，简单情况是仅包含一个项目的列表。
• solve：解决琐碎的情况。对于合并排序，它只是标识（因为它只是一个项目列表）。
• split：分裂的大问题分解成更小的问题（将做过很多次，直到他们是平凡的合并排序，它只是在一半分裂名单
• combine：。需要的东西列表，合并排序，这就是合并魔术发生的位置:)

注意：合并排序算法可能与我提到的有点不同。例如，排序列表也可以是一个微不足道的情况。