Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 26
Текст из файла (страница 26)
В отличие от Лиспа с его парами, вэтих языках нет встроенного универсального клея, который позволял бы легко работать с составными даннымиединым способом. Это ограничение дало Алану Перлису повод сказать в предисловии к этой книге: «В Паскале обилие объявляемых структур данных ведет к специализации функций, которая сдерживает и наказываетслучайное взаимодействие между ними.
Лучше иметь 100 функций, которые работают с одной структуройданных, чем 10 функций, работающих с 10 структурами».Глава 2. Построение абстракций с помощью данных1081234Рис. 2.4. Последовательность 1, 2, 3, 4, представленная в виде цепочки пар.(cons 1(cons 2(cons 3(cons 4 nil))))Такая последовательность пар, порождаемая вложенными cons-ами, называется список (list). В Scheme имеется примитив, который называется list и помогает строить списки8. Вышеуказанную последовательность можно было бы получить с помощью(list 1 2 3 4). В общем случае(list ha1 i ha2 i ... han i)эквивалентно(cons ha1 i (consha2 i (cons ... (cons han i nil) ...
)))По традиции, Лисп-системы печатают списки в виде последовательности их элементов,заключенной в скобки. Таким образом, объект данных с рисунка 2.4 выводится как (12 3 4):(define one-through-four (list 1 2 3 4))one-through-four(1 2 3 4)Внимание: не путайте выражение (list 1 2 3 4) со списком (1 2 3 4), которыйявляется результатом вычисления этого выражения. Попытка вычислить выражение (12 3 4) приведет к сообщению об ошибке, когда интерпретатор попробует применитьпроцедуру 1 к аргументам 1, 2, 3 и 4.Мы можем считать, что процедура car выбирает первый элемент из списка, а cdrвозвращает подсписок, состоящий из всех элементов, кроме первого.
Вложенные применения car и cdr могут выбрать второй, третий и последующие элементы списка9 .8 В этой книге термин список всегда означает цепочку пар, которая завершается маркером конца списка.Напротив, термин списковая структура (list structure) относится к любой структуре данных, составленнойиз пар, а не только к спискам.9 Поскольку записывать вложенные применения car и cdr громоздко, в диалектах Лиспа существуютсокращения — например,(cadr hаргi) = (car (cdr hаргi))У всех таких процедур имена начинаются с c, а кончаются на r. Каждое a между ними означает операциюcar, а каждое d операцию cdr, и они применяются в том же порядке, в каком идут внутри имени.
Именаcar и cdr сохраняются, поскольку простые их комбинации вроде cadr нетрудно произнести.2.2. Иерархические данные и свойство замыкания109Конструктор 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)(5 1 2 3 4)Значение nil, которым завершается цепочка пар, можно рассматривать как последовательность без элементов, пустой список (empty list). Слово nil произошло от стяжениялатинского nihil, что значит «ничто»10 .Операции со спискамиИспользованию пар для представления последовательностей элементов в виде списков сопутствуют общепринятые методы программирования, которые, работая со списками, последовательно их «у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)1610 Удивительно, сколько энергии при стандартизации диалектов Лиспа было потрачено на споры буквальнони о чем: должно ли слово nil быть обычным именем? Должно ли значение nil являться символом? Должноли оно являться списком? Парой? В Scheme nil — обычное имя, и в этом разделе мы используем его какпеременную, значение которой — маркер конца списка (так же, как true — это обычная переменная, значение которой истина).
Другие диалекты Лиспа, включая Common Lisp, рассматривают nil как специальныйсимвол. Авторы этой книги пережили слишком много скандалов со стандартизацией языков и хотели бы невозвращаться к этим вопросам. Как только в разделе 2.3 мы введем кавычку, мы станем обозначать пустойсписок в виде ’(), а от переменной nil полностью избавимся.110Глава 2. Построение абстракций с помощью данныхЧасто мы проcdrиваем весь список.
Чтобы помочь нам с этим, Scheme включает элементарную процедуру null?, которая определяет, является ли ее аргумент пустым списком.Процедура length, которая возвращает число элементов в списке, иллюстрирует этухарактерную схему использования операций над списками:(define (length items)(if (null? items)0(+ 1 (length (cdr items)))))(define odds (list 1 3 5 7))(length odds)4Процедура length реализует простую рекурсивную схему. Шаг редукции таков:• Длина любого списка равняется 1 плюс длина cdr этого спискаЭтот шаг последовательно применяется, пока мы не достигнем базового случая:• Длина пустого списка равна 0.Мы можем вычислить length и в итеративном стиле:(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.2. Иерархические данные и свойство замыкания111Упражнение 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 так, чтобы ее вторым аргументом был список монет, а нецелое число, которое указывает, какие монеты использовать.
Тогда у нас могли бы быть списки,определяющие типы валют:(define us-coins (list 50 25 10 5 1))(define uk-coins (list 100 50 20 10 5 2 1 0.5))Можно было бы вызывать cc следующим образом:(cc 100 us-coins)292Это потребует некоторых изменений в программе cc. Ее форма останется прежней, но со вторымаргументом она будет работать иначе, вот так:(define (cc amount coin-values)(cond ((= amount 0) 1)((or (< amount 0) (no-more? coin-values)) 0)(else(+ (cc amount(except-first-denomination coin-values))(cc (- amount(first-denomination coin-values))coin-values)))))Определите процедуры first-denomination, except-first-denomination и no-more? втерминах элементарных операций над списковыми структурами. Влияет ли порядок списка coinvalues на результат, получаемый cc? Почему?Глава 2.
Построение абстракций с помощью данных112Упражнение 2.20.Процедуры +, * и list принимают произвольное число аргументов. Один из способов определения таких процедур состоит в использовании точечной записи (dotted-tail notation). В определении процедуры список параметров с точкой перед именем последнего члена означает, что,когда процедура вызывается, начальные параметры (если они есть) будут иметь в качестве значений начальные аргументы, как и обычно, но значением последнего параметра будет список всехоставшихся аргументов. Например, если дано определение(define (f x y . z) hтелоi)то процедуру f можно вызывать с двумя и более аргументами. Если мы вычисляем(f 1 2 3 4 5 6)то в теле f переменная x будет равна 1, y будет равно 2, а z будет списком (3 4 5 6). Если даноопределение(define (g .
w) hтелоi)то процедура g может вызываться с нулем и более аргументов. Если мы вычислим(g 1 2 3 4 5 6)то в теле g значением переменной w будет список (1 2 3 4 5 6)11 .Используя эту нотацию, напишите процедуру same-parity, которая принимает одно илиболее целое число и возвращает список всех тех аргументов, у которых четность та же, что упервого аргумента. Например,(same-parity 1 2 3 4 5 6 7)(1 3 5 7)(same-parity 2 3 4 5 6 7)(2 4 6)Отображение списковКрайне полезной операцией является применение какого-либо преобразования к каждому элементу списка и порождение списка результатов. Например, следующая процедура умножает каждый элемент списка на заданное число.(define (scale-list items factor)(if (null? items)nil(cons (* (car items) factor)(scale-list (cdr items) factor))))(scale-list (list 1 2 3 4 5) 10)(10 20 30 40 50)11 Длятого, чтобы определить f и g при помощи lambda, надо было бы написать(define f (lambda (x y .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
