從功能鏈表中「刪除」一個節點

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): 
    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測試不同]

Answer 2

如果你想要一個尾遞歸的解決方案，你可以說：

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是否會進行尾呼優化