Практика 9

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

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

Мы пойдем весьма необычным путём. В этом задании вы будете реализовывать последовательность(связный список) с помощью рекурсии и базового элемента 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))
• функция for_each_indexed для обхода списка с индексом for_each(seq(1,2,3,4), lambda i, x: print(i, x))

Трансформаторы, фильтры, свёртки рекурсивных списков. Hard.

• функция преобразования map: map(seq(1,2,3,4), lambda x: x**2) == seq(1,4,9,16)
• функция фильтрации filter: filter(seq(1,2,3,4),lambda x: x%2==1) == seq(1,3)
• функция редуцирования reduce: reduce(s=seq(1,2,3,4), init_value=0, func=lambda acc, cur: acc+cur) == 0+1+2+3+4==10
• на основе функции редуцирования сделать функцию конвертации последовательности в python list list(seq(1,2,3,4)) == [1,2,3,4]

Дополнительное задание, если интересно:

• на основе функции редуцирования сделать функцию flat_map, которая превращает последовательность последовательностей в последовательность. flat_map(seq(1,2,3), lambda x: seq(x, x + 10)) == seq(1, 11, 2, 12, 3, 13)

Домашнее задание

Сделать как можно больше заданий. Например easy+moderate, hard+moderate. И так далее.

За помощью можете обратиться к книге “Структура и интерпретация компьютерных программ” и главе 2.2.