我对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”代表什么？“琐碎”和“解决”（以及拆分/合并）应该做什么？
因此，的签名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 y = if trivial y then solve y
else (combine . map x . split) y
此函数可完成您需要的所有递归操作，因此您的函数无需关心。您的功能应为：
trivial：如果solve在这种情况下可以解决问题，则为true 。对于合并排序，普通情况是仅包含一项的列表。solve：解决小问题。对于合并排序，它只是标识（因为它只是一个项目列表）。split：将大问题分解为较小的问题（将完成很多次，直到它们变得微不足道。对于合并排序，这只是将列表分成两半。combine：获取以前拆分的内容的列表，并将它们组合在一起。对于合并排序，这就是合并魔术发生的地方:)注意：合并排序算法可能与我提到的有所不同。例如，排序列表也可以是平凡的情况。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句