在 oCaml 中将一个列表附加到另一个列表

Question

我需要一个尾递归函数，将 list1 附加到 list2 前面。

我试过这样

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

append [1;3;4] [3;4;2] [];;

但结果每次都是“超时”

Answer 1

你有无限递归，因为你没有更新

lst1

。当你评估你的测试用例时：

append [1;3;4] [3;4;2] []
append [1;3;4] [3;4] (1 :: [])
append [1;3;4] [3;4] (1 :: 1 :: [])

这将永远运行，这解释了你的“超时”问题。

您需要更新

lst1

。例如

let rec append lst1 lst2 acc = 
  match lst1 with 
  | [] -> acc @ lst2
  | hd::tl -> append tl lst2 (hd::acc)

append [1;3;4] [3;4;2] []
append [3;4] [3;4;2] (1 :: [])
append [4] [3;4;2] (3 :: 1 :: [])
append [] [3;4;2] (4 :: 3 :: 1 :: [])
[4;3;1] @ [3;4;2]
[4;3;1;3;4;2]

但这是不对的。你需要考虑一下你的逻辑。 OCaml 中的列表是单链表。

[1; 3; 4]

相当于

1 :: 3 :: 4 :: []

并且

[1; 3; 4; 3; 4; 2]

是

1 :: 3 :: 4 :: 3 :: 4 :: 2 :: []

。

您只需将第一个列表中的

[]

替换为

[3; 4; 2]

即可。其基本形式如下：

let rec append lst1 lst2 =
  match lst1 with
  | [] -> ...
  | hd::tl -> hd :: append ... ...