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

Das ist die "haskellischste" Methode, die ich mir vorstellen kann. Das Einzige, was fehlt, ist die Möglichkeit, kleiner/größer als eine "where"-Klausel zu deklarieren:

let rec qsort:int list -> int list = function
    | [] -> []
    | x::xs -> let smaller = [for a in xs do if a<=x then yield a]
               let larger =  [for b in xs do if b>x then yield b]
               qsort smaller @ [x] @ qsort larger

Ich weiß, das gehört nicht zu Ihrer Frage, aber ich würde die List.partition um die Liste in einem einzigen Durchgang zu verkleinern/vergrößern:

let rec qsort = function
    | [] -> []
    | x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
               qsort smaller @ [x] @ qsort larger

Answer 2

Ihre zweite Match-Klausel soll lauten x :: xs und den Operator @ (Anhängen) zu verwenden, wo Ihr Haskell-Beispiel ++ verwendet:

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

Es ist nicht ganz dasselbe wie die Syntax der Haskell-Definition nach Fällen, aber hoffentlich ähnlich genug für Sie!

Answer 3

...Oder Sie könnten ein rekursives qsort mit Hilfe von CPS erstellen:

let qSort lst = 
   let rec qs l cont = 
       match l with
       | []      -> cont []
       | (x::xs) -> qs (List.filter (fun e -> e <= x) xs) (fun smaller ->
                    qs (List.filter (fun e -> e >  x) xs) (fun larger  ->
                        smaller @ (x :: larger) |> cont))
   qs lst id

Answer 4

Dies scheint so prägnant zu sein, wie es nur geht (Kombination der Ideen aus anderen Antworten und Verwendung von Currying für Operatoren):

let rec qsort = function
| [] -> []
| (x:int) :: xs ->
    let smaller = List.filter ((>=) x) xs
    let larger  = List.filter ((<) x) xs
    qsort smaller @ [x] @ qsort larger

Answer 5

Die 'where'-Syntax von Haskell, mit der man den Namen einer Funktion vor ihrer Definition verwenden kann, entspricht in etwa dem f# 'let rec ... and'.

let qsort xs =
    let rec sort xs = 
        match ls with
        |[] -> ....
        |h::t -> (smaller t) @ h @ (larger t)

    and smaller ls =    //the 'and' lets you define the 
                        //  function after where it is used, 
                        //  like with 'where' in haskell
         ... define smaller in terms of sort
    and larger ls =
         ... same

    sort xs