Как проектировать программы [Маттиас Фелляйзен] (pdf) читать постранично, страница - 118
- Как проектировать программы [Введение в программирование и компьютерные вычисления] (пер. А. Н. Киселев) 10.78 Мб, 726с. скачать: (pdf) - (pdf+fbd) читать: (полностью) - (постранично) - Маттиас Фелляйзен - Мэтью Флэтт - Роберт Брюс Финдлер - Шрирам Кришнамурти
Книга в формате pdf! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
List-of-numbers -> List-of-numbers
; упорядочивает элементы списка alon в порядке убывания
(check-expect (sort> '()) '())
(check-expect (sort> (list 3 2 1)) (list 3 2 1))
(check-expect (sort> (list 1 2 3)) (list 3 2 1))
(check-expect (sort> (list 12 20 -5))
(list 20 12 -5))
(define (sort> alon)
alon)
Теперь заголовок включает примеры, оформленные в виде модульных тестов, использующих list. Если применение этой функции вызывает у вас дискомфорт, то сформулируйте примеры с использованием cons, чтобы поупражняться в использовании разных форм запи
си. Два дополнительных примера требуют, чтобы sort> правильно
обрабатывала списки, уже отсортированные в порядке возрастания
и убывания.
Далее нужно преобразовать это определение данных в макет функции. Раньше мы уже имели дело со списками чисел, поэтому этот шаг
выполняется просто:
317
318
Глава 11
(define (sort> alon)
(cond
[(empty? alon) ...]
[else (... (first alon) ...
... (sort> (rest alon)) ...)]))
Используя этот макет, мы можем, наконец, перейти к самому интересному этапу разработки программы. Рассмотрим каждое условие
в cond отдельно, начав с наиболее простого случая. Если sort> получает
'(), то она должна вернуть '(), как определено в примере. Если sort>
получает непустой список, то этому случаю в макете соответствуют
два выражения:
zz (first alon) извлекает первое число из входного списка;
zz (sort> (rest alon)) сортирует (rest alon) в порядке убывания, со-
гласно описанию назначения функции.
Чтобы прояснить эти абстрактные ответы, воспользуемся вторым
примером и подробно исследуем его части. Когда sort> получает (list
12 20 -5),
1) (first alon) возвращает 12;
2) (rest alon) возвращает (list 20 -5);
3) (sort> (rest alon)) возвращает (list 20 -5), потому что этот список уже отсортирован.
Чтобы получить желаемый ответ, sort> должна вставить 12 между
двумя числами в последнем списке. Иначе говоря, мы должны найти
выражение, которое вставляет (first alon) в нужное место в результат
выражения (sort> (rest alon)). Если мы сможем это сделать, сортировка превратится в простую задачу.
Очевидно, что вставить число в отсортированный список непросто.
Требуется выполнить поиск по отсортированному списку, чтобы найти нужное место. Для поиска в любом списке нужна вспомогательная
функция, потому что списки имеют произвольный размер и, согласно
пункту 3 из предыдущего раздела, для обработки значений произвольного размера необходимо спроектировать вспомогательную функцию.
Добавим новую запись в список желаний:
; Число List-of-numbers -> List-of-numbers
; вставляет число n в отсортированный список чисел alon
(define (insert n alon) alon)
То есть insert получает число и список, отсортированный в порядке
убывания, и возвращает отсортированный список, в который в нужное место вставлено указанное число.
Имея функцию insert, мы с легкостью можем завершить определение sort>:
(define (sort> alon)
(cond
Проектирование методом композиции
[(empty? alon) '()]
[else
(insert (first alon) (sort> (rest alon)))]))
Чтобы получить окончательный результат, sort> извлекает первый элемент из непустого списка, получает отсортированную версию
оставшейся части списка и применяет insert для создания полного
отсортированного списка из двух частей.
Стоп! Протестируйте программу в текущем ее виде. Некоторые
тестовые примеры будут выполняться успешно, а некоторые нет.
Это прогресс. Следующий шаг – создание примеров применения
функции. Поскольку первым аргументом insert является произвольное число, мы используем значение 5 и определение данных
для списка чисел List-of-numbers, чтобы создать примеры для второго аргумента.
Сначала рассмотрим, что должна вернуть insert, получив число
и пустой список '(). Согласно описанию назначения функции insert,
результатом должен быть список, содержащий все числа из второго
аргумента и число из первого аргумента. То есть:
(check-expect (insert 5 '()) (list 5))
Далее используем непустой список с одним элементом:
(check-expect (insert 5 (list 6)) (list 6 5))
(check-expect (insert 5 (list 4)) (list 5 4))
И снова результат должен содержать все числа из списка во втором
аргументе и дополнительное число из первого аргумента. А кроме
того, результат должен быть отсортирован.
Наконец, создадим пример со списком во втором аргументе, содержащим более одного элемента. Мы можем получить такой пример из примеров для sort>. В частности, из нашего анализа второго
предложения cond мы знаем, что sort> должна вставить 12 в (list 20 -5)
в надлежащее место:
(check-expect (insert 12 (list 20 -5))
(list 20 12 -5))
То есть insert получает во втором аргументе список, который уже
отсортирован в порядке убывания.
Обратите внимание, чему нас учит развитие примеров. Функция
insert должна найти первое число, которое меньше заданного. Если
такого числа нет, то функция в конечном итоге достигнет конца спис
ка и должна добавить n в конец. Теперь, прежде чем перейти к макету,
создайте еще несколько примеров. Для этого вы можете использовать
дополнительные примеры для функции sort>.
В отличие от sort>, функция insert принимает два аргумента. Мы
знаем, что первый является числом и элементарным значением, по
этому
; упорядочивает элементы списка alon в порядке убывания
(check-expect (sort> '()) '())
(check-expect (sort> (list 3 2 1)) (list 3 2 1))
(check-expect (sort> (list 1 2 3)) (list 3 2 1))
(check-expect (sort> (list 12 20 -5))
(list 20 12 -5))
(define (sort> alon)
alon)
Теперь заголовок включает примеры, оформленные в виде модульных тестов, использующих list. Если применение этой функции вызывает у вас дискомфорт, то сформулируйте примеры с использованием cons, чтобы поупражняться в использовании разных форм запи
си. Два дополнительных примера требуют, чтобы sort> правильно
обрабатывала списки, уже отсортированные в порядке возрастания
и убывания.
Далее нужно преобразовать это определение данных в макет функции. Раньше мы уже имели дело со списками чисел, поэтому этот шаг
выполняется просто:
317
318
Глава 11
(define (sort> alon)
(cond
[(empty? alon) ...]
[else (... (first alon) ...
... (sort> (rest alon)) ...)]))
Используя этот макет, мы можем, наконец, перейти к самому интересному этапу разработки программы. Рассмотрим каждое условие
в cond отдельно, начав с наиболее простого случая. Если sort> получает
'(), то она должна вернуть '(), как определено в примере. Если sort>
получает непустой список, то этому случаю в макете соответствуют
два выражения:
zz (first alon) извлекает первое число из входного списка;
zz (sort> (rest alon)) сортирует (rest alon) в порядке убывания, со-
гласно описанию назначения функции.
Чтобы прояснить эти абстрактные ответы, воспользуемся вторым
примером и подробно исследуем его части. Когда sort> получает (list
12 20 -5),
1) (first alon) возвращает 12;
2) (rest alon) возвращает (list 20 -5);
3) (sort> (rest alon)) возвращает (list 20 -5), потому что этот список уже отсортирован.
Чтобы получить желаемый ответ, sort> должна вставить 12 между
двумя числами в последнем списке. Иначе говоря, мы должны найти
выражение, которое вставляет (first alon) в нужное место в результат
выражения (sort> (rest alon)). Если мы сможем это сделать, сортировка превратится в простую задачу.
Очевидно, что вставить число в отсортированный список непросто.
Требуется выполнить поиск по отсортированному списку, чтобы найти нужное место. Для поиска в любом списке нужна вспомогательная
функция, потому что списки имеют произвольный размер и, согласно
пункту 3 из предыдущего раздела, для обработки значений произвольного размера необходимо спроектировать вспомогательную функцию.
Добавим новую запись в список желаний:
; Число List-of-numbers -> List-of-numbers
; вставляет число n в отсортированный список чисел alon
(define (insert n alon) alon)
То есть insert получает число и список, отсортированный в порядке
убывания, и возвращает отсортированный список, в который в нужное место вставлено указанное число.
Имея функцию insert, мы с легкостью можем завершить определение sort>:
(define (sort> alon)
(cond
Проектирование методом композиции
[(empty? alon) '()]
[else
(insert (first alon) (sort> (rest alon)))]))
Чтобы получить окончательный результат, sort> извлекает первый элемент из непустого списка, получает отсортированную версию
оставшейся части списка и применяет insert для создания полного
отсортированного списка из двух частей.
Стоп! Протестируйте программу в текущем ее виде. Некоторые
тестовые примеры будут выполняться успешно, а некоторые нет.
Это прогресс. Следующий шаг – создание примеров применения
функции. Поскольку первым аргументом insert является произвольное число, мы используем значение 5 и определение данных
для списка чисел List-of-numbers, чтобы создать примеры для второго аргумента.
Сначала рассмотрим, что должна вернуть insert, получив число
и пустой список '(). Согласно описанию назначения функции insert,
результатом должен быть список, содержащий все числа из второго
аргумента и число из первого аргумента. То есть:
(check-expect (insert 5 '()) (list 5))
Далее используем непустой список с одним элементом:
(check-expect (insert 5 (list 6)) (list 6 5))
(check-expect (insert 5 (list 4)) (list 5 4))
И снова результат должен содержать все числа из списка во втором
аргументе и дополнительное число из первого аргумента. А кроме
того, результат должен быть отсортирован.
Наконец, создадим пример со списком во втором аргументе, содержащим более одного элемента. Мы можем получить такой пример из примеров для sort>. В частности, из нашего анализа второго
предложения cond мы знаем, что sort> должна вставить 12 в (list 20 -5)
в надлежащее место:
(check-expect (insert 12 (list 20 -5))
(list 20 12 -5))
То есть insert получает во втором аргументе список, который уже
отсортирован в порядке убывания.
Обратите внимание, чему нас учит развитие примеров. Функция
insert должна найти первое число, которое меньше заданного. Если
такого числа нет, то функция в конечном итоге достигнет конца спис
ка и должна добавить n в конец. Теперь, прежде чем перейти к макету,
создайте еще несколько примеров. Для этого вы можете использовать
дополнительные примеры для функции sort>.
В отличие от sort>, функция insert принимает два аргумента. Мы
знаем, что первый является числом и элементарным значением, по
этому
Последние комментарии
1 день 51 минут назад
1 день 5 часов назад
1 день 7 часов назад
1 день 9 часов назад
1 день 14 часов назад
1 день 15 часов назад