Quicksort in F# - Frage zur Syntax

Question

Ich habe eine einfache f# schnelle Sortierfunktion definiert als:

let rec qsort(xs:List<int>) =

let smaller = xs |> List.filter(fun e -> e < xs.Head)
let larger = xs |> List.filter(fun e -> e > xs.Head)
match xs with
| [] -> []
| _ -> qsort(smaller)@[xs.Head]@qsort(larger)

Gibt es eine Möglichkeit, in f# zu schreiben es mehr wie Haskell:

qsort       :: [Int] -> [Int]
qsort []     = []
qsort (x:xs) =
qsort smaller ++ [x] ++ qsort larger
where
  smaller = [a | a <- xs, a <= x]
  larger  = [b | b <- xs, b >= x]

Ich weiß, dass dem f#-Algorithmus ein <= und >= fehlt. Die Frage bezieht sich eher auf die Syntax/Lesbarkeit.

Danke.

Answer 1

let  rec QuickSort l =
        match   l with  
        |  []  ->  []
        |   _   ->  QuickSort([for e in l do if e < (List.head l) then yield e]) @[(List.head l)]@ QuickSort([for e in l do if e > (List.head l) then yield e])

Answer 2

Vergessen Sie nicht, dass List eine Partitionsmethode hat, also

let rec quicksort ls =
    match ls with
    | [] -> []
    | h :: t -> let fore, aft = List.partition (fun i -> i < h) t
                (quicksort fore) @ (h :: quicksort aft)

Answer 3

Ich hatte vor ein paar Jahren eine Analyse von Sortieralgorithmen in F# in einem sehr imperativen Stil durchgeführt; ich versuchte, die .NET-Implementierung zu schlagen, was mir auch gelang ici . Wollte mir heute die folgende Antwort zukommen lassen, aber FPish lässt mich kein Konto erstellen. Argh! Ich muss meinen Beitrag irgendwo veröffentlichen, und hier ist so gut wie überall, lol...

Als ich gestern "Learn You a Haskell For Great Good" las, stellte der Autor ein Beispiel für die Implementierung von quicksort vor. Die Beschreibung war ziemlich klar und noch bevor ich zum Beispielcode kam, fiel mir eine elegante rekursive Lösung (in Haskell) ein. Ich hatte wohl nie ein intuitives Gefühl dafür entwickelt, wie Quicksort funktioniert, denn die triviale Lösung ist recht einfach, wenn auch nicht sehr effizient.

Hier ist meine Version in F#:

let rec quicksort = function
    | [] -> []
    | pivot :: xs ->
        (left pivot xs) @ pivot :: (right pivot xs)
and left pivot xs = quicksort [ for x in xs do if x <= pivot then yield x ]
and right pivot xs = quicksort [ for x in xs do if x > pivot then yield x ]

Und das äquivalente Haskell (ich mag das hier... sauber!):

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot : xs) =
    left ++ pivot : right
    where
        left = quicksort [ x | x <- xs, x <= pivot ]
        right = quicksort [ x | x <- xs, x > pivot ]

Zum Schmunzeln, hier ist eine andere F#-Version (meist tail-recursive), die etwa 2x die Geschwindigkeit der trivialen Version ist. Ich habe mir nicht die Mühe gemacht, dies mit meinem ursprünglichen Beitrag zu vergleichen, also keine Ahnung, wie es sich mit der veränderbaren Version in meinem OP auf FPish.net (FSHub) von vor ein paar Jahren verträgt...

let rec quicksort' xs =
    let rec aux pivot left right = function
        | [] -> (quicksort' left) @ pivot :: (quicksort' right)
        | x :: xs ->
            if x <= pivot then
                aux pivot (x :: left) right xs
            else
                aux pivot left (x::right) xs
    match xs with
    | [] -> []
    | x :: xs -> aux x [] [] xs