f# - F# 中的快速排序 - 语法问题

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