改进朴素的 qsort 实现

Question

我开始学习 Haskell，我一直在阅读Haskell wiki 上的这个页面，它报告了这个 qsort 实现：

 qsort :: (Ord a) => [a] -> [a]
 qsort []     = []
 qsort (x:xs) = qsort less ++ [x] ++ qsort more
     where less = filter (<x)  xs
           more = filter (>=x) xs

接着是警告说这不是最有效的方法，并链接了一篇文章，该文章显示了相同算法的极其冗长的版本。只是看着它，我认为那不是我学习 Haskell 的目的，我想在不牺牲其优雅的情况下制作初始 qsort 的更好版本。我主要集中在消除filter每次调用运行两次的需要，这就是我提出的：

filter' :: (a -> Bool) -> [a] -> ([a], [a])
filter' _ [] = ([], [])
filter' f a = filterInternal a ([], [])
  where
    filterInternal [] p = p
    filterInternal (x:xs) (l, t)
      | f x       = filterInternal xs (x:l, t)
      | otherwise = filterInternal xs (l, x:t)

qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = qsort' less ++ [x] ++ qsort' more
  where
    (more, less) = filter' (>x) xs

但我不确定这是否真的更好。我的意思是，它有效，但它与初始版本相比如何？

Answer 1

这是我在思考大致相同的问题时提出的解决方案（请指出任何警告！）。我没有考虑太多空间复杂性（不过不应该太糟糕），只是考虑时间。真正扼杀幼稚的qsort是O(n)操作(++)。因此，让我们使用一种新的数据结构（将是可折叠的）来实现快速串联。

{-# LANGUAGE DeriveFoldable #-}

import Data.Foldable
import Data.List

data Seq a = (Seq a) :++: (Seq a) | Leaf a | Empty deriving (Foldable)

qsort'然后，返回 a 的修改Seq a将是

qsort' :: Ord a => [a] -> Seq a
qsort' []     = Empty
qsort' (x:xs) = qsort less :++: Leaf x :++: qsort more
    where (less, more) = partition (<x)  xs

而qsort其本身则只是qsort = toList . qsort'。

注意：涉及的修复partition可以让您更好地获得常数因子，但++vs:++:意味着qsort现在可以比 更好O(n^2)。此外，大多数排序实现都比这更好。这样做的目的只是为了尽可能地反映“天真的”实现。