OCaml高效递归列表反转函数解析：双参数作用与执行过程问询

咱们先把这个函数的代码摆出来，方便对照：

(* val rev : ’a list -> ’a list -> ’a list *)
let rec rev l r = 
  match l with 
  | [] -> r 
  | (h::t) -> rev t (h::r)

函数签名与参数作用 #

首先看签名’a list -> ’a list -> ’a list：这是个多态函数，意思是它能处理任意类型的列表（不管是整数、字符串还是自定义类型），接受两个列表参数，最终返回一个列表。

再说说两个参数的核心职责：

• l：这是还没处理完的待反转列表。每次递归，我们都会把它的第一个元素（头部）摘出来，剩下的部分（尾部）继续传给下一次递归。
• r：这是已经完成反转的累积结果，你可以把它看成一个"临时收纳盒"。每次我们把l的头部元素放到这个盒子的最前面，慢慢就攒出了完整的反转列表。初始调用的时候，这个参数一般传空列表[]，因为一开始还没有任何反转元素。

递归执行逻辑（以[1;2;3]为例） #

要反转[1;2;3]，我们会调用rev [1;2;3] []，接下来一步步看递归的完整过程：

1. 第一次调用：rev [1;2;3] []

   • 匹配到l是h::t的形式，其中h=1，t=[2;3]
   • 执行递归调用：rev [2;3] (1::[]) → 也就是rev [2;3] [1]

2. 第二次调用：rev [2;3] [1]

   • 同样匹配h::t，h=2，t=[3]
   • 递归调用：rev [3] (2::[1]) → 也就是rev [3] [2;1]

3. 第三次调用：rev [3] [2;1]

   • 匹配h::t，h=3，t=[]
   • 递归调用：rev [] (3::[2;1]) → 也就是rev [] [3;2;1]

4. 第四次调用：rev [] [3;2;1]

   • 这次l是空列表，直接返回r的值[3;2;1]，递归结束。

为什么这个函数高效？ #

这是个尾递归函数——递归调用是函数执行的最后一步，OCaml会对尾递归做优化，不会因为列表太长导致栈溢出。对比那种用@拼接的非尾递归反转（比如let rec rev = function [] -> [] | h::t -> rev t @ [h]），这个版本每次都是O(1)的元素添加操作，整体时间复杂度是O(n)，效率高得多。

内容的提问来源于stack exchange，提问作者Erik Hansson