Quicksort in F # - sintassi domanda

Question

Ho una semplice funzione di quick sort f # 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 # per 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 la Algoritmo f # manca un < = e> =. La domanda riguarda più la sintassi/la leggibilità.

Grazie.

Answer 1

volete che il vostro clausola secondo match di essere 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 definizione Haskell dalla sintassi dei casi , ma si spera abbastanza simile per te!

Answer 2

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 3

Questo è il più 'Haskellian' modo 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 

io so che non è parte della tua domanda, ma mi piacerebbe usare List.partition di dividere il elencare in caratteri più piccoli/più grandi in un'unica passata:

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

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

... Oppure si potrebbe fare una coda qsort ricorsiva che utilizzano 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 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

Ho fatto alcune analisi degli algoritmi di ordinamento in F # qualche anno fa in uno stile molto imperativo; Stavo cercando di battere l'implementazione di magazzino .NET e sono riuscito a farlo here. Sono andato a dare la seguente risposta a me stesso oggi, ma FPish non mi permetterà di creare un account. Argh! Devo rendere il mio post da qualche parte, e qui è buono come ovunque, lol ...

Durante la lettura di "Learn You a Haskell per Great Good" ieri, l'autore ha creato un esempio per implementare quicksort. La descrizione era abbastanza chiara e ancor prima di arrivare al codice di esempio, una elegante soluzione ricorsiva (in Haskell) mi è venuta in mente. Immagino che non abbia mai avuto una sensazione intuitiva per come quicksort fa la sua cosa, perché la soluzione banale è abbastanza facile, se non molto efficiente.

Ecco 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 qualche anno 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