Haskell快速排序效率

Question

下面是一个学习Haskell的例子：

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

对于每个递归，似乎每个列表迭代两次，对于每个列表理解，迭代一次。对此进行优化的编译器有什么神奇之处吗？如果没有，如何解决这个问题？

编辑:我不在乎这是否是一个真正的快速。忽略快速排序。我的问题是关于两个列表理解的效率，以及如何修改这个特定的算法(快速排序或不修改)，以避免每次递归迭代xs两次。

Answer 1

不是的。到目前为止，GHC7.8.2还不够聪明，无法从上面的quicksort定义中找到聪明的就地快速排序算法。通过定义quicksort，您可以在一次传递中执行相同的操作

import Data.List (partition)
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = let (psx1, psx2, psx3) = partition3 x (x:xs) in
                   quicksort psx1 ++ psx2 ++ quicksort psx3

partition3 _ [] = ([], [], [])
partition3 a (x:xs)
    | a == x = (pxs1, x:pxs2, pxs3)
    | a < x = (pxs1, pxs2, x:pxs3)
    | a > x = (x:pxs1, pxs2, pxs3)
    where (pxs1, pxs2, pxs3) = partition3 a xs

但是您应该检查is it possible to do quicksort of a list with only one passing?，因为它比上面的版本更有效。