position - Lisp - 从位置移除

Question

我需要一个函数来删除起始列表和所有子列表中第 n 个位置的元素。我不需要工作代码，我只需要任何建议。

Answer 1

寻求建议而不是最终解决方案是值得称赞的。我会尽力向您解释。

单链表适合从头到尾进行递归处理。您可以使用便宜的操作来获取列表的第一个元素及其其余元素，并通过在前面放置一个新元素来构建列表。一个简单的递归方案是:从列表中取出第一个元素，用它做一些事情，然后把它放在结果的前面，用列表的其余部分重复整个过程。这种对连续元素和休息的过程的重复是递归部分。如果您有一个空的输入列表，则无事可做，并返回空列表，从而结束处理。这是你的基本案例、 anchor 或任何你想给它起的名字。请记住:递归案例、基本案例、检查——两者都需要。

(由于 Lisp 的求值规则，要将已处理的元素实际放在已处理的剩余部分之前，必须记住它，直到实际处理剩余部分，因为构建列表的操作会在返回新列表之前评估它的两个参数。这些中间结果将保存在堆栈中，这对于大列表来说可能是个问题。有一些方法可以避免这种情况，但我们将在这里保持简单。)

现在，您实际上不仅需要简单的列表，还需要树。方便的是，该树表示为一个嵌套列表，所以通常上面的内容仍然适用，除了一点点复杂:您将必须检查您要处理的元素本身是否是一个分支，即列表。如果是，则整个过程也必须在该分支上完成。

基本上就是这样。现在，要从树中删除一个元素，您的操作只是检查您的元素是否匹配，如果是，则删除它。更详细:

• 要从空列表中删除元素，只需返回一个空列表即可。

• 如果第一个元素本身是一个列表，则返回一个列表，该列表是从第一个元素构建的，并将所有匹配项作为其第一个删除，其余元素将所有匹配项作为其其余部分删除。

• 如果它的第一个元素匹配，则返回列表的其余部分匹配元素被移除。 (注意这里有些东西被“丢弃”了。)

• 否则，返回从第一个元素构建的列表作为它的第一个，并返回列表的其余部分，删除所有加工元素作为它的其余部分。

看看这个并尝试找到您的递归案例、基本案例以及处理嵌套树结构的内容。如果您了解所有这些，实现起来就会很容易。如果你从来没有真正学过这一切，而且你现在还没有头晕，那么就认为自己是天生的 Lisp 程序员。否则，递归只是一个基本概念，第一次可能难以掌握，但一旦点击，就像骑自行车一样。

Ed:不知何故错过了“位置”部分，并且误读了——尽管有问题标题。这就是疲劳对人的影响。

无论如何，如果你想按位置删除树中的元素，你可以让你的函数接受一个可选的计数器参数(或者你可以使用提供它的包装函数)。如果您查看以上几点，递归新分支将是您重置计数器的地方。基本的递归方案保持不变，但不是比较元素本身，而是检查计数器——如果它与您要删除的位置匹配，则删除该元素。在每个递归情况下，您都会将递增的计数器传递给您的函数，除非在进入新分支时重置它，即传递 0 作为您的计数器参数。 (您也可以在删除元素后只返回列表的其余部分，从而提高函数的性能，尤其是对于要删除靠近开头的元素的长列表，但我们在这里保持简单。)