sorting - 对任何类型的列表进行快速排序 | haskell

Question

我目前正在 learnyouahaskell.com 上学习 Haskell，他们向我们展示了以下用于整数列表的快速排序算法。

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<=x) xs)  
        biggerSorted = quicksort (filter (>x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted  

有没有办法修改它以接受任何类型的列表？我正在考虑添加一个额外的参数来指示要使用的比较操作

Answer 1

您可以，正如您在 your comment 中指定的那样，传递一个函数，该函数将确定例如第一项是否小于或等于第二项，或任何其他顺序关系。

在这种情况下，您可以使用:

quicksort :: (a -> a -> Bool) -> [a] -> [a]    
quicksort _ [] = []
quicksort <b>lte</b> (x:xs) =
    let smallerSorted = quicksort <b>lte</b> (filter (`<b>lte</b>` x) xs)  
        biggerSorted = quicksort <b>lte</b> (filter <b>…</b> xs)
    in  smallerSorted ++ x : biggerSorted

对于 ... 部分，您必须取消 lte 函数。我把它留作练习。