F# 中的尾递归：快速排序的反转

Question

嗨，我在理解尾递归方面有些困难。我知道避免无限循环和内存使用很重要。我在 "Expert in F#" 中看过一些简单函数的例子，比如斐波那契数列，但我认为我没有看到结果与数字不同的代码。

那么累加器是什么？我不确定...

这是我写的一个递归函数。它使用快速排序算法计算数组中的反转次数。 [取自斯坦福大学 Coursera MOOC Algo I 的练习]

如果有人能解释如何使尾部递归，我将不胜感激。 [此外，我已经从命令式代码翻译了该代码，就像我之前在 R 中编写的那样，所以这种风格根本不起作用...]

另一个问题：语法是否正确，A 是一个（可变）数组，我到处写 let A = ....？ A <- .... 更好/一样吗？

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

非常感谢您的帮助

Answer 1

正如我在评论中所说：你做 inplace-swapping 所以重新创建和 return 数组没有意义。

但是当你询问 tail-recursive 解决方案时，请查看此版本使用列表和 continuation-passing-style 来制作算法 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

备注：

你可以这样想：
- 首先将输入分成upper和lower部分
- 然后开始对 lower 部分进行（递归）排序，完成后继续...
- ... 取 lowerSorted 并对 upper 部分进行排序，然后继续 ...
- ... 取出两个排序的部分，加入它们并将它们传递给外部延续
- 最外层的延续当然应该只是id函数
有些人会争辩说这是不是快速排序，因为它没有就地排序！
可能很难看到，但它是 tail-recursive，因为最后一次调用是 qsort，它的结果将是当前调用的结果
我使用 List 是因为 pattern-matching 更好 - 但您也可以将其用于您的数组版本
在那些你有多个递归调用的情况下（如这里）我总是发现 cont-传递解决方案更容易编写和更自然 - 但也可以使用累加器（但它会得到凌乱，因为你也需要经过你所在的地方）
与完全没有 cont 传递的版本相比，这 不会占用更少的内存 - 它只会被放置在堆上而不是堆栈上（你通常有更多可用的堆 ;) ) - 所以这有点像作弊
这就是为什么命令式算法仍然更好 performance-wise - 所以通常的妥协是（例如）复制数组，使用 inplace-algorithm 在副本上然后 return 副本 - 这样算法表现就好像它在外面是纯粹的

Answer 2

快速排序的交换分区过程的全部意义在于它可以改变同一个数组；您只需将它必须处理的数组范围的低索引和高索引传递给它。

所以制作一个 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 表示你用 A.[i] <- A.[j].

改变数组

嵌套函数可以直接访问其父函数的参数，因为它在范围内。因此，也使 swap 嵌套：

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

因此 partition 将是尾递归的，在 quicksort 为其设置的环境中工作。

（免责声明：我不了解 F# 也从未使用过它，但我在某种程度上了解 Haskell 和 Scheme）。

F# 中的尾递归：快速排序的反转

Tail Recursivity in F# : Inversions with Quicksort

recursion

f#

quicksort

tail-recursion

mutable

备注：