Quicksort in F# - syntax question

Question

I have a simple f# quick sort 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 the f# algorithm is missing a <= and >=. The question is more about syntax/readibility.

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

It's not quite the same as the Haskell definition by cases syntax, but hopefully similar enough for you!

Answer 2

This is the most 'Haskellian' way I can think of, the only thing missing is being able to declare smaller/larger 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 it's not part of your question, but I'd use List.partition to split the list in 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

...Or you could make a tail recursive qsort by 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 4

This seems to be as concise as it can get (combining the ideas from other answers, and using currying for operators):

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

haskell 'where' syntax, which lets you use the name of a function before its definition, kind of maps to 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 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

Don't forget that List has a partition 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

I had done some analysis of sorting algorithms in F# a few years ago in a very imperative style; I was trying to beat the .NET stock implementation, and managed to do so here. Went to make the following reply to myself today, but FPish won't let me create an account. Argh! Gotta make my post somewhere, and here's as good as anywhere, lol...

While reading "Learn You a Haskell For Great Good" yesterday, the author set up an example for implementing quicksort. The description was quite clear and even before I got to the sample code, an elegant recursive solution (in Haskell) popped into my head. Guess I had never really had an intuitive feel for how quicksort does its thing, because the trivial solution is quite easy, if not very efficient.

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 Haskell (I like this one... 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's another F# version (mostly tail-recursive) that's about 2x the speed of the trivial version. Haven't bothered to time this against my original post, though, so no idea how it stacks up to the mutable version in my OP on FPish.net (FSHub) from 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