在 Ocaml 中跟踪嵌套递归
trace a nested recursion in Ocaml
我试图通过使用排序列表算法来理解 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 的第一个递归调用，但之后我无法理解。
例如，假设我们有列表[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]**
在插入排序中，是插入函数执行要插入的元素与当前排序列表之间的比较。
您可以看到您的跟踪以相反的顺序插入列表的元素：
insert <-- 3
...
insert <-- 5
...
insert <-- 5
...
insert <-- 2
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
下一步可能是弄清楚为什么 insert 以 6 作为参数被调用四次而以 2 作为参数仅被调用一次。
首先，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，其不变性是它之前的所有元素都应该更小，而之后的所有元素都应该更高。
两种情况发生：
- 如果列表为空，则不变量确保您 return 包含您尝试插入的元素的列表。
- 如果列表不是，则它由一个我们称为
head 的元素和我们称为 tail 的列表的其余部分组成。现在我们有两个新案例：
- if
elt <= head 然后列表的所有元素都高于 elt 所以你只是 return elt :: list （例如如果你调用 insert 1 [2; 3; 4]你会 return [1; 2; 3; 4]
- 否则，
head < elt 所以我们需要在将 return 插入 elt 到 tail 的列表前面添加 head，因此递归调用 insert elt tail
现在，当您调用 sort 时，您可以这样调用它：
insert head (sort tail)
为什么会这样？因为仅当您尝试将 head 插入其中的列表已排序时，不变式才有效（因此之前进行了粗体排序）。所以你需要在插入 head 之前对 tail 进行排序。
如果您有以下列表：[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]
我试图通过使用排序列表算法来理解 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 的第一个递归调用，但之后我无法理解。
例如，假设我们有列表[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]**
在插入排序中，是插入函数执行要插入的元素与当前排序列表之间的比较。 您可以看到您的跟踪以相反的顺序插入列表的元素：
insert <-- 3
...
insert <-- 5
...
insert <-- 5
...
insert <-- 2
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
下一步可能是弄清楚为什么 insert 以 6 作为参数被调用四次而以 2 作为参数仅被调用一次。
首先，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，其不变性是它之前的所有元素都应该更小，而之后的所有元素都应该更高。
两种情况发生：
- 如果列表为空，则不变量确保您 return 包含您尝试插入的元素的列表。
- 如果列表不是，则它由一个我们称为
head的元素和我们称为tail的列表的其余部分组成。现在我们有两个新案例：- if
elt <= head然后列表的所有元素都高于elt所以你只是 returnelt :: list（例如如果你调用insert 1 [2; 3; 4]你会 return[1; 2; 3; 4] - 否则，
head < elt所以我们需要在将 return 插入elt到tail的列表前面添加head，因此递归调用insert elt tail
- if
现在，当您调用 sort 时，您可以这样调用它：
insert head (sort tail)
为什么会这样？因为仅当您尝试将 head 插入其中的列表已排序时，不变式才有效（因此之前进行了粗体排序）。所以你需要在插入 head 之前对 tail 进行排序。
如果您有以下列表：[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]