При выполнении заданий не используйте присваивание, циклы и обращение к элементам последовательности по индексу. Избегайте возврата логических значений из условных конструкций. Подготовьте примеры для демонстрации работы разработанных вами процедур.
Определите следующие процедуры для обработки списков:
(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-left quotient '(1)) ⇒ 1
(my-fold-right expt '(2 3 4)) ⇒ 2417851639229258349412352
(my-fold-right expt '(2)) ⇒ 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
Реализуйте библиотеку процедур для работы со строками. Реализуйте следующие процедуры:
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-prefix? "abcdef" "abc") ⇒ #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-infix? "bcd" "abc") ⇒ #f
(string-split "x;y;z" ";") ⇒ ("x" "y" "z")
(string-split "x-->y-->z" "-->") ⇒ ("x" "y" "z")
Реализуйте поддержку типа «многомерный вектор» — вектор произвольной размерности (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
; Индексы '(1 2 1 1) и '(2 1 1 1) — разные индексы
(multi-vector-set! m '(1 2 1 1) 'X)
(multi-vector-set! m '(2 1 1 1) 'Y)
(multi-vector-ref m '(1 2 1 1)) ⇒ X
(multi-vector-ref m '(2 1 1 1)) ⇒ Y
(define m (make-multi-vector '(3 5 7) -1))
(multi-vector-ref m '(0 0 0)) ⇒ -1
Реализуйте композицию функций (процедур) одного аргумента, для чего напишите
процедуру o, принимающую произвольное число процедур одного аргумента
и возвращающую процедуру, являющуюся композицией этих процедур.
Примеры применения процедуры:
(define (f x) (+ x 2))
(define (g x) (* x 3))
(define (h x) (- x))
((o f g h) 1) ⇒ -1
((o f g) 1) ⇒ 5
((o h) 1) ⇒ -1
((o) 1) ⇒ 1
Эти задачки решаются по желанию, в обязательную часть не входят.
flatten без использование функции append (или её аналога,
написанного вручную) — +1 балл.flatten без использование функции append (или её аналога,
написанного вручную), с хвостовой рекурсией — +2 балла.list-trim-right, удаляющую пробельные символы на конце списка,
без реверса этого списка (встроенной функции
reverse или её аналога, написанного вручную) — +1 балл.list-trim-right, удаляющую пробельные символы на конце списка,
без реверса этого списка (встроенной функции
reverse или её аналога, написанного вручную) и работающую со сложностью
O(len(xs)) — +2 балла.