ordenación rápida en Fa # - sintaxis pregunta

Question

Tengo una sencilla función de clasificación rápida f # define como:

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) 

¿Hay alguna manera en f # escribirlo más como 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] 

Sé que el El algoritmo f # falta un < = y> =. La pregunta es más sobre sintaxis/lectura.

Gracias.

Answer 1

usted quiere que su cláusula segundo partido sea x :: xs, y utilizar la @ (append) operador de donde su ejemplo Haskell utiliza ++:

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 

No es exactamente la misma que la definición Haskell por la sintaxis de los casos , pero espero lo suficientemente similar para ti!

Answer 2

Haskell 'donde' la sintaxis, que le permite usar el nombre de una función antes de su definición, tipo de mapas de f # 'let rec ... y'

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

Este es el más 'Haskellian' manera que se me ocurre, lo único que falta es ser capaz de declarar más pequeña/grande como 'dónde' cláusula:

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 

yo sé que no es parte de su pregunta, pero me gustaría utilizar List.partition dividir el enumere en más pequeño/más grande en una sola pasada:

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

Answer 4

Esto parece ser lo más concisos como se puede conseguir (que combina las ideas de otras respuestas, y el uso de ganarse a los operadores):

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

... o usted podría hacer una cola por qsort recursiva a través de CP:

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

no hay que olvidar que la lista tiene un método de partición, por lo

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

He hecho algunos análisis de algoritmos de clasificación en F # hace unos años en un estilo muy imperativo; Intentaba vencer a la implementación de stock de .NET y logré hacerlo al here. Fui a hacer la siguiente respuesta a mí mismo hoy, pero FPish no me deja crear una cuenta. Argh! Tengo que hacer mi publicación en alguna parte, y aquí está tan bien como en cualquier lugar, lol ...

Mientras leía "Aprende Haskell para un gran bien" ayer, el autor creó un ejemplo para implementar quicksort. La descripción fue bastante clara e incluso antes de llegar al código de muestra, una elegante solución recursiva (en Haskell) apareció en mi cabeza. Supongo que nunca había tenido una idea intuitiva de cómo Quicksort hace su trabajo, porque la solución trivial es bastante fácil, si no muy eficiente.

Aquí está mi versión de 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 ] 

Y, el equivalente Haskell (me gusta este ... limpio!):

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 ] 

para las muecas, aquí es otra versión # F (en su mayoría recursiva de cola) que se trata de la velocidad 2x de la versión trivial. No se han molestado en este momento contra mi post original, sin embargo, así que ni idea cómo se acumula hasta la versión mutable en mi OP en FPish.net (FSHub) desde hace unos años ...

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