改进朴素的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)

然后，返回Seq 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)更好。而且，大多数的排序实现都比这更好。这样做的目的只是试图尽可能地反映“天真”的实现。