问将列表中的所有n项替换为给定的列表- ocaml

EN

我建议你先定义第二个函数。

::将允许我们在列表尾部递归运行函数所创建的列表前面添加x。

@会让我们连接两个列表，这样我们就可以将替代列表中的值插入到结果中。

let rec replace_value_with_list v sub lst =
  match lst with
  | [] -> []
  | x::xs when x <> v -> x :: replace_value_with_list v sub xs
  | x::xs -> sub @ replace_value_with_list v sub xs

第一个函数则要简单得多，它只是第二个函数的一个专门应用程序，将单个值放入列表中。

let replace_value v sub lst =
  replace_value_with_list v [sub] lst

这种实现的不利因素

我已决定编辑，以提及这一基础上的评论。以上不是尾递归.每次调用函数时，它都占用一定的堆栈空间。堆栈是有限的。递归调用一个或多个函数会导致堆栈溢出错误。

OCaml (和其他一些编程语言，主要是功能方面的语言)提供了尾叫优化。如果编译器能够确定一个函数做的最后一件事是调用自己还是另一个函数，那么调用者在堆栈上占用的空间就可以被重用。

我们可以从ealier修改现有的函数。

当x

replace_value_with_list v -> x :：replace_value_with_list v sub x::xs -> sub @ replace_value_with_list v sub时，让rec replace_value_with_list v sub = match lst与x [] -> [] xs：：xs <> v-> x::xs ->sub@replace_value_with_list sub xs匹配。

例如，此操作使函数非尾递归：

x :：replace_value_with_list诉sub

首先我们必须调用replace_value_with_list v sub xs，然后将x添加到它的前面。我们可以通过传递建立列表的累加器来解决这个问题。我们可以使用一个局部辅助函数来隐藏这个细节。由于本地函数正在处理递归，因此不再需要将replace_value_with_list标记为递归。

let replace_value_with_list v sub lst =
  let rec aux v sub lst acc =
    match lst with
    | [] -> List.rev acc
    | x::xs when x <> v -> aux v sub xs (x :: acc)
    | x::xs -> replace_value_with_list v sub xs (sub @ acc)
  in
  aux v sub lst []

请注意，当我们调用aux函数时，它将按照我们期望的方式以相反的顺序构建累加器，因此我们需要在退出条件下反转累加器。

但是，这仍然不是最优的，因为执行连接的@操作符不是尾递归的。我们可以通过将@替换为尾部递归的List.rev_append来克服这一问题。

let replace_value_with_list v sub lst =
  let rec aux v sub lst acc =
    match lst with
    | [] -> List.rev acc
    | x::xs when x <> v -> aux v sub xs (x::acc)
    | x::xs -> aux v sub xs (List.rev_append sub acc)
  in
  aux v sub lst []

这个迭代列表和积累值的过程就是折叠真正发光的地方。

let rvl v sub lst =
  List.(
    let f acc x = if x <> v then x::acc else rev_append sub acc in
    fold_left f [] lst |> rev
  )