---

% Лабораторная работа № 1Б. Рекурсия, процедуры высшего порядка, обработка списков
% <лабораторная ещё не сдана>
% Кирилл Меньшиков, ИУ9-12/6

Цель работы

Приобретение навыков работы с основами программирования на языке Scheme: использование рекурсии, процедур высшего порядка, списков.

Индивидуальный вариант

1. Реализовать процедуру "(uniq xs)", удаляющую из списка "xs" соседние дубликаты.
2. Реализовать процедуру "(delete pred? xs)", удаляющую из списка "xs" все элементы, удовлетворяющие предикату "pred?".
3. Реализовать процедуру "(polynom (an ... a1 a0) x)", вычисляющую значение полинома.
4. Реализовать процедуру "(intersperse e xs)", вставляющую элемент "e" между элементами списка "xs".
5. Реализовать предикат "(all? pred? xs)", проверяющий, удовлетворяют ли все элементы списка "xs" предикату "pred?".
6. Реализовать процедуру "(o ...)", создающую композицию процедур одного аргумента.

Реализация

1. Процедура "uniq"

Процедура удаляет только соседние повторяющиеся элементы списка.

(define (uniq xs)
  (cond ((null? xs) '())
        ((null? (cdr xs)) xs)
        ((equal? (car xs) (cadr xs))
         (uniq (cdr xs)))
        (else
         (cons (car xs)
               (uniq (cdr xs))))))

2. Процедура "delete"

Процедура удаляет все элементы списка, для которых переданный предикат возвращает "#t".

(define (delete pred? xs)
  (cond ((null? xs) '())
        ((pred? (car xs))
         (delete pred? (cdr xs)))
        (else
         (cons (car xs)
               (delete pred? (cdr xs))))))

3. Процедура "polynom"

Для вычисления полинома используется схема Горнера.

(define (polynom coeffs x)
  (define (iter xs acc)
    (if (null? xs)
        acc
        (iter (cdr xs)
              (+ (* acc x) (car xs)))))
  (iter coeffs 0))

4. Процедура "intersperse"

Процедура вставляет заданный элемент между соседними элементами списка.

(define (intersperse e xs)
  (cond ((null? xs) '())
        ((null? (cdr xs)) xs)
        (else
         (cons (car xs)
               (cons e
                     (intersperse e (cdr xs)))))))

5. Предикат "all?"

Процедура проверяет, удовлетворяют ли все элементы списка заданному предикату. Для пустого списка результатом является "#t".

(define (all? pred? xs)
  (or (null? xs)
      (and (pred? (car xs))
           (all? pred? (cdr xs)))))

6. Процедура "o"

Процедура принимает произвольное количество процедур одного аргумента и возвращает их композицию.

(define (o . fs)
  (define (compose fs)
    (if (null? fs)
        (lambda (x) x)
        (let ((f (car fs))
              (g (compose (cdr fs))))
          (lambda (x)
            (f (g x))))))
  (compose fs))

Тестирование

Тестирование "uniq"

> (uniq '(a a b c c c d d a b a))
(a b c d a b a)

> (uniq '(1 1 2 2 2 3 4 4 1))
(1 2 3 4 1)

> (uniq '((x 7) (x 7) (y 5) (y 5)))
((x 7) (y 5))

> (uniq '(a))
(a)

> (uniq '())
()

Тестирование "delete"

> (delete even? '(0 1 2 3))
(1 3)

> (delete even? '(0 2 4 6))
()

> (delete even? '(1 3 5 7))
(1 3 5 7)

> (delete even? '())
()

> (delete odd? '(0 1 2 3))
(0 2)

> (delete zero? '(0 1 2 3))
(1 2 3)

Тестирование "polynom"

> (polynom '(3 5 2 8) 4)
288

> (polynom '(83 -53 74) 7)
3770

> (polynom '(4) 100)
4

Тестирование "intersperse"

> (intersperse 'x '(1 2 3 4))
(1 x 2 x 3 x 4)

> (intersperse 'x '(1 2))
(1 x 2)

> (intersperse 'x '(1))
(1)

> (intersperse 'x '())
()

Тестирование "all?"

> (all? odd? '(1 3 5 7))
#t

> (all? odd? '(0 1 2 3))
#f

> (all? odd? '(0 2 4 6))
#f

> (all? odd? '())
#t

Тестирование "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

Вывод

В ходе выполнения лабораторной работы были реализованы процедуры обработки списков с использованием рекурсии, процедуры высшего порядка и композиции функций на языке Scheme.

Были изучены и применены операции "car", "cdr", "cadr", "cons", предикаты "null?", "equal?", "even?", "odd?", "zero?", а также логические операции "and" и "or".

При реализации процедур "polynom" и "all?" использована хвостовая рекурсия. Все реализованные процедуры протестированы на примерах из задания.