(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? в терминах элементарных операций над списковыми структурами. Влияет ли порядок списка coin-values на результат, получаемый cc? Почему?

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

Процедуры +, * и list принимают произвольное число аргументов. Один из способов определения таких процедур состоит в использовании точечной записи (dotted-tail notation). В определении процедуры список параметров с точкой перед именем последнего члена означает, что, когда процедура вызывается, начальные параметры (если они есть) будут иметь в качестве значений начальные аргументы, как и обычно, но значением последнего параметра будет список всех оставшихся аргументов. Например, если дано определение

(define (f x y . z) (тело))

то процедуру f можно вызывать с двумя и более аргументами. Если мы вычисляем

(f 1 2 3 4 5 6)

то в теле f переменная x будет равна 1, y будет равно 2, а z будет списком (3 4 5 6). Если дано определение

(define (g . w) (тело))

то процедура g может вызываться с нулем и более аргументов. Если мы вычислим

(g 1 2 3 4 5 6)

то в теле g значением переменной w будет список (1 2 3 4 5 6).11

Используя эту нотацию, напишите процедуру same-parity, которая принимает одно или более целое число и возвращает список всех тех аргументов, у которых четность та же, что у первого аргумента. Например,

11 Для того, чтобы определить f и g при помощи lambda, надо было бы написать

(define f (lambda (x y . z) (тело))) (define g (lambda w (тело)))

(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)

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

(define (map proc items)

(if (null? items) nil

(cons (proc (car items))

(map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))

(10 2.5 11.6 17)

(map (lambda (x) (* x x))

(list 1 2 3 4)) (1 4 9 16)

Теперь мы можем дать новое определение scale-list через map:

12 Стандартная Scheme содержит более общую процедуру map, чем описанная здесь. Этот вариант map принимает процедуру от n аргументов и n списков и применяет процедуру ко всем первым элементам списков, всем вторым элементам списков и так далее. Возвращается список результатов. Например:

(map + (list 12 3) (list 40 50 60) (list 700 800 900)) (741 852 963)

(map (lambda (x y) (+ x (* 2 y)))

(list 1 2 3) (list 4 5 6)) (9 12 15)

(define (scale-list items factor) (map (lambda (x) (* x factor)) items))

Map является важным конструктом, не только потому, что она фиксирует общую схему, но и потому, что она повышает уровень абстракции при работе со списками. В исходном определении scale-list рекурсивная структура программы привлекает внимание к поэлементной обработке списка. Определение scale-list через map устраняет этот уровень деталей и подчеркивает, что умножение преобразует список элементов в список результатов. Разница между этими двумя определениями состоит не в том, что компьютер выполняет другой процесс (это не так), а в том, что мы думаем об этом процессе по-другому. В сущности, map помогает установить барьер абстракции, который отделяет реализацию процедур, преобразующих списки, от деталей того, как выбираются и комбинируются элементы списков. Подобно барьерам на рисунке 2.1, эта абстракция позволяет нам свободно изменять низкоуровневые детали того, как реализованы списки, сохраняя концептуальную схему с операциями, переводящими одни последовательности в другие. В разделе 2.2.3 такое использование последовательностей как способ организации программ рассматривается более подробно.

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

Процедура square-list принимает в качестве аргумента список чисел и возвращает список квадратов этих чисел.

(square-list (list 1 2 3 4))

(14 9 16)

Перед Вами два различных определения square-list. Закончите их, вставив пропущенные выражения:

(define (square-list items)

(if (null? items) nil

(cons (??) (??))))

(define (square-list items) (map (??) (??)))

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

Хьюго Дум пытается переписать первую из процедур square-list из упражнения 2.21 так, чтобы она работала как итеративный процесс:

(define (square-list items) (define (iter things answer)

(if (null? things)

answer

(iter (cdr things)

(cons (square (car things)) answer))))

(iter items nil))

К сожалению, такое определение square-list выдает список результатов в порядке, обратном желаемому. Почему?

Затем Хьюго пытается исправить ошибку, обменяв аргументы cons: