使用Ocaml对列表中的交换元素使用Ocaml

Question

我是Ocaml初学者，无法理解尾递归或列表迭代。我们如何迭代列表是2s并交换对？

let rec swap = function 
| a :: (b :: _ as t) -> b::a::swap t | smaller -> smaller;; 
let newlist = swap [1;2;3;4];; 
List.iter print_int newlist; 

例如，1234，交换功能被交换1和2，然后将列表头仍处于2，和其交换2和3，而它应该是在3和交换3和4

Answer 1

你正在尝试在swap做的应该是

let rec swap = function 
    | a :: b :: tail -> b :: a :: (swap tail) 
    | whatever -> whatever 

这样你交换的头两个元素之后那些东西进行。

但是，这里有一个问题。让我们看看会发生什么，比方说，在swap [1; 2; 3; 4; 5; 6]呼叫的情况：

1. swap被称为与[1; 2; 3; 4; 5; 6]
2. a与1匹配，b 2匹配，...

.. ..2.1。 swap被称为[3; 4; 5; 6]

.... 2.2。在此第二次通话中a与3匹配，b与4匹配，并且...

........ 2.2.1。 swap叫[5; 6]

........ 2.2.2。在此第三通电话内a与5匹配，b与6匹配，并且...

............ 2.2.2.1。 swap被称为[]（空列表）

............ 2.2.2.2。此呼叫返回空列表

........ 2.2.3。 ......它是在以前swap呼叫拿起添加b和a到它的开始，生产6 :: 5 :: []或​​

........ 2.2.4。这是返回

.... 2.3。 ......它是在以前swap呼叫拿起增加（自己的）b和a到它的开始，生产4 :: 3 :: [6; 5]或[4; 3; 6; 5]

.... 2.4。这是返回

1. ...并且在以前swap呼吁增加（自己的）b和a到它的开始回升，生产2 :: 1 :: [4; 3; 6; 5]或[2; 1; 4; 3; 6; 5]
2. 被返回作为最终结果

注意如何整条产业链的swap呼叫有在两个方向上进行行进：

呼叫1，swap [1; 2; 3; 4; 5; 6] =>呼叫2，swap [3; 4; 5; 6] =>调用3，swap [5; 6] =>调用4，swap []，返回[]，现在回到=>调用3，返回​​=>致电2，返回[4; 3; 6; 5] =>致电1，返回[2; 1; 4; 3; 6; 5]。

这意味着程序在整个过程中“停止”，它应该保留前一个路径在内存中，以便它可以返回。如果你的列表是200万条记录，那么整个路径将是100万条记录，并且应该保存在记忆中。如果你运行这样的事情，你将会用完堆栈空间。

如何解决这个问题？通常的技术是使用某种“累加器”。

let rec swap_helper acc = function 
    | a :: b :: tail -> swap_helper (a :: b :: acc) tail 
    | a :: [] -> a :: acc 
    | [] -> acc ;; 

let swap2 lst = List.rev (swap_helper [] lst) 

这些功能是什么？我们试着看看如果我们打电话swap2 [1; 2; 3; 4; 5; 6]会发生什么。它从呼叫swap_helper [] [1; 2; 3; 4; 5; 6]开始。

1. a与1匹配，b与2相匹配，tail与[3; 4; 5; 6]匹配，所以我们称之为swap_helper [1; 2] [3; 4; 5; 6]。但是，瞧！当下一次调用返回时，我们没有做任何结果，因此没有理由返回 - 编译器会生成代码，以立即返回我们将在swap_helper [1; 2] [3; 4; 5; 6]中得到的结果，而不会返回原始代码 - 因为在原来的调用中没有任何结果。 这叫做尾部呼叫优化。

2. 现在我们在swap_helper [1; 2] [3; 4; 5; 6]通话，这样a与3相匹配，b与4匹配和tail与[5; 6]匹配，所以我们称之为未来swap_helper [3; 4; 1; 2] [5; 6]又一次没有什么离开后，这样做，所以我们不会再回到这里了！

3. 那么，swap_helper [3; 4; 1; 2] [5; 6]调用。这里a是5,b是6,tail是[]。我们前往swap_helper [5; 6; 3; 4; 1; 2] []，我们是而不是了，因为没有什么可做的了！

4. swap_helper [5; 6; 3; 4; 1; 2] []打比赛的最后一案，并立即返回[5; 6; 3; 4; 1; 2] - 但不是任何中间swap_helper电话，他们已经忘记了，没有工作，那些剩下要做的 - 而是直接到原swap2来电！

现在swap2我们扭转我们从swap_helper列入清单，并让我们的[2; 1; 4; 3; 6; 5]，根据需要。

所以，重复一遍：在这段代码中，当swap_helper自己调用时，没有什么可以做的，所以没有理由返回，所以没有理由花费内存来记住“回头路”，因为我们不会去回去。在原始代码中，我们无法做到这一点，因为swap正在自行调用，并且在准备就绪后仍然必须将a和b粘贴到第二次调用的结果。