Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 8
Текст из файла (страница 8)
Соглашения о правилахзаписи точечных пар позволяют также использовать и списочнуюнотацию:• точка, за которой непосредственно следует открывающая скобка, можетбыть опущена, так же опускаются открывающая и соответствующаязакрывающие скобки:(v1. (v2. (v3 .. .Vk.vk+1)(vk . vk+1)...)записывается в виде (v1 v2 . . .• точка, за которой непосредственно следует атом nil, также может бытьопущена, это относится и к атому nil:(v 1 v 2 ... V k .nil) записывается в виде (v 1 v 2 . . . v k )42Из этого следует, что значение выражения (cons a (cons b (cons сnil))) представляется структурой (a. (b. (с. nil))), которая может бытьпоследовательно сведена к структурам(а b .
(с . nil))( а b с . nil) ( а bс)Точечная запись используется в тех случаях, когда, например, необходимосослаться на первые два элемента списка произвольной длины. В записи(x1 х2 . у) X1 обозначает первый элемент, х2 - второй, у - оставшийсясписок.Графическое представление составных объектовОбъекты можно представлять в виде указателя на некоторый бокс. Бокспростого объекта содержит текстовое представление этого объекта.
Боксдля составного объекта (типа пара) - двойной. Левая часть содержитуказатель на первый элемент пары (саг пары), в правой части находитсяуказатель на второй элемент пары (cdr пары).Пара является универсальным составным типом для построения любыхструктур данных. Соответственно, объекты произвольно сложнойструктуры можно построить с помощью процедуры cons.Например,43Иерархические структурыСимвольное выражение можно представить в виде двоичного дерева. Еслиэлементы - атомы, то они являются листьями, если это точечные пары, тоони являются поддеревьями.
Рекурсия является естественным приемом дляобработки деревьев. Рассмотрим процедуру count-leaves, которая вкачестве результата выдает количество листьев в дереве. В отличие отпроцедуры length процедура count-leaves считает элементы-атомы навсех уровнях вложенности.(define x (cons (list 1 2)(length x)(count-leaves x)(list x x)4))(length (list x x))(count-leaves (list x x))(list 3 4) ) )-> 2-> 4-> ( ( (1 2) 3 4) ((1 2) 3-> 2-> 8Реализация процедуры count-leaves может опираться на следующиеутверждения.1.
Количество листьев в пустом дереве равно нулю.2. Количество листьев в дереве, состоящем из единственного атома, равноединице.3. Количество листьев в любом другом дереве может быть получено каксумма листьев правого (саг) и левого (cdr) поддеревьев.(define (count-leaves x)(cond ((null? x) 0)((atom? x) 1)(else (+ (count-leaves (car x))(count-leaves (cdr x))))))Упражнения11.Вычислите выражение (list l (list 2 (list 3 4) ) ) . Определитерезультат работы интерпретатора, а также приведите соответствующееграфическое представление структуры.12.Определите необходимые комбинации вызовов процедур саг и cdr, врезультате которых для данных списков можно будет получить элемент7.(1 3 (5 7) 9)((7))(1 (2 (3 (4 (5 ( 6 7 ) ) ) } ) )4413.
Пусть х и у определены как списки.(define x (list 1 2 3 ) )(define у (list 4 5 6 ) )Вычислите выражения:(append x у)(cons х у)(list x у)14.Модифицируйте процедуру reverse, так чтобы получить процедуруdeep-reverse, которая по заданному списку, с элементами любойструктуры, строит список, элементы которого расположены в обратномпорядке.
При этом если элементом списка является список, то вполученном списке элементы подсписка расположены также вобратном порядке. Например:(define x (list (list 1х->(reverse x)->(deep-reverse x)->2) (list 3 4 ) ) )( (1 2) (3 4))( (3 4) (1 2 ) )((4 3) (2 1 ) )15.Определите процедуру fringe, которая по дереву, заданному в видесписка, строит список, содержащий листовые элементы заданногодерева, расположенные слева направо.(define x (list (list 1 2) (list 3 4 ) ) )(fringe x)-> (1 2 3 4)(fringe (list x x) ) -> ( 1 2 3 4 1 2 3 4 )Процедуры высшего порядкаЧасто одни и те же схемы программ, отличающиеся друг от друга наборомиспользуемых процедур, могут быть использованы для решенияразличных задач. Для того чтобы определять такие схемы, необходимыпроцедуры, допускающие использование аргумента процедурного типа,или возвращающие значение типа процедура.
Процедуры, которыеиспользуют, таким образом, другие процедуры, называются процедурамивысшего порядка.Процедуры как аргументыРассмотрим следующие три примера процедур. Первая процедуравычисляет сумму целых чисел от а до b:(define (sum-integers a b)(if (> a b) 0 (+ a (sum-integers (+ a 1) b) ) ) )Вторая вычисляет сумму квадратов целых чисел на том же отрезке:(define (sum-squares a b)( i f (> a b) 0 ( + (square a) (sum-squares (+ а 1) b))) )Третья вычисляет сумму ряда: 1/1*3+1/5*7+1/9*11+ ...(define (pi-sum a b) (if (> a b) О ( + (/1.0 (* а ( + а2 ) ) ) (pi-sum (+ а 4) Ь) ) ) )Все три процедуры могут быть описаны одной общей схемой. Ониотличаются друг от друга только именем процедуры, способомвычисления слагаемого и определением следующего значения а.
Любая изних может быть получена из следующего конструктивного шаблона:(define (<name> a b)(if (> a b) 0 ( + (<term> a)(<name> (<next> a) b))))Математики для записи вычислений сумм используют /*знак суммы*/Eобозначения. В программировании концепция суммирования может бытьпредставлена в виде процедуры.(define (sum term a next b)(if (> a b) 0 ( + (term a)(sum (next a) b) ) ) )Процедура sum имеет 4 аргумента: нижнюю и верхнюю границусуммирования (а, b) и процедуры term и next. Процедуру sum можноиспользовать так же, как и все предшествующие.
Например, дляопределения описанных выше процедур суммирования.(define (inc n) (+ n 1))(define (sum-squares a b)(sum square a inc b))(define (identity x) x)(define (sum-integers a b)(sum identity a inc b))(define (pi-sum a b)(define (pi-term x) (/ 1.0 (* x (+ x 2)))))(define (pi-next x) (+ x 4)) (sum pi-term api-next b))46В качестве еще одного примера рассмотрим процедуру, котораяприбавляет единицу к каждому элементу списка, состоящего из чисел.(define (inc1-list x)(if (eq? x nil) nil(cons (+ (car x) 1)(incl-list (cdr x)))))Имеющая аналогичную структуру процедура mod2-list вычисляет поисходному списку х список остатков от деления каждого из его элементовна 2.(define (mod2-list x)(if (eq? x nil) nil(cons (mod (car x) 2)(mod2-list (cdr x)))))Определим обобщенную процедуру, в которой конкретная операция,которая выполняется над каждым элементом списка, является параметромэтой процедуры.(define (map x f)(if (eq? x nil) nil(cons (f (car x) 2)(map (cdr x)))))Можно переопределить процедуры inc-list и mod2-list через mapследующим образом:(define(define(define(define(inc1 x) (+ x 1) )(mod2 x) (mod x 2))(incl-list x) (map x incl))(mod2-list x) (map x mod2))Процедуры, которые используют другие процедуры в качестве аргументов,являются примерами процедур высшего порядка.
Разумное использованиепроцедур высшего порядка может привести к простой записи сложныхпрограмм.В качестве другого примера определим процедуру reduce со следующимипараметрами х - список, g - бинарная операция, а - константа.Процедура по списку (x1 x2 ... xk) вычисляет значение g(x1, g(x2 . . .g(xk, a) . . . ) ) . Например, (reduce x + 0) вычисляет сумму элементовсписка х.(define (reduce x g a)(if (eq? x nil) a(g (car x) (reduce (cdr x) g a ))))47Применяя эту функцию, можно определить операции суммирования ипроизведения:{define (sum x) (reduce x + 0))(define (mult x) (reduce x * 1)Еще одна процедура filter по заданному списку строит список,состоящий из элементов заданного списка, удовлетворяющихопределенному условию.(define (filter predicate sequence)(cond ((null? sequence) nil)((predicate (car sequence))(cons (car sequence)(filter predicate (car sequence))))(else (filter predicate (cdr sequence)))))Например:(filter odd? (list 1 2 3 4 5 ) )-> ( 1 3 5 ) Другойпример процедуры высшего порядка - процедура accumulate.(define (accumulate op initial sequence) (if (null?sequence) initial (op (car sequence) (accumulateop initial (cdr sequence)))))Примеры ее использования:(accumulate + 0 (list 1 2 3 4 5 ) )(accumulate * 1 (list 1 2 3 4 5 ) )(accumulate cons nil (list 1 2 3 4 5 ) )-> 15-> 120-> ( 1 2 3 4 5 )Упражнения16.Переопределите процедуры map, append, length, count-leaves Спомощью определенной выше процедуры accumulate.(define (map p sequence)(accumulate (lambda (x y) <??>) nil sequence)(define (append seql seq2)(accumulate cons <??> <??>))(define (length sequence)(accumulate <??> 0 sequence))48(define (count-leaves t)(accumulate <??> <??> (map <??> <??>)))17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
