OCaml嵌套列表扁平化：为何用x::acc后反转而非acc@[x]？

问题背景 #

我正在完成OCaml习题集的第7题，题目基于以下嵌套列表类型定义：

type 'a node =
  | One of 'a 
  | Many of 'a node list

需要实现一个flatten函数来扁平化该嵌套列表，示例断言如下：

assert (
  flatten [ One "a"; Many [ One "b"; Many [ One "c"; One "d" ]; One "e" ] ]
  = [ "a"; "b"; "c"; "d"; "e" ])

网站提供的解决方案为：

let flatten list =
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t
    | Many l :: t -> aux (aux acc l) t
  in
  List.rev (aux [] list)
;;

疑问 #

为什么该方案采用x :: acc构建列表后再调用List.rev反转，而非直接用acc @ [x]来避免最终的反转操作？

解答 #

核心原因是性能差异：

• x :: acc是OCaml列表的原生高效操作，它只需要创建一个新的列表节点，时间复杂度为O(1)，几乎没有额外开销。
• 而acc @ [x]属于列表拼接操作，它需要完整遍历一遍acc列表才能把新元素追加到末尾，时间复杂度是O(n)（n为acc的当前长度）。如果在递归过程中每次都用@拼接，随着列表元素增多，整体时间复杂度会退化为O(n²)，处理较大的嵌套列表时性能会急剧下降。

用x :: acc先把元素逆序收集到累加器中，最后只需要执行一次O(n)的List.rev反转操作，整体时间复杂度保持为O(n)，比全程用@高效得多。这种"先逆序收集再统一反转"的写法是OCaml处理列表时的常用优化技巧，既保证了性能，代码逻辑也清晰易懂。

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