使用前向递归删除列表元素

Question

我正在编写一个程序，它删除适合谓词的第一个元素，例如。

remove' (fun x -> x = 2) [1;3;2;4;2] => [1;3;4;2]

问题是：正向递归怎么写？可能吗？使用尾递归，这不是问题。如果下一个元素不适合谓词，我只是将它们添加到 acc。

我在想

List.fold_right,

但也许有不同的方法来做到这一点？

Answer 1

没有"forward recursion"这样的东西。尾递归定义了一种特殊的递归，它发生在尾部位置。当你想引用一个不在尾部位置的递归时，你称它为"non tail recursive"

在您指定的代码中根本没有递归。所以，我建议你首先尝试编写 remove_if 函数并尝试弄清楚它是尾部还是非尾部。

更新

我通常尽量不为别人解决作业，但在这种情况下，我会通过为您提供 remove_if 函数的最常见定义来稍微启动一下：

 let rec remove matches = function
    | [] -> []
    | x :: xs when matches x -> remove matches xs
    | x :: xs -> x :: remove matches xs

这个函数中出现了两次递归：

| x :: xs when matches x -> remove matches xs
                            ^^^^^^^^^^^^^^^^^
                            last expression - 
                            tail recursion

| x :: xs -> x :: remove matches xs
                  ^^^^^^^^^^^^^^^^^
                  not the last - 
                  non tail recursive

因此，最后一个案例需要澄清一下：在 x 可以添加到 remove matches xs 的结果之前，需要评估后一个表达式。这意味着计算机需要将 x 存储在某处，以等到 remove matches xs 被计算。

所以，没有有趣的部分，你有一个非尾递归版本。现在，尝试递归地实现它。有fun！

Answer 2

ivg 解决方案对我帮助很大，但我需要对其进行一些升级。我的回答是：

 let remove' p xs =
   let rec remove_guard p xs g =
      match xs with 
        [] -> []
      | hd::tl -> if (p hd && g = 1) then remove_guard p tl 0 
                  else  hd::remove_guard p tl g
 in remove_guard p xs 1

也许不是最好的，但它只删除了一个元素。

感谢大家的帮助。非常感谢。

使用前向递归删除列表元素

Removing element of list with forward recursion

recursion

ocaml

functional-programming

更新