尾递归zip函数

Question

我有一个名为 zip_with_2_fs 的函数。我试图使其尾部递归（zip_with_2_fs_tr），但我不太明白我在做什么。我是 Ocaml 新手，希望对尾递归和辅助函数有更深入的了解。

let rec zip_with_2_fs fx fy xs ys =
 match (xs, ys) with
  | ([], []) -> []
  | ([], _) -> []
  | (_, []) -> []
  | (xh::xt, yh::yt) -> (fx xh, fy yh)::zip_with_2_fs fx fy xt yt;;

我该如何解决这个问题？

let zip_with_2_fs_tr fx fy xs ys =
  let rec helper fxx fy xss yss =
    match (xs, ys) with
    | ([], []) -> []
    | ([], _) -> []
    | (_, []) -> []
    | (xh::xt, yh::yt) -> (fx xh, fy yh)::helper fx fy xt yt
  in helper fx fy xs ys;;

Answer 1

表达式

(fx xh, fy yh)::helper fx fy xt yt

不是尾递归，因为为了将其减少到一个值，您需要递归调用的结果。例如，让我们以更详细的方式重写它，只是为了给事物命名（当事物有名字时更容易谈论事物），

let head = (fx xh, fy yh) in
let tail = helper fx fy xt yt in (* recursive call *)
let result = head :: tail in
result

所以在这里，我们正在进行递归调用，并且当前调用的结果直到该调用返回才确定，因此我们的调用会累积（因为递归调用将进行自己的调用并等待结果准备好，依此类推） ）并且我们有宝贵的堆栈空间用于存储所有这些中间结果。

所以诀窍是递归调用的返回值应该是调用函数的结果。尾调用的概念实际上比尾递归调用更通用。由于任何其结果成为调用者结果的调用都称为尾部调用，并且可以在不扩展堆栈空间的情况下进行，例如，讲 C，

int bar(int x) {return x + 1; }
int foo(int x) {return bar(x+1);}

这里我们有一个从

foo

到

bar

的尾部调用，编译器只需跳转到

bar

就可以轻松实现它，而无需分配新的堆栈帧或传递从

bar 返回的值

.

回到 OCaml。所以我们需要确保我们的递归函数返回的值就是递归调用返回的值。但这里没有免费的午餐，因为我们需要一些空间来积累中间结果。在非尾递归函数版本中，它是程序堆栈。我们可以在递归调用期间显式创建一个值并在其中累积值，而不是程序堆栈，例如，

let zip_with_f_fs fx fy xs ys =
  let rec loop acc xs ys = match xs, ys with
    | [],[] -> List.rev acc
    | x::xs,y::ys -> loop ((fx x, fy y)::acc) xs ys
    | _  -> failwith "uneven lists" in
  loop [] xs ys

现在你可以看到我们有一个递归调用

loop

    | x::xs,y::ys -> loop ((fx x, fy y)::acc) xs ys

位于尾部位置，我们将结果存储在第一个名为

acc

的参数中，一旦到达两个列表的末尾，我们就反转它（因为我们假装它，实际上

acc

是我们的堆栈）以正确的顺序获取值。

Answer 2

作为补充说明，ivg所解释的累积在

List.fold_left2

中被抽象出来。

来自 Github 上的 list.ml：

let rec fold_left2 f accu l1 l2 =
  match (l1, l2) with
    ([], []) -> accu
  | (a1::l1, a2::l2) -> fold_left2 f (f accu a1 a2) l1 l2
  | (_, _) -> invalid_arg "List.fold_left2"

因此，您的函数可以通过将正确的更新函数传递给

List.fold_left2

来实现，该函数将

fx

和

fy

应用于适当的值，将它们构建成一个元组并将它们保存到累积列表中。

# let zip_with_f_fs fx fy xs ys =
    List.fold_left2 (fun i x y -> (fx x, fy y)::i) [] xs ys 
    |> List.rev;;
val zip_with_f_fs :
  ('a -> 'b) -> ('c -> 'd) -> 'a list -> 'c list -> ('b * 'd) list =
  <fun>

另请注意，虽然：

let rec zip_with_2_fs fx fy xs ys =
 match (xs, ys) with
  | ([], []) -> []
  | ([], _) -> []
  | (_, []) -> []
  | (xh::xt, yh::yt) -> (fx xh, fy yh)::zip_with_2_fs fx fy xt yt

不是尾递归，从 OCaml 4.14 及更高版本开始，以下 是。

let[@tail_mod_cons] rec zip_with_2_fs fx fy xs ys =
  match (xs, ys) with
  | ([], _) | (_, []) -> []
  | (xh::xt, yh::yt) -> (fx xh, fy yh)::zip_with_2_fs fx fy xt yt

连续传递样式也是将其转换为尾递归的一个选项。

let zip_with_2_fs f g x y =
  let rec aux x y k =
    match x, y with
    | ([], _) | (_, []) -> k []
    | x::xs, y::ys -> aux xs ys (fun i -> k @@ (f x, g y) :: i)
  in
  aux x y Fun.id