Quicksort w F # - składnia zapytania

Question

Mam proste F # funkcję szybkiego sortowania zdefiniowana jako:

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) 

Czy istnieje sposób w F #, aby napisać to bardziej jak 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] 

Wiem f # algorytm brakuje < = i> =. Pytanie dotyczy raczej składni/czytelności.

Dzięki.

Answer 1

Chcesz, aby Twoja druga klauzula mecz będzie x :: xs i użyć @ (dołącz) operator gdzie przykładem Haskell wykorzystuje ++:

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 

To nie całkiem tak samo jak definicja Haskell przez przypadki składni , ale mam nadzieję, że jest wystarczająco podobny dla ciebie!

Answer 2

Haskell „gdzie”, składnia, która pozwala na korzystanie z nazwy funkcji przed jej definicji, rodzaj mapy do F # „let rec ... i”

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

Jest to najbardziej „Haskellian” sposób mogę myśleć, jedyną rzeczą, której brakowało jest w stanie zadeklarować mniejsze/większe jako „gdzie” klauzuli:

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 

wiem, że to nie jest część twojego pytania, ale użyję List.partition o podziale lista w mniejszych/większych w jednym przebiegu:

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

Answer 4

To wydaje się być tak zwięzłe, jak to może dostać (łączenie pomysłów od innych odpowiedzi, a przy użyciu currying dla operatorów):

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

... Albo można zrobić ogon rekurencyjnej qsort przez wykorzystujące 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

nie zapomnij tej listy ma metodę partycji, więc

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

Zrobiłem kilka analiz algorytmów sortowania w F # kilka lat temu w bardzo imperatywnym stylu; Próbowałem pobić wdrożenie platformy .NET i udało mi się to zrobić here. Postąpiłem dzisiaj, aby odpowiedzieć sobie na pytanie, ale FPish nie pozwoli mi założyć konta. Argh! Muszę zrobić gdzieś mój posterunek, a tutaj jest tak dobrze, jak wszędzie, lol ...

Podczas czytania "Learn You a Haskell For Great Good" wczoraj, autor ustanowił przykład wdrożenia quicksort. Opis był dość jasny i zanim dotarłem do przykładowego kodu, w mojej głowie pojawił się elegancki, rekursywny roztwór (w Haskell). Chyba nigdy nie miałem intuicyjnego wyczucia tego, jak działa quicksort, ponieważ trywialne rozwiązanie jest dość łatwe, jeśli nie bardzo wydajne.

Oto moja wersja w 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 ] 

A, odpowiednik Haskell (mi się podoba ... czyste!)

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 ] 

Na grins tu inna wersja # C (przeważnie ogon rekurencyjne), który znajduje się około 2 x prędkość wersji trywialne. Nie przeszkadzało do czasu tego przeciwko mojego oryginalnego postu, choć, więc nie wiem jak to stosy aż do wersji zmienny w moim OP na FPish.net (FSHub) od kilku lat temu ...

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