Tail Recursivity in F# : Inversions with Quicksort

Question

Hi i have some difficulty in understanding tail-recursivity. I know thats it's important to avoid infinite loops and also for memory usage. I've seen some examples on simple functions like Fibonacci in "Expert in F#", but I don't think i've seen code when the result is something different than just a number.

What would be the accumulator then ? i'm not sure...

Here is a recursive function that I've written. It counts the number of inversions in an array, using the quicksort algorithm. [it's taken from an exercise of the Coursera MOOC Algo I by Stanford]

I'd be grateful if somebody could explain how to make that tail recursive. [Also, i've translated that code from imperative code, as i had written that in R before, so the style is not functional at all...]

another question: is the syntax correct, A being a (mutable) array, i've written let A = .... everywhere ? is A <- .... better / the same ?

open System.IO
open System


let X = [|57; 97; 17; 31; 54; 98; 87; 27; 89; 81; 18; 70; 3; 34; 63; 100; 46; 30; 99;
    10; 33; 65; 96; 38; 48; 80; 95; 6; 16; 19; 56; 61; 1; 47; 12; 73; 49; 41;
    37; 40; 59; 67; 93; 26; 75; 44; 58; 66; 8; 55; 94; 74; 83; 7; 15; 86; 42;
    50; 5; 22; 90; 13; 69; 53; 43; 24; 92; 51; 23; 39; 78; 85; 4; 25; 52; 36;
    60; 68; 9; 64; 79; 14; 45; 2; 77; 84; 11; 71; 35; 72; 28; 76; 82; 88; 32;
    21; 20; 91; 62; 29|]

// not tail recursive. answer = 488

let N = X.Length

let mutable count = 0

let swap (A:int[]) a b =
    let tmp = A.[a]
    A.[a] <- A.[b]
    A.[b] <- tmp
    A

let rec quicksortNT (A:int[]) = 
    let L = A.Length


    match L with 
         | 1 -> A
         | 2 -> count <- count + 1
                if (A.[0]<A.[1]) then A 
                   else [|A.[1];A.[0]|]

         | x -> let p = x
                let pval = A.[p-1]
                let A = swap A 0 (p-1)
                let mutable i = 1
                for j in 1 .. (x-1) do 
                     if (A.[j]<pval) then let A = swap A i j
                                          i <- i+1
                // end of for loop

                // putting back pivot at its right place
                let A = swap A 0 (i-1)
                let l1 = i-1
                let l2 = x-i

                if (l1=0) then
                            let A =  Array.append [|A.[0]|] (quicksortNT A.[1..p-1])               
                            count <- count + (l2-1)
                            A
                     elif (l2=0) then 
                            let A = Array.append (quicksortNT A.[0..p-2]) [|A.[p-1]|]
                            count <- count + (l2-1)
                            A
                else
                            let A = Array.append ( Array.append (quicksortNT A.[0..(i-2)]) [|A.[i-1]|] ) (quicksortNT A.[i..p-1])
                            count <- count + (l1-1)+(l2-1)
                            A


let Y = quicksortNT X
for i in 1..N do printfn "%d" Y.[i-1]
printfn "count = %d" count

Console.ReadKey() |> ignore

Thank you very much for your help

Answer 1

As I said in my comment: you do inplace-swapping so it makes no sense to recreate and return arrays.

But as you ask about tail-recursive solutions look at this version using lists and continuation-passing-style to make the algorithm tail-recursive:

let quicksort values =
    let rec qsort xs cont =
        match xs with
        | [] -> cont xs
        | (x::xs) ->
            let lower = List.filter (fun y -> y <= x) xs
            let upper = List.filter (fun y -> y > x) xs
            qsort lower (fun lowerSorted ->
                qsort upper (fun upperSorted -> cont (lowerSorted @ x :: upperSorted)))
    qsort values id

---

remarks:

• you can think of it like this:
  • first partition the input into upper and lower parts
  • then start with sorting (recursively) the lower part, when you are done with this continue by...
  • ... take lowerSorted and sort the upper part as well and continue with ...
  • ... take both sorted parts, join them and pass them to the outer continuation
  • the outermost continuation should of course just be the id function
• some will argue that this is not quicksort as it does not sort inplace!
• maybe it's hard to see but it's tail-recursive as the very last call is to qsort and it's result will be the result of the current call
• I used List because the pattern-matching is so much nicer - but you can adopt this to your version with arrays as well
• in those cases (as here) where you have multiple recursive calls I always find cont-passing solutions to be easier to write and more natural - but accumulators could be used as well (but it will get messy as you need to pass where you are too)
• this will not take less memory than the version without the cont-passing at all - it just will be placed on the heap instead of the stack (you usually have way more heap available ;) ) - so it's a bit like cheating
• that's why the imperative algorithm is still way better performance-wise - so a usual compromise is to (for example) copy the array, use the inplace-algorithm on the copy and then return the copy - this way the algorithm behaves as if it's pure on the outside