简化选择排序和归并

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)