Quicksort in F # - domanda sintassi

Question

Ho una semplice f # rapida funzione di ordinamento definito come:

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)

C'è un modo in F # di scrivere più come 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]

So che l'algoritmo f # manca un <= e> =. La questione è più sulla sintassi / leggibilità.

Grazie.

Answer 1

Vuoi che il tuo clausola secondo match da x :: xs, e di utilizzare il @ (aggiungere) Operatore in cui il tuo esempio Haskell utilizza ++:

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

Non è proprio la stessa cosa, come la definizione Haskell dalla sintassi dei casi, ma si spera abbastanza simili per voi!

Answer 2

Questo è il modo più 'Haskellian' mi viene in mente, l'unica cosa che manca è essere in grado di dichiarare più piccolo / grande come un 'dove' la clausola:

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

Lo so che non è parte della tua domanda, ma mi piacerebbe utilizzare List.partition di dividere la lista in più piccola / grande in un unico passaggio:

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

Answer 3

... Oppure si potrebbe fare una coda qsort ricorsiva utilizzando CPS:

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

Questo sembra essere il più conciso quanto si può ottenere (che unisce le idee da altre risposte, e l'utilizzo di strigliare per gli operatori):

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

Haskell 'dove' la sintassi, che consente di utilizzare il nome di una funzione prima della sua definizione, tipo di mappe a F # 'let rec ... e'

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

Answer 6

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 7

Non dimenticate che lista ha un metodo di partizione, quindi

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 8

avevo fatto alcune analisi di algoritmi di ordinamento in F # a pochi anni fa in uno stile molto imperativo; Stavo cercando di battere l'attuazione .NET magazzino, e sono riuscito a farlo href="http://fpish.net/topic/Some/0/57065" qui . Andò a fare la seguente risposta a me stesso di oggi, ma FPish non mi permette di creare un account. Argh! Devo fare il mio post da qualche parte, e qui è buono come ovunque, lol ...

Durante la lettura di "Impara È un Haskell Per gran bene" di ieri, l'autore impostare un esempio per l'attuazione Quicksort. La descrizione era abbastanza chiaro e anche prima ho avuto modo di codice di esempio, una soluzione ricorsiva elegante (in Haskell) spuntato nella mia testa. Immagino non avevo mai davvero avuto una sensazione intuitiva di come Quicksort fa la sua cosa, perché la soluzione banale è abbastanza facile, se non molto efficiente.

Qui è la mia versione 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 ]

E, l'equivalente Haskell (mi piace questo ... pulita!):

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 ]

Per sorrisi, ecco un altro F # versione (per lo più tail-ricorsiva) che è circa 2 volte la velocità della versione banale. Non hanno preso la briga di tempo questo contro il mio post originale, però, quindi nessuna idea come impila fino alla versione mutabili nel mio OP sul FPish.net (FSHub) da un paio di anni fa ...

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