«Удаление» узла из функционального связанного списка

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)) 

Примечание: Я не программист на Лиспе, я не обязательно сделал это наилучшим образом.

[Изменить: Возможно, я неправильно истолковал, что вы имели в виду, удалив определенный узел. Если вы начинаете с суффиксом 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 оптимизацию хвостового вызова