我試圖通過使用排序串列演算法來理解 OCaml 中的深層嵌套遞回。出于這個原因，我正在跟蹤以下具有遞回函式sort并呼叫另一個函式的代碼insert。
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
我理解對 的第一次遞回呼叫sort，但之后我無法遵循。
例如，假設我們有 list [6, 2, 5, 3]。在tail將此串列排序為2,3,5代碼中的哪個位置之后，將head 6與此尾部的每個元素進行比較？有人可以提供跟蹤結果的提示嗎？
utop # sort [6; 2; 5; 3];;
> sort <-- [6; 2; 5; 3]
> sort <-- [2; 5; 3]
> sort <-- [5; 3]
> sort <-- [3]
> sort <-- []
> sort --> []
> insert <-- 3
> insert -->
> insert* <-- []
> insert* --> [3]
> sort --> [3]
> insert <-- 5
> insert -->
> insert* <-- [3]
> insert <-- 5
> insert -->
> insert* <-- []
> insert* --> [5]
> insert* --> [3; 5]
> sort --> [3; 5]
> insert <-- 2
> insert -->
> insert* <-- [3; 5]
> insert* --> [2; 3; 5]
> sort --> [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [3; 5]
> insert <-- 6
> insert -->
> insert* <-- [5]
> insert <-- 6
> insert -->
> insert* <-- []
> insert* --> [6]
> insert* --> [5; 6]
> insert* --> [3; 5; 6]
> insert* --> [2; 3; 5; 6]
> sort --> [2; 3; 5; 6]
>
> - : int list = [2; 3; 5; 6]**
uj5u.com熱心網友回復：
首先，沒有理由擁有insert和sort相互遞回，因為insert不依賴于sort. 所以你可以這樣寫：
let rec insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
現在，發生了insert什么？該函式嘗試elt在排序串列中插入一個元素，其不變性是它之前的所有元素都應該更小，之后的所有元素都應該更高。
發生兩種情況：
- 如果串列為空，則不變數 in 確保您是否只回傳一個包含您嘗試插入的元素的串列。
- 如果串列不是，它由我們將呼叫的元素和我們將呼叫
head的串列的其余部分組成tail。現在我們有兩個新案例：- 如果
elt <= head然后串列的所有元素都高于elt所以你只回傳elt :: list（例如，如果你打電話insert 1 [2; 3; 4]，你會回傳[1; 2; 3; 4] - 否則，
head < elt所以我們需要head在將通過插入eltto回傳的串列前面添加tail，因此遞回呼叫insert elt tail
- 如果
現在，當您呼叫 sort 時，您可以這樣稱呼它：
insert head (sort tail)
為什么這樣？因為僅當您嘗試將 head 插入的串列已排序時，不變數才有效（因此之前的粗體排序）。所以你需要tail在插入之前進行排序head。
如果您有以下串列：[3; 2; 1]，您將致電
insert 3 (sort [2; 1])
它被轉化為
insert 3 (insert 2 (sort [1]))
它被轉化為
insert 3 (insert 2 (insert 1 (sort [])))
這是解決的
insert 3 (insert 2 [1])
這是解決的
insert 3 [1; 2]
這是解決的
[1; 2; 3]
并且您的串列已排序。
[編輯]
這是帶有一些列印的代碼，以查看發生了什么：
let pp_sep ppf () = Format.fprintf ppf "; "
let rec insert elt lst =
Format.printf "@[<v 2>(Insert %d in [%a]" elt
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
lst;
let l =
match lst with
| [] -> [ elt ]
| head :: tail ->
if elt <= head then elt :: lst
else (
Format.printf "@,";
head :: insert elt tail)
in
Format.printf ")@]";
l
let rec sort (lst : int list) =
match lst with
| [] -> []
| head :: tail ->
Format.printf "@[<v 2>(Sort [%a] then insert %d@,"
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
tail head;
let l = insert head (sort tail) in
Format.printf ")@]@,";
l
# sort [3;2;1];;
(Sort [2; 1] then insert 3
(Sort [1] then insert 2
(Sort [] then insert 1
(Insert 1 in []))
(Insert 2 in [1]
(Insert 2 in [])))
(Insert 3 in [1; 2]
(Insert 3 in [2]
(Insert 3 in []))))
- : int list = [1; 2; 3]
uj5u.com熱心網友回復：
在按插入排序中，插入函式執行要插入的元素與當前排序串列之間的比較。您可以看到您的跟蹤以相反的順序插入串列的元素：
insert <-- 3
...
insert <-- 5
...
insert <-- 5
...
insert <-- 2
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
一個可能的下一步是弄清楚為什么insert以作為引數呼叫了四次，6并且僅以2作為引數呼叫了一次。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/470058.html