Tail Recursivity in F# : Inversions with Quicksort
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
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:
upper and lower parts lower part, when you are done with this continue by... lowerSorted and sort the upper part as well and continue with ... id function qsort and it's result will be the result of the current call 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) 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 The whole point to quicksort's swapping partition procedure is that it can mutate the same array; you just pass it the low and the high index of the array's range it has to process.
So make a nested function and pass it just the 2 indices. To make it tail recursive, add the third parameter, list-of-ranges-to-process; when that becomes empty, you're done. Wikibook says you mutate arrays with A.[i] <- A.[j] .
A nested function can access its parent function's argument directly, because it is in scope. So, make swap nested too:
let rec quicksort (A:int[]) =
let swap a b =
let tmp = A.[a]
A.[a] <- A.[b]
A.[b] <- tmp
let todo = ... (* empty list *)
let rec partition low high =
.... (* run the swapping loop,
find the two new pairs of indices,
put one into TODO and call *)
partition new_low new_high
let L = A.Length
match L with
| 1 -> (* do nothing A *)
| 2 -> count <- count + 1
if (A.[0]<A.[1]) then (* do nothing A *)
else (* [|A.[1];A.[0]|] *) swap 1 0
| x -> ....
partition 0 L
So partition will be tail recursive, working inside the environment set up for it by quicksort .
(disclaimer: I don't know F# and have never used it, but I know Haskell and Scheme, to some degree).
链接地址: http://www.djcxy.com/p/80532.html上一篇: F＃在尾递归和Seq库之间的性能差异