QuickSort em Haskell - Outra Implementação

Estou estudando Haskell faz algum tempo. Existem duas funções que acredito serem o "Hello World!' do Haskell: fatorial e quicksort. Essas duas funções fornecem uma boa idéia do que ganhamos quando descrevemos um problema (forma descritiva) ao invés de tentarmos resolvê-lo (forma imperativa). Quando vi o quicksort (em Haskell) pela primeira vez, percebi que a lista sofria duas leituras: uma para os elementos menores ou iguais ao pivot; outra para os elementos maiores que o pivot.

-- Tradicional: lê a lista duas vezes
quicksort []  = []
quicksort (a:as) = quicksort ( [x | x <- as, x <= a] ) ++   -- primeira leitura
                   [ a ]                               ++  
                   quicksort ( [x | x <- as, x > a] )       -- segunda leitura 

Desde essa primeira vez, fiquei incomodado com isso - pois, eu acreditava que seria melhor se fizesse apenas uma leitura na lista. Demorou muito tempo, desde então... :-) Pois, não estudei tão rapidamente quanto poderia. Mas, finalmente, produzi a tal função. Segue o quicksort:

-- Com separador: lê a lista uma vez
-- by Marcelo Parrela (marcelo.parrela@gmail.com)
quicksort' []  = []
quicksort' (a:as) = quicksort' l1 ++ a : quicksort' l2 
    where
        (l1,l2) = separate as a [] []
        -- lê a lista e a separa em duas: l1 para os elementos
        -- menores ou iguais ao pivot e l2 para os demais
        separate [] _ a b = (a,b)
        separate (l:ls) a l1 l2
            | l <= a    = separate ls a l1' l2
            | otherwise = separate ls a l1 l2'
            where 
                l1' = l1++[l] --montando lista de elementos menores
                l2' = l2++[l] --montando lista para os demais elementos
                

Essa primeira solução ainda não é muito boa - por causa da aplicação da função (++). Esta função, neste contexto, prejudica a performance. Sendo assim, produzi uma segunda solução, corrigindo apenas esse ponto. Segue o código abaixo:

-- Com separador: lê a lista uma vez
-- Com performance melhorada
-- by Marcelo Parrela (marcelo.parrela@gmail.com)
quicksort' []  = []
quicksort' (a:as) = quicksort' l1 ++ a : quicksort' l2 
    where
        (l1,l2) = separate as a [] []
        -- lê a lista e a separa em duas: l1 para os elementos
        -- menores ou iguais ao pivot e l2 para os demais
        separate [] _ a b = (a,b)
        separate (l:ls) a l1 l2
            | l <= a    = separate ls a l1' l2
            | otherwise = separate ls a l1 l2'
            where 
                l1' = l:l1 --montando lista de elementos menores
                l2' = l:l2 --montando lista para os demais elementos
                

Outro benefício interessante é que esta função é polimórfica. Note que não há declaração de tipos, na definição da função. Isso que dizer que ela pode ser utilizada para ordenar qualquer tipo de dado que seja ordenável. Veja o exemplo abaixo:

    quicksort' "Teste de Ordenacao"
    "  OTaacddeeeenorst"

    quicksort' [3,4,1,0,12,0,(-1),10]
    [-1,0,0,1,3,4,10,12]

    quicksort' [3.25 , 4.0 , 1.2, 0.5 , 12.1 , 0.2 , (-1) , 10 ]
    [-1.0,0.2,0.5,1.2,3.25,4.0,10.0,12.1]

    quicksort' [True, False, True, False, False ]
    [False,False,False,True,True]

Por Marcelo Parrela (marcelo.parrela@gmail.com)