使用递归函数进行 CCaml 列表扁平化

Question

我正在尝试使用递归函数来压平不允许使用辅助函数的列表。我只能用@。我正在尝试使用“匹配”

我试过这个方法

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

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

结果是堆栈溢出

（我刚刚将

flatten lst1

换成

flatten tl

，它可以工作。谢谢）

Answer 1

不要忽略编译器警告：

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

|  |hd::tl -> hd @ (flatten lst1);;
        ^^
Warning 27 [unused-var-strict]: unused variable tl.

Answer 2

您可以使用相同的列表来提供递归函数。尝试用尾部调用递归函数

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

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

> [3; 4; 4; 5]

Answer 3

你甚至不需要

@

。只需使用

::

即可完成。您只需要处理三个条件：

• 该列表完全是空的。这为您的递归提供了退出情况。
• 列表中的第一个元素是一个空列表，在这种情况下，您只需展平列表的尾部即可。
• 第一个元素不是空列表。在这种情况下，您可以将第一个元素限制在展平嵌套列表其余部分的结果上。

let rec flatten lst =
  match lst with
  | [] -> []
  | []::tl -> flatten tl
  | (x::xs)::tl -> x :: flatten (xs :: tl)

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

应用

tail_mod_cons

，这可以成为尾递归，不需要任何辅助函数。