簡化選擇排序和歸併

Question

我已成功地實現在幾行插入排序和快速排序，而是選擇排序和歸併仍然讓我頭疼;）

selectionsort [] = [] 

selectionsort (x:xs) = 
    let (minimum, greater) = extractMinimum x [] xs 
    in minimum : selectionsort greater 

extractMinimum minimumSoFar greater [] = (minimumSoFar, greater) 

extractMinimum minimumSoFar greater (x:xs) 
    | x < minimumSoFar = extractMinimum x (minimumSoFar:greater) xs 
    | otherwise  = extractMinimum minimumSoFar (x:greater) xs 

是有點像extractMinimum功能提供標準的圖書館嗎？沒有任何運氣，我嘗試了(a -> a -> Bool/Ordering) -> [a] -> (a, [a])的窩點。

mergesort [ ] = [ ] 

mergesort [x] = [x] 

mergesort xs = 
    let (left, right) = splitAt (length xs `div` 2) xs 
    in merge (mergesort left) (mergesort right) 

merge xs [] = xs 

merge [] ys = ys 

merge xxs@(x:xs) yys@(y:ys) 
    | x < y  = x : merge xs yys 
    | otherwise = y : merge xxs ys 

同樣，我必須寫merge自己，或者我可以重用現有的組件？ Hoogle給(a -> a -> Bool/Ordering) -> [a] -> [a] -> [a]沒有任何有用的結果。

Answer 1

標準庫中沒有任何東西，但至少merge由hackage上的包提供，儘管我不確定這是否值得引入這種簡單函數的依賴關係。

然而，

merge xxs@(x:xs) yys@(y:ys) 
    | x < y  = x : merge xs yys 
    | otherwise = y : merge xxs ys 

產生一個非穩定的排序，以獲得一個穩定的排序，放置x的條件應該是x <= y。

對於extractMinimum，我還沒有發現任何東西，但我可以提供一個替代的定義，

extractMinimum :: Ord a => a -> [a] -> (a,[a]) 
extractMinimum x = foldl' select (x, []) 
    where 
    select (mini, greater) y 
     | y < mini = (y, mini:greater) 
     | otherwise = (mini, y:greater) 

的selectionSort一個很好的定義是

import Data.List -- for unfoldr 

selectionSort :: Ord a => [a] -> [a] 
selectionSort = unfoldr getMin 
    where 
    getMin [] = Nothing 
    getMin (x:xs) = Just $ extractMinimum x xs 

Answer 2

我的選擇排序建議：

import Data.List 

selectionsort xs = unfoldr f xs where 
    f [] = Nothing 
    f xs = Just $ extractMinimum xs 

extractMinimum (x:xs) = foldl' f (x,[]) xs where 
    f (minimum, greater) x | x < minimum = (x, minimum : greater) 
         | otherwise = (minimum, x : greater)