Простейшие абстракции данных. Список.

Задания в классе

Мы пойдем весьма необычным путём. В этом задании вы будете реализовывать последовательность(связный список) с помощью рекурсии и базового элемента tuple. Это отличается от классического связного списка, основанного на структуре и указателе next, когда обход бы делался с помощью for, пока не встретился бы null pointer.

Немного теории. Допустим у нас есть связная последовательность чисел

Её можно представить в виде последовательности вложенных друг в друга пар: seq=(1, (2, (3, 4))). Тогда чтобы взять последний элемент списка нужно сделать seq[1][1][1]. Или если создать специальную вспомогательную функцию tail: tail(tail(tail(seq))), что немного математичнее.

Использовать цикл for, while запрещено. Только рекурсия, только хардкор.

Можно использовать классы и переопределять операторы. Как делать классы можно прочитать тут или в официальной документации.

Тесты писать на все функции, чем больше, тем лучше. Проверяйте все граничные условия.

Hints

Вы можете использовать этот набор методов за основу рекурсивного списка. Далее можно в лоб реализовывать функции и не связываться с классами.

def head(pair):
    if pair is None:
        return None
    return pair[0]

def tail(pair):
    if pair is None:
        return None
    if len(pair) < 2:
        return None
    return pair[1]

def Seq(*elements):
    def first(x):
        return x[0]
    def other(x):
        return x[1:]

    if len(elements) == 0:
        return None

    if len(elements) == 1:
        return first(elements), None

    if len(elements) == 2:
        return first(elements), other(elements)

    return first(elements), Seq(*other(elements))

s = Seq(1,2,3,4,5)
s == (1, (2, (3, (4, (5,)))))
head(s) == 1
tail(s) == (2, (3, (4, (5,))))

Комментарий: ваш список должен уметь быть пустым, чтобы его длина была 0. Это потребуется в следующем задании.

Рекурсивно связная последовательность. Easy.

• взятие элемента по индексу at(seq(1,2,3), 1) == 2
• вычисление длины последовательности size(seq(1,2)) == 2
• сравнение массивов eq(seq(1,2), seq(1,2)) == Treu, eq(seq(1,2,3), seq(1,2)) == False

Функции над рекурсивно связаной последовательностью. Moderate.

• взятие хвоста последовательности, пропустив N значений, eq(tail(seq(1,2,3,4), 2), seq(3,4)) == True
• соединение двух списков eq(concat(seq(1,2), seq(3,4)), seq(1,2,3,4)) == True
• функция for_each для обхода списка for_each(seq(1,2,3,4), lambda x: print(x))