从功能链接lis中“删除”节点

Question

我正在寻找一个函数，它返回一个不包含特定节点的链表。你知道吗

下面是一个示例实现：

Nil = None                  # empty node

def cons(head, tail=Nil):
    """ Extends list by inserting new value. """
    return (head, tail)

def head(xs):
    """ Returns the frst element of a list. """
    return xs[0]

def tail(xs):
    """ Returns a list containing all elements except the first. """
    return xs[1]

def is_empty(xs):
    """ Returns True if the list contains zero elements """
    return xs is Nil

def length(xs):
    """                                                                                                                                                                               
    Returns number of elements in a given list. To find the length of a list we need to scan all of its                                                                               
    elements, thus leading to a time complexity of O(n).                                                                                                                              
    """
    if is_empty(xs):
        return 0
    else:
        return 1 + length(tail(xs))

def concat(xs, ys):
    """ Concatenates two lists. O(n) """
    if is_empty(xs):
        return ys
    else:
        return cons(head(xs), concat(tail(xs), ys))

如何实现remove_item函数？你知道吗

Answer 1

如果您想要尾部递归解决方案，可以说：

def remove_item(xs, value):
  before_rev, after = split_remove(Nil, xs, value)
  return reverse_append(before_rev, after)

def reverse_append(a, b):
  if is_empty(a):
    return b
  else:
    return reverse_append(tail(a), cons(head(a),b))

def split_remove(before_rev, xs, value):
  if is_empty(xs):
    return (before_rev, xs)
  elif head(xs) == value:
    return (before_rev, tail(xs))
  else:
    return split_remove(cons(head(xs), before_rev), tail(xs), value)

尽管我不知道Python是否进行了尾部调用优化

Answer 2

def remove_item(xs, value):
    if is_empty(xs):
        return xs
    elif head(xs) == value:
        return tail(xs) # or remove_item(tail(xs), value) to remove all
    else:
        return cons(head(xs), remove_item(tail(xs), value))

注意：我不是一个Lisp程序员，我不一定用最好的方法。你知道吗

[编辑：我可能误解了您删除特定节点的意思。如果以后缀xs开始，而不是以值xs开始，那么原理是相同的，但是涉及value的测试是不同的]