使用前向递归删除列表元素 [英] Removing element of list with forward recursion

问题描述

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

I'm writing a program which remove first element which fit to predicate eg.

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

问题是:如何用正向递归来写?是否可以?使用尾递归，这不是问题.如果它们不适合谓词，我只是将下一个元素添加到 acc.

and the problem is: how to write it with foward recursion? Is it possible? With tail recursion it is not a problem. I just add next elements to acc if they are not fit to predicate.

我在考虑

List.fold_right,

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

but maybe is there different way to do this?

推荐答案

没有前向递归"这样的东西.尾递归定义了一种特殊的递归，它发生在尾位置.当你想引用一个不在尾位置的递归时，你称之为非尾递归"

There is no such thing as "forward recursion". Tail recursion defines a special kind of recursion, that occurs in a tail position. When you want to refer to a recursion that is not in a tail position, you call it "non tail recursive"

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

In the code you've specified there is no recursion at all. So, I would suggest you first of all to try to write remove_if function and try to figure out whether it is tail or non-tail.

我通常会尽量不为别人解决家庭作业，但在这种情况下，我将通过为您提供remove_if函数的最常见定义来给你一个小启动:

I usually try no to solve homework for others, but at this case I will give a little kick start, by providing you with the most common definition of remove_if function:

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

此函数中出现了两次递归:

There are two occurrences of recursion in this function:

| 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 匹配 xs 的结果之前，需要评估后一个表达式.这意味着计算机需要将 x 存储在某处，以等待 remove matching xs 被评估.

So, last case needs some clarification: before the x can be prepended to the result of remove matches xs the latter expression needs to be evaluated. That means that computer needs to store x somewhere, to wait until remove matches xs is evaluatd.

所以，没有有趣的部分，你有一个非尾递归版本.现在，尝试以尾部递归方式实现它.玩得开心！

So, no the fun part, you have a non-tail recursive version. Now, try to implement it tail recursively. Have fun!

这篇关于使用前向递归删除列表元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！