F#中的Quicksort - 语法问题

Question

我有一个简单的f#快速排序功能,定义如下:

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)

在f#中是否有一种方法可以像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]

我知道f#算法缺少<=和> =.问题更多的是语法/可读性.

谢谢.

Answer 1

这是我能想到的最"Haskellian"方式,唯一缺少的是能够将较小/较大的声明声明为'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

我知道这不是你问题的一部分,但是我会List.partition在一次传递中以较小/较大的方式拆分列表:

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

Answer 2

你想要你的第二个匹配子句x :: xs,并使用你的Haskell示例使用++的@(append)运算符:

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

它与案例语法中的Haskell定义并不完全相同,但希望对您来说足够相似!

Answer 3

这似乎是尽可能简洁(结合其他答案的想法,并为运营商使用currying):

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 4

...或者您可以使用CPS进行尾递归qsort：

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