追加两个列表

Question

所以这是附加两个列表的一种方法：

let rec append l1 l2 =
  match l1 with
  | h :: t -> h :: append t l2
  | [] -> l2

但我正在尝试编写追加版本的尾递归版本。 （在调用递归函数之前解决问题）。

这是我到目前为止的代码，但是当我尝试在第一个 if 语句中添加附加时，代码由于奇怪的原因而变得错误。

let list1 = [1;2;3;4]
let list2 = [5;6;7;8]

let rec append lista listb =
  match listb with
  | h :: taillist -> if taillist != []  then 
  begin 
    lista @ [h];
    (* I cant put an append recursive call here because it causes error*)
  end else
  append lista taillist;
 | [] -> lista;;

append list1 list2;;

Answer 1

将非尾递归列表算法转换为尾递归列表算法的最简单方法是使用累加器。考虑使用第三个列表重写代码，这将累积结果。使用 cons （即

::

）将新元素添加到第三个列表中，最终您将得到串联结果。接下来，您只需使用

List.rev

反转它即可。

Answer 2

为了完整起见，有一个尾递归

append

：

let append l1 l2 =
  let rec loop acc l1 l2 =
    match l1, l2 with
    | [], [] -> List.rev acc
    | [], h :: t -> loop (h :: acc) [] t
    | h :: t, l -> loop (h :: acc) t l
    in
    loop [] l1 l2

我建议解决99个问题来学习这个习语。

Answer 3

使用常量堆栈空间的版本，通过几个标准函数实现（展开定义后您将获得尾递归解决方案）：

let append xs ys = List.rev_append (List.rev xs) ys

顺便说一句，一些 OCaml 库以非常复杂的方式实现

append

函数： (1)参见Core_kernel库中的core_list0.ml：搜索“slow_append”和“count_append” (2) 或电池库中的batList.mlv。

Answer 4

对您的代码的一些评论：

1. 使用

   @

   定义列表追加函数似乎是作弊，因为这已经是一个追加两个列表的函数了:-)

2. 您的代码编写得就像 OCaml 是命令式语言一样；即，您似乎期望表达式

   lista @ [h]

   修改

   lista

   的值。但 OCaml 并不是这样工作的。 OCaml 中的列表是不可变的，并且

   lista @ [h]

   只是计算一个新值，而不更改任何先前的值。您需要在递归调用中传递这个新值。

正如@ivg所说，解决问题最直接的方法是使用累加器，最后使用列表反转。这是具有不可变列表的语言中的常见习惯用法。

Answer 5

利用延续的替代尾递归解决方案（F#）：

let concat x =
  let rec concat f = function
  | ([], x) -> f x
  | (x1::x2, x3) ->  concat (fun x4 -> f (x1::x4)) (x2, x3)
  concat id x

Answer 6

我认为最好的方法，就像有些人所说的那样，是反转第一个列表，然后递归地将头添加到 list2 的前面，但是带有代码的顶部注释使用累加器，当你可以获得相同的值时没有它的结果通过

::

到第二个列表而不是累加器

let reverse list =
  let rec reverse_helper acc list =
    match list with
    | [] -> acc
    | h::t -> reverse_helper (h::acc) t in
  reverse_helper [] lst;;

let append list1 list2 = 
  let rec append_helper list1_rev list2 =
    match list1_rev with
    | [] -> list2
    | h :: t -> append_helper t (h::lst2) in
  append_helper (reverse lst1) lst2;;

Answer 7

虽然 ivg 是正确的，即使用累加器可能是在常量堆栈空间中实现

append

的最简单方法，但连续传递是实现相同目的的另一种方法。

let append lst1 lst2 =
  let rec append' lst1 lst2 k =
    match lst1 with
    | [] -> k lst2
    | x::xs -> append' xs lst2 (fun i -> k (x :: i))
  in
  append' lst1 lst2 Fun.id

这里我们有

append'

将两个列表作为参数 和 一个函数。我们使用这个参数来构建一个能够实际完成工作的函数。直到我们达到退出条件（即第一个列表为空）之前，它实际上不会被调用。

让我们看一下如果我们使用“小”数据进行调用会发生什么情况：

append [1; 2] [3; 4]
append' [1; 2] [3; 4] Fun.id
append' [2] [3; 4] (fun i -> Fun.id (1 :: i))
append' [] [3; 4] (fun i -> (fun i -> Fun.id (1 :: i)) (2 :: i))
(fun i -> (fun i -> Fun.id (1 :: i)) (2 :: i)) [3; 4]
(fun i -> Fun.id (1 :: i)) (2 :: [3; 4])
Fun.id (1 :: 2 :: [3; 4])
1 :: 2 :: [3; 4]
[1; 2; 3; 4]

Answer 8

这是一个更简单的解决方案：

let rec apptr l k =
    let ln = List.rev l in
    let rec app ln k acc = match ln with
        | [] -> acc
        | h::t -> app t k (h::acc) in
    app ln k k
;;

Answer 9

另一种方法可以做到这一点，使用递归，而不使用

@

运算符：

let rec concat l1 l2 =
  match l1 with
  | [] -> l2
  | h :: t -> h :: concat t l2
;;

它很简单，并且具有线性复杂度，这取决于第一个列表的长度。

Answer 10

您的问题的可能答案可能是以下代码：

let append list1 list2 = 
 let rec aux acc list1 list2 = match list1, list2 with 
  | [], [] -> List.rev(acc)
  | head :: tail, [] -> aux (head :: acc) tail []
  | [], head :: tail -> aux (head :: acc) [] tail
  | head :: tail, head' :: tail' -> aux (head :: acc) tail (head' :: tail')
 in aux [] list1 list2;

它与您帖子中另一位评论者给出的代码非常相似，但这个更详尽，因为我添加了一个案例，说明 list2 从一开始就是空的，而 list1 不是空的