Улучшение наивные реализации QSort

Question

Я начинаю изучать Haskell, и я читал this страницу на вики Haskell, который сообщает эту реализацию 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) 

Затем модифицированный qsort', который возвращает 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 получает вас постоянный фактор лучше, но ++ против :++: означает, что qsort теперь может быть лучше, чем O(n^2). Кроме того, большинство вариантов реализации там лучше, чем это. Дело в том, чтобы попытаться максимально точно отразить «наивную» реализацию.