получить с помощью (list 1 2 3 4). В общем случае (list {a1) {a2) ... {an))

эквивалентно

(cons {a1) (cons{a2) (cons ... (cons {an) nil) ... )))

По традиции, Лисп-системы печатают списки в виде последовательности их элементов, заключенной в скобки. Таким образом, объект данных с рисунка 2.4 выводится как (1 2 3 4) :

(define one-through-four (list 12 3 4))

one-through-four (1 2 3 4)

Внимание: не путайте выражение (list 1 2 3 4) со списком (1 2 3 4) , который является результатом вычисления этого выражения. Попытка вычислить выражение (1 2 3 4) приведет к сообщению об ошибке, когда интерпретатор попробует применить процедуру 1 к аргументам 1, 2, 3 и 4.

Мы можем считать, что процедура car выбирает первый элемент из списка, а cdr возвращает подсписок, состоящий из всех элементов, кроме первого. Вложенные применения car и cdr могут выбрать второй, третий и последующие элементы списка.9 Конструктор cons порождает список, подобный исходному, но с дополнительным элементом в начале.

(car one-through-four)

1

(cdr one-through-four)

(2 3 4)

(car (cdr one-through-four))

2

(cons 10 one-through-four) (10 1 2 3 4)

(cons 5 one-through-four) (51234)

Значение nil, которым завершается цепочка пар, можно рассматривать как последовательность без элементов, пустой список (empty list). Слово nil произошло от стяжения латинского nihil, что значит «ничто».10

9Поскольку записывать вложенные применения car и cdr громоздко, в диалектах Лиспа существуют сокращения - например,

(cadr {ара)) = (car (cdr {ара)))

У всех таких процедур имена начинаются с с, а кончаются на r. Каждое a между ними означает операцию car, а каждое d операцию cdr, и они применяются в том же порядке, в каком идут внутри имени. Имена car и cdr сохраняются, поскольку простые их комбинации вроде cadr нетрудно произнести.

10Удивительно, сколько энергии при стандартизации диалектов Лиспа было потрачено на споры буквально ни о чем: должно ли слово nil быть обычным именем? Должно ли значение nil

Операции со списками

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

•Если n = 0, list-ref должна вернуть car списка.

•В остальных случаях list-ref должна вернуть (n - 1)-й элемент от cdr списка.

(define (list-ref items n)

(if (= n 0)

(car items)

(list-ref (cdr items) (- n 1))))

(define squares (list 1 4 9 16 25))

(list-ref squares 3)

16

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

(define (length items)

(if (null? items) 0

(+ 1 (length (cdr items)))))

(define odds (list 13 5 7))

(length odds) 4

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

•Длина любого списка равняется 1 плюс длина cdr этого списка

Этот шаг последовательно применяется, пока мы не достигнем базового случая:

•Длина пустого списка равна 0.

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

являться символом? Должно ли оно являться списком? Парой? В Scheme nil - обычное имя, и в этом разделе мы используем его как переменную, значение которой - маркер конца списка (так же, как true - это обычная переменная, значение которой истина). Другие диалекты Лиспа, включая Common Lisp, рассматривают nil как специальный символ. Авторы этой книги пережили слишком много скандалов со стандартизацией языков и хотели бы не возвращаться к этим вопросам. Как только в разделе 2.3 мы введем кавычку, мы станем обозначать пустой список в виде (), а от переменной nil полностью избавимся.

(define (length items)

(define (length-iter a count)

(if (null? a)

count

(length-iter (cdr a) (+ 1 count)))) (length-iter items 0))

Еще один распространенный программистский прием состоит в том, чтобы «сconsить» результат по ходу уcdrивания списка, как это делает процедура append, которая берет в качестве аргументов два списка и составляет из их элементов один общий список:

(append squares odds) (1 4 9 16 25 1 3 5 7)

(append odds squares)

(1 3 5 7 1 4 9 16 25)

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

•Если список list1 пуст, то результатом является просто list2.

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

(define (append list1 list2)

(if (null? list1) list2

(cons (car list1) (append (cdr list1) list2)))) Упражнение 2.17.

Определите процедуру last-pair, которая возвращает список, содержащий только последний элемент данного (непустого) списка.

(last-pair (list 23 72 149 34))

(34)

Упражнение 2.18.

Определите процедуру reverse, которая принимает список как аргумент и возвращает список, состоящий из тех же элементов в обратном порядке:

(reverse (list 1 4 9 16 25))

(25 16 9 4 1) Упражнение 2.19.

Рассмотрим программу подсчета способов размена из раздела 1.2.2. Было бы приятно иметь возможность легко изменять валюту, которую эта программа использует, так, чтобы можно было, например, вычислить, сколькими способами можно разменять британский фунт. Эта программа написана так, что знание о валюте распределено между процедурами first-denomination и count-change (которая знает, что существует пять видов американских монет). Приятнее было бы иметь возможность просто задавать список монет, которые можно использовать при размене.

Мы хотим переписать процедуру cc так, чтобы ее вторым аргументом был список монет, а не целое число, которое указывает, какие монеты использовать. Тогда у нас могли бы быть списки, определяющие типы валют: