home2.md

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

При выполнении заданий не используйте присваивание, циклы и обращение к элементам последовательности по индексу. Избегайте возврата логических значений из условных конструкций. Подготовьте примеры для демонстрации работы разработанных вами процедур.

1. Обработка списков

Определите следующие процедуры для обработки списков:

• Процедуру (my-range a b d), возвращающую список чисел в интервале [a, b) с шагом d.
• Процедуру my-flatten, раскрывающую вложенные списки.
• Предикат (my-element? x xs), проверяющий наличие элемента x в списке xs. Рекомендация: для проверки равенства элементов используйте встроенный предикат equal?.
• Предикат (my-filter pred? xs), возвращающий список только тех элементов списка xs, которые удовлетворяют предикату pred?.
• Процедуру (my-fold-left op xs) для левоассоциативной свертки списка xs с помощью оператора (процедуры двух аргументов) op.
• Процедуру (my-fold-right op xs) для правоассоциативной свертки списка xs с помощью оператора (процедуры двух аргументов) op.

Примеры вызова процедур:

(my-range  0 11 3) ⇒ (0 3 6 9)

(my-flatten '((1) 2 (3 (4 5)) 6)) ⇒ (1 2 3 4 5 6)

(my-element? 1 '(3 2 1)) ⇒ #t
(my-element? 4 '(3 2 1)) ⇒ #f

(my-filter odd? (my-range 0 10 1))
  ⇒ (1 3 5 7 9)
(my-filter (lambda (x) (= (remainder x 3) 0)) (my-range 0 13 1))
  ⇒ (0 3 6 9 12)

(my-fold-left  quotient '(16 2 2 2 2)) ⇒ 1
(my-fold-right expt     '(2 3 4))      ⇒ 2417851639229258349412352

2. Множества

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

• Процедуру (list->set xs), преобразующую список xs в множество.
• Предикат (set? xs), проверяющий, является ли список xs множеством.
• Процедуру (union xs ys), возвращающую объединение множеств xs и ys.
• Процедуру (intersection xs ys), возвращающую пересечение множеств xs и ys.
• Процедуру (difference xs ys), возвращающую разность множеств xs и ys.
• Процедуру (symmetric-difference xs ys), возвращающую симметричную разность множеств xs и ys.
• Предикат (set-eq? xs ys), проверяющий множества xs и ys на равенство друг другу.
• Примеры вызова процедур (порядок элементов множества не существенен):

(list->set '(1 1 2 3))                       ⇒ (3 2 1)
(set? '(1 2 3))                              ⇒ #t
(set? '(1 2 3 3))                            ⇒ #f
(set? '())                                   ⇒ #t
(union '(1 2 3) '(2 3 4))                    ⇒ (4 3 2 1)
(intersection '(1 2 3) '(2 3 4))             ⇒ (2 3)
(difference '(1 2 3 4 5) '(2 3))             ⇒ (1 4 5)
(symmetric-difference '(1 2 3 4) '(3 4 5 6)) ⇒ (6 5 2 1)
(set-eq? '(1 2 3) '(3 2 1))                  ⇒ #t
(set-eq? '(1 2) '(1 3))                      ⇒ #f

3. Работа со строками

Реализуйте библиотеку процедур для работы со строками. Реализуйте следующие процедуры:

• Процедуры string-trim-left, string-trim-right и string-trim, удаляющие все пробельные символы в начале, конце и с обеих сторон строки соответственно.
• Предикаты (string-prefix? a b), (string-suffix? a b) и (string-infix? a b), соответственно, проверяющие, является ли строка a началом строки b, окончанием строки b или строка a где-либо встречается в строке b.
• Процедуру (string-split str sep), возвращающую список подстрок строки str, разделенных в строке str разделителями sep, где sep — непустая строка. Т.е. процедура (string-split str sep) должна разбивать строку на подстроки по строке-разделителю sep.

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

Примеры вызова процедур:

(string-trim-left  "\t\tabc def")   ⇒ "abc def"
(string-trim-right "abc def\t")     ⇒ "abc def"
(string-trim       "\t abc def \n") ⇒ "abc def"

(string-prefix? "abc" "abcdef")  ⇒ #t
(string-prefix? "bcd" "abcdef")  ⇒ #f

(string-suffix? "def" "abcdef")  ⇒ #t
(string-suffix? "bcd" "abcdef")  ⇒ #f

(string-infix? "def" "abcdefgh") ⇒ #t
(string-infix? "abc" "abcdefgh") ⇒ #t
(string-infix? "fgh" "abcdefgh") ⇒ #t
(string-infix? "ijk" "abcdefgh") ⇒ #f

(string-split "x;y;z" ";")       ⇒ ("x" "y" "z")
(string-split "x-->y-->z" "-->") ⇒ ("x" "y" "z")

4. Многомерные вектора

Реализуйте поддержку типа «многомерный вектор» — вектор произвольной размерности (1 и более). Пусть элементы такого вектора хранятся не во вложенных векторах, а в едином одномерном векторе встроенного типа.

Реализуйте следующие процедуры:

• (make-multi-vector sizes) и (make-multi-vector sizes fill) для создания многомерного вектора. Число элементов в каждой размерности задается списком sizes. Второй вариант вызова процедуры позволяет заполнить все элементы значением fill. (multi-vector? m) для определения, является ли m многомерным вектором. Для вектора в общем случае (т.е. для такого, который не является представлением многомерного вектора) должна возвращать #f.

• (multi-vector-ref m indices) для получения значения элемента с индексами, перечисленными в списке indices.

• (multi-vector-set! m indices x) для присваивания значения x элементу с индексами, перечисленными в списке indices.

Примеры вызова процедур:

(define m (make-multi-vector '(11 12 9 16)))
(multi-vector? m)
(multi-vector-set! m '(10 7 6 12) 'test)
(multi-vector-ref m '(10 7 6 12)) ⇒ test

(define m (make-multi-vector '(3 5 7) -1))
(multi-vector-ref m '(0 0 0)) ⇒ -1

5. Композиция функций

Реализуйте композицию функций (процедур) одного аргумента, для чего напишите процедуру o, принимающую произвольное число процедур одного аргумента и возвращающую процедуру, являющуюся композицией этих процедур. Примеры применения процедуры:

(define (f x) (* x 2))
(define (g x) (* x 3))
(define (h x) (- x))

((o f g h) 1) ⇒ -6
((o f g) 1)   ⇒ 6
((o h) 1)     ⇒ -1
((o) 1)       ⇒ 1