Домашнее задание № 7

Для выполнения задания найди ссылку-приглашение в онлайн чате, получи доступ к репозиторию с файлом-заготовкой и заполни пропуски в нём. Фиксируй изменения (делай коммиты) после решения каждой задачи. Оставь название файла неизменным, иначе робот-проверятель не найдёт твои ответы. Отправить решения на GitHub нужно до истечения установленного срока.

Интерпретатор Scheme уже находится в репозитории — файл scheme. Для запуска используй:

python3 scheme

Для загрузки в интерпретатор файла (например, hw_07.scm) используй

python3 scheme -load hw_07.scm

Вопрос 1

Определи процедуры cadr и caddr, которые возвращают второй и третий элементы списка соответственно:

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

(define (caddr s)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

В этот раз тесты tests.py отделены от кода hw_07.scm. Тесты оформлены доктестами на Python, хоть и тестируют Scheme-код.

python3 -m doctest tests.py

Условные выражения

Специальная форма cond — это обобщенное условное выражение, похожее на условное выражение в Python с несколькими предложениями. Обобщенное условное выражение выглядит так:

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <выражение-else>))

Оно состоит из символа cond, за которым следуют пары выражений (<p> <e>), называемые предложениями. Первое выражение в каждой паре — предикат (выражение, значение которого интерпретируется как true или false).

В Scheme все значения, за исключением специального булевого значения False (исторически называемого #f) интерпретируются как истинные. Также существует булево значение True (исторически называемого #t). В твоей версии Scheme False и #f могут использоваться взаимозаменяемо.

Условные выражения обрабатываются следующим образом. Сначала вычисляется значение предиката <p1>. Если его значение ложно (false), то вычисляется <p2>. Если значение <p2> также ложно, то вычисляется значение <p3>. Этот процесс продолжается, пока не будет найден предикат со значением true. После этого интерпретатор возвращает значение соответствующего выражения <e> в качестве результата всего условного выражения. Если ни один из предикатов <p> не имеет значение true, интерпретатор возвращает значение <выражение-else> в качестве результата всего условного выражения.

Слово «предикат» используется как для процедур, возвращающих true или false, так и для выражений.

Вопрос 2

Используя выражение cond, определи процедуру sign, которая принимает один параметр x и возвращает -1 при отрицательном аргументе, 0 при нулевом и 1 при положительном:

(define (sign x)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

Вопрос 3

Реализуй процедуру pow для возведения числа b в целую неотрицательную степень n, которая имеет временной порядок роста \(\Theta (\log n)\).

Обдумай вот что:

\(b^{2k} = (b^k)^2\)
\(b^{2k+1} = b(b^k)^2\)

Используй встроенные предикаты even?, odd? и процедуру square.

(define (square x) (* x x))

(define (pow b n)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

Вопрос 4

Напиши процедуру (предикат) ordered?, которая принимает список чисел и возвращает true, если числа расположены в неубывающем порядке, иначе false. Предикат — это процедура, результат выполнения которой либо true, либо false. Неубывающий порядок означает, что каждый следующий элемент больше или равен предыдущего. То есть 1 2 3 3 4 ` — не убывает, `1 2 3 3 2 — убывает.

тебе может пригодиться встроенный предикат null?, который проверяет аргумент на равенство nil.

(define (ordered? s)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

Множества на упорядоченных списках

Множество — это коллекция, которая содержит уникальные элементы. Основная операция для коллекции — проверка принадлежности элемента множеству.

Встроенного в Scheme типа данных для представления множеств не существует, однако одним из способов организации множества является представление его упорядоченным списком (упорядочивание нужно, чтобы вычисление объединений union и перечислений intersection были проще). Следующие вопросы развивают эту идею. Таким образом, представляй множество упорядоченным от меньшего к большему списком без повторяющихся элементов.

Вопрос 5

Сперва определи процедуру add, которая принимает множество s и значение v. Процедура должна возвращать представление множества, содержащее все элементы исходного s вместе со значением v. Результат не должен содержать одинаковые элементы.

(define (empty? s) (null? s))

(define (add s v)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

Вопрос 6

Теперь определи процедуру contains?, которая проверяет принадлежность значения v множеству s. Реализация этой процедуры на Python приведена для удобства.

(define (contains? s v)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)

Вопрос 7

Наконец, создай процедуру intersect (пересечение), которая возвращает множество элементов, входящих одновременно и в множество s, и в множество t.

Также определи процедуру union (объединение), которая возвращает множество элементов, принадлежащих любому из множеств s или t.

Реализация обеих процедур должна требовать линейного времени от длины исходных множеств.

(define (contains? s v)
  ; ТВОЙ КОД ЗДЕСЬ
  nil
)