分而治之：合併排序

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：。需要的東西列表，合併排序，這就是合併魔術發生的位置:)

注意：合併排序算法可能與我提到的有點不同。例如，排序列表也可以是一個微不足道的情況。