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

Question

Tengo un simple f # función de clasificación rápida definida 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 una manera de 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 f # algoritmo le falta un <= y> =. La cuestión es más acerca de la sintaxis / legibilidad.

Gracias.

Answer 1

Usted quiere que su cláusula segundo partido sea x :: xs, y para usar el operador @ (agregar), donde sus Haskell ejemplo 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 lo mismo que la definición Haskell por la sintaxis de los casos, pero con suerte lo suficientemente similares para usted!

Answer 2

Esta es la forma más 'Haskellian' se me ocurre, lo único que falta es ser capaz de declarar más pequeña / grande como una cláusula where:

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 usar List.partition para dividir la lista en la más pequeña / 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 3

... O usted podría hacer una cola qsort recursiva mediante el uso de 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

Esto parece ser lo más concisos como se puede conseguir (que combina las ideas de otras respuestas, y el uso de currificación para 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

Haskell 'donde' la sintaxis, que le permite usar el nombre de una función antes de su definición, tipo de mapas de f # 'dejó 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 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, así

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

Me había hecho un poco de análisis de algoritmos de ordenación en Fa # hace unos años en un estilo muy imprescindible; Yo estaba tratando de vencer a la aplicación .NET de valores, y logró hacerlo aquí . Se fue a hacer la siguiente respuesta a mí mismo hoy, pero FPish no me deja crear una cuenta. Argh! Tengo que hacer mi puesto en alguna parte, y aquí es tan buena como en cualquier lugar, lol ...

Durante la lectura de "Aprender Eres una Haskell Para gran bien" ayer, el autor configurar un ejemplo de la aplicación de la clasificación rápida. La descripción era bastante clara e incluso antes de llegar al código de ejemplo, una solución elegante recursiva (en Haskell) vino a la cabeza. Supongo que en realidad nunca había tenido un sentido intuitivo de cómo quicksort hace su cosa, porque la solución trivial si no es muy fácil, muy eficiente.

Esta es 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 (I como éste ... 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í hay 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