Quicksort in F # - Syntax Question

Question

I have a simple f # quicksort function defined as:

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) 

Is there a way in f # to write it more like 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] 

I know that the f # algorithm is missing <= and> =. The question is more about syntax / readability.

Thanks.

Answer 1

You want your second match clause to be x :: xs , and to use the @ (append) operator, where your Haskell example uses ++:

 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 

This is not exactly the same as the Haskell definition for case syntax, but hopefully it will be pretty similar to you!

Answer 2

This is the most “Haskellian" way that I can think of, the only thing that is missing is to declare less / more as a "where" clause:

 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 

I know this is not part of your question, but I would use List.partition to split the list into smaller / larger in a single pass:

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

Answer 3

It looks as concise as it can (combining ideas from other answers and using currying for statements):

 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

haskell 'where' syntax that allows you to use the name of the function before defining it, the kind of maps in 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 

Answer 5

... Or you can do tail recursive qsort using 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

Remember that List has a split method, so

 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

A few years ago I did some analysis of sorting algorithms in F # in a very imperative style; I tried to defeat the implementation of .NET stocks and was able to do it here . Went today to answer this question, but FPish will not allow me to create an account. Argh! Gotta make my post somewhere, and here, like nowhere else, lol ...

While reading "Learn You a Haskell For Great Good" yesterday, the author created an example for implementing quicksort. The description was pretty clear, and even before I got into the code sample, an elegant recursive solution appeared in my head (in Haskell). I guess I never had an intuitive idea of ​​how quicksort does its job, because the trivial solution is quite simple, if not very effective.

Here is my version in 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 ] 

And, the equivalent of Haskell (I like this ... clean!):

 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 ] 

For grins, here is another version of F # (mostly tail recursive), which is about 2 times faster than the trivial version. Don't bother with the fact that this contradicts my original post, so don’t imagine how it stacks up with the volatile version of my OP on FPish.net (FSHub) a few years ago ...

 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