为何我的OCaml尾递归compress函数被判定为非尾递归？

问题背景 #

我在解决99 OCaml问题的第8题，题目要求实现名为compress的函数，移除列表中的连续重复元素，测试用例如下：

assert (
  compress
    ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]
  = ["a"; "b"; "c"; "a"; "d"; "e"])

我的实现 #

我写出的解决方案：

let head = function x :: _ -> Some x | [] -> None

let compress list =
  let rec fn old_list new_list =
    match (old_list, new_list) with
    | h :: t, _ ->
        fn t (if Some h = head new_list then new_list else h :: new_list)
    | _ ->
        new_list
  in
  List.rev (fn list [])
;;

官方示例实现 #

题目提供的示例解决方案：

let rec compress = function
    | a :: (b :: _ as t) ->
        if a = b then compress t else a :: compress t
    | smaller ->
        smaller;;

我的疑问 #

我原本认为自己的实现是尾递归，应该比官方的非尾递归版本效率更高——毕竟官方版本里a :: compress t需要把a暂存在栈中。但用[@tailcall]属性测试时：

assert (
  (compress [@tailcall])
    ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]
  = ["a"; "b"; "c"; "a"; "d"; "e"])

编译器给出了“非尾递归”的警告。按我的理解，我的实现不需要在栈中保留任何状态，应该是尾递归才对，这是为什么？

补充说明 #

我还尝试把[@tailcall]直接加在fn上，写成List.rev ((fn [@tailcall]) list [])，但还是得到同样的警告。

问题解答 #

核心原因：[@tailcall]用错了对象 #

1. 外层compress函数并非尾递归：你给compress添加[@tailcall]属性，但compress的最后一步是执行List.rev (fn list [])——它需要先拿到fn的返回值，再调用List.rev处理结果，所以compress本身不是尾递归函数，编译器的警告完全正确。
2. 辅助函数fn才是尾递归：真正的尾递归部分是你定义的内部fn，它的所有递归调用都处于尾位置（函数的最后一步操作就是递归调用，没有后续计算）。你需要给fn内部的递归调用添加[@tailcall]来验证，而非外层的compress。

修改fn的递归调用处即可验证：

let compress list =
  let rec fn old_list new_list =
    match (old_list, new_list) with
    | h :: t, _ ->
        (fn [@tailcall]) t (if Some h = head new_list then new_list else h :: new_list)
    | _ ->
        new_list
  in
  List.rev (fn list [])
;;

此时编译器不会再给出尾递归警告，因为fn的递归调用确实符合尾递归要求。

额外优化建议 #

你的实现中用Some h = head new_list判断重复，其实可以直接比较元素，避免Option类型的构造与比较，让代码更简洁高效：

let compress list =
  let rec fn old_list new_list =
    match old_list with
    | [] -> new_list
    | h :: t ->
        match new_list with
        | [] -> fn t [h]
        | nh :: _ ->
            if h = nh then fn t new_list else fn t (h :: new_list)
  in
  List.rev (fn list [])
;;

内容的提问来源于stack exchange，提问作者Jay Mody