Quicksort в F# - вопрос о синтаксисе
У меня есть простая 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# алгоритм отсутствует <= и> =. Вопрос больше о syntax/readibility.
Спасибо.
5 ответов
] Вы хотите, чтобы ваше второе условие совпадения было []x :: xs[], и чтобы вы использовали оператор @ (append), где ваш пример Haskell использует ++:[
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 по синтаксису кейсов, но, надеюсь, достаточно похожее для вас![
].Это самый "хаскеллианский" способ, единственное, чего мне не хватает, это возможности объявить меньшее/большее как пункт "где":
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
...Или можно сделать рекурсивный qsort хвоста с помощью 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
Это кажется настолько лаконичным, насколько это возможно (объединение идей из других ответов и использование карри для операторов):
let rec qsort = function
| [] -> []
| (x:int) :: xs ->
let smaller = List.filter ((>=) x) xs
let larger = List.filter ((<) x) xs
qsort smaller @ [x] @ qsort larger
haskell синтаксис 'where', который позволяет использовать имя функции до ее определения, своего рода карты f# 'let rec... and'
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