使用仅含@和match with的递归函数实现OCaml列表扁平化遇栈溢出如何解决？

需求背景 #

需要编写一个递归函数实现列表扁平化，约束条件：

• 不能使用辅助函数
• 仅允许使用@运算符
• 必须采用match with语法

错误代码与问题分析 #

最初尝试的代码如下：

let rec flatten lst1 = match lst1 with 
  | [] -> []
  | hd::tl -> hd @ (flatten lst1);;

flatten [[3; 4]; [4; 5]];;

这段代码会触发栈溢出，核心原因是递归调用时传入的参数是原列表lst1，而非剩余未处理的tl。这会导致函数无限递归：每次进入hd::tl分支后，又重新处理整个原列表，永远无法触达基准情况[]，最终耗尽栈空间。

修正后的正确代码 #

将递归调用的参数改为tl，即可解决问题：

let rec flatten lst1 = match lst1 with 
  | [] -> []
  | hd::tl -> hd @ (flatten tl);;

flatten [[3; 4]; [4; 5]];;

修正后，每次递归处理的是列表的剩余部分tl，问题规模逐步缩小，最终会遇到空列表的基准情况，递归正常终止。运行上述测试代码，会得到正确结果[3; 4; 4; 5]。

内容的提问来源于stack exchange，提问作者J.B