在 Ocaml 中跟踪嵌套递归

Question

我试图通过使用排序列表算法来理解 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]**

Answer 1

首先，没有理由让

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

发生了什么？该函数尝试在

sorted

列表中插入一个元素 elt，其不变条件是该元素之前的所有元素都应该更小，之后的所有元素都应该更高。

发生两种情况：

• 如果列表为空，则只要返回包含您尝试插入的元素的列表即可确保不变性。
• 如果列表不是，则它由我们称为

  head

  的元素和我们称为

  tail

  的列表的其余部分组成。现在我们有两个新案例：
  • if

    elt <= head

    那么列表中的所有元素都高于

    elt

    ，因此您只需返回

    elt :: list

    （例如，如果您调用

    insert 1 [2; 3; 4]

    ，您将返回

    [1; 2; 3; 4]

  • 否则，

    head < elt

    ，所以我们需要在通过将

    head

    插入到

    elt

    返回的列表前面添加

    tail

    ，因此递归调用

    insert elt tail

现在，当你调用 sort 时，你可以这样称呼它：

insert head (sort tail)

为什么会这样？因为只有当您尝试插入头的列表已排序时，不变式才起作用（因此之前的粗体已排序）。所以你需要先对

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]

Answer 2

在插入排序中，插入函数执行要插入的元素与当前排序列表之间的比较。 您可以看到跟踪以相反的顺序插入列表的元素：

 insert <-- 3                                                          
 ...
 insert <-- 5
 ...
 insert <-- 5
 ...
 insert <-- 2                                                           
 ...                                                          
 insert <-- 6                                                          
 ...
 insert <-- 6                                                          
 ...
 insert <-- 6                                                          
 ...
 insert <-- 6                                                          
 ...

下一步可能是弄清楚为什么以

insert

作为参数调用

6

四次，而以

2

作为参数只调用一次。