Cвойство замыкания, на примере list

Все знают такую структуру в разных языках как список(однонаправленный). Многие даже знают, как происходит работа с ним в недрах компутера. Здесь я хотел бы показать это на пальцах. Воссоздав этот список искуственно.

Пример взят из Lisp и искусственно спроецирован на Python.
Для реализации конкретного уровня абстракции данных в Lisp имеется составная структура, называемая парой (pair), и она создается с помощью элементарной процедуры cons(мы вместо cons будем использовать кортеж из 2-х элементов). Эта процедура принимает два аргумента и возвращает объект данных, который содержит эти два аргумента в качестве частей. Имея пару, мы можем получить ее части с помощью элементарных процедур car и cdr.
*-Нравится статья? Кликни по рекламе! :)

Пары служат элементарным «клеем», с помощью которого можно
строить составные объекты данных. Сами пары способны соединять не только числа, но и другие пары. Как следствие этого, пары являются универсальным материалом, из которого можно строить любые типы структур данных.
Возможность создавать пары, элементы которых сами являются парами, определяет значимость списковой структуры как средства представления данных. Мы называем эту возможность свойством замыкания (closure property). В общем случае, операция комбинирования объектов данных обладает свойством замыкания в том случае, если результаты соединения объектов с помощью этой операции сами могут соединяться этой же операцией. Замыкание — это ключ к выразительной силе для любого средства комбинирования, поскольку оно позволяет строить иерархические (hierarchical) структуры, то есть структуры, которые составлены из частей, которые сами составлены из частей, и так далее.

Представление последовательностей
Одна из полезных структур, которые можно построить с помощью пар — это последовательность (sequence), то есть упорядоченная совокупность объектов данных. Разумеется, существует много способов представления последовательностей при помощи пар. Один, особенно простой, показан на рисунке ниже, где последовательность 1, 2, 3, 4 представлена как цепочка пар. В каждой паре car — это соответствующий член цепочки, а cdr — следующая пара цепочки. Представим это себе следующими функциями:

def car(l):
    return l[0];
def cdr(l):
    return l[1]

Cdr последней пары указывает на особое значение, не являющееся парой, которое на диаграммах изображается как диагональная линия, а в программах как значение переменной nil. Вся последовательность порождается несколькими вложенными операциями cons:

(1, (2, (3, (4, None))))

Такая последовательность пар, порождаемая вложенными cons-ами, называется список (list). В Python имеется тип, который называется list и помогает строить списки. Вышеуказанную последовательность можно было бы получить с помощью list([1, 2, 3, 4])(ну т.е. [1, 2, 3, 4], прошлое для выразительности=).
Значение nil(в Python None), которым завершается цепочка пар, можно рассматривать как последовательность без элементов, пустой список (empty list). Слово nil произошло от стяжения латинского nihil, что значит «ничто».

Операции со списками
Использованию пар для представления последовательностей элементов в виде списков сопутствуют общепринятые методы программирования. Например, процедура listRef берет в качестве аргументов список и число n и возвращает n-й элемент списка. Обычно элементы списка нумеруют, начиная с 0. Метод вычисления listRef следующий:

• Если n = 0, listRef должна вернуть car списка.
• В остальных случаях listRef должна вернуть (n −1)-й элемент от cdr списка.

def listRef(l, n):
    if n==0:
        return car(l)
    return listRef(cdr(l), n-1)

Часто мы просматриваем весь список. Чтобы помочь нам с этим, Python включает элементарный предикат is None, который определяет, является ли ее аргумент пустым списком.
Процедура length, которая возвращает число элементов в списке, иллюстрирует эту характерную схему использования операций над списками:

def length(l):
    if l is None:
        return 0
    return length(cdr(l))+1

Процедура length реализует простую рекурсивную схему. Шаг редукции таков:

• Длина любого списка равняется 1 плюс длина cdr этого списка. Этот шаг последовательно применяется, пока мы не достигнем базового случая.
• Длина пустого списка равна 0.

Мы можем вычислить length и в итеративном стиле:

def length(l):
    def lengthIter(a, count):
        if a is None:
            return count
        return lengthIter(cdr(a), count+1)
    return lengthIter(l, 0)

Еще один распространенный программистский прием состоит в том, чтобы «соединить» результат по ходу просмотра списка, как это делает процедура append, которая берет в качестве аргументов два списка и составляет из их элементов один общий список. Append также реализуется по рекурсивной схеме. Чтобы соединить списки list1 и list2, нужно сделать следующее:

• Если список list1 пуст, то результатом является просто list2.
• В противном случае, нужно соединить cdr от list1 с list2, а к результату
  прибавить car от list1 с помощью tuple:

def append(l1, l2):
    if l1 is None:
        return l2
    return (car(l1), append(cdr(l1), l2))

Крайне полезной операцией является применение какого-либо преобразования к каждому элементу списка и порождение списка результатов. Например, умножение каждого элемента списка на заданное число. Мы можем выделить общую идею и зафиксировать ее как схему, выраженную в виде процедуры высшего порядка. Здесь эта процедура
высшего порядка называется map. Map берет в качестве аргументов процедуру от одного аргумента и список, а возвращает список результатов, полученных применением процедуры к каждому элементу списка:

def map(proc, l):
    if l is None:
        return None
    return (proc(car(l)), map(proc,cdr(l)))

Используемая литература:

1. http://mitpress.mit.edu/sicp/