haskell - 改进 naive qsort 实现

Question

我开始学习 Haskell 并且我一直在阅读 this 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

随后发出警告，表明这不是最有效的方法，并链接 article它显示了同一算法的极其冗长的版本。仅仅通过查看它，我就认为这不是我学习 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 的修改后的 qsort' 将是

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 的修复可以让您更好地获得常数因子，但是 ++ 与 :++: 意味着 >qsort 现在可以比 O(n^2) 更好。此外，大多数排序实现都比这更好。这样做的目的只是为了尽可能地反射(reflect)“天真的”实现。