---

Ниже — готовые решения для лабораторной №1Б на Scheme, соответствующие ограничениям (без `set!`, циклов и обращения по индексу).

### 1\. `uniq` — удалить соседние дубликаты

```scheme
(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))))))
```

Проверка:

```scheme
(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)
```

### 2\. `delete` — удалить элементы по предикату

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

Проверка:

```scheme
(delete even? '(0 1 2 3))
; => (1 3)

(delete zero? '(0 1 2 3))
; => (1 2 3)
```

### 3\. `polynom` — вычисление полинома (схема Горнера)

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

Проверка:

```scheme
(polynom '(3 5 2 8) 4)
; => 288

(polynom '(83 -53 74) 7)
; => 3770
```

### 4\. `intersperse` — вставить элемент между элементами списка

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

Проверка:

```scheme
(intersperse 'x '(1 2 3 4))
; => (1 x 2 x 3 x 4)
```

### 5\. `all?` — все элементы удовлетворяют предикату

Без `if` и `cond`, только `and` и `or`.

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

Проверка:

```scheme
(all? odd? '(1 3 5 7))
; => #t

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

(all? odd? '())
; => #t
```

### 6\. `o` — композиция функций

```scheme
(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))
```

Проверка:

```scheme
(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
```

### Ответы на защиту

### 1\. Где использована хвостовая рекурсия?

| Процедура   | Хвостовая рекурсия |
| ----------- | ------------------ |
| uniq        | Нет                |
| delete      | Нет                |
| polynom     | Да                 |
| intersperse | Нет                |
| all?        | Да                 |
| o           | Нет                |

Почему?

* В `polynom` рекурсивный вызов — последнее действие процедуры (`iter`).

* В `all?` рекурсивный вызов находится последним в выражении `and`; если предыдущая проверка истинна, результатом сразу становится рекурсивный вызов.

### 2\. Алгоритмическая сложность

| Процедура   | Время                                             | Память                                  |
| ----------- | ------------------------------------------------- | --------------------------------------- |
| uniq        | O(n)                                              | O(n)                                    |
| delete      | O(n)                                              | O(n)                                    |
| polynom     | O(n)                                              | O(1) при оптимизации хвостовой рекурсии |
| intersperse | O(n)                                              | O(n)                                    |
| all?        | O(n), в лучшем случае меньше (короткое замыкание) | O(n)                                    |
| o           | Построение O(n), вызов композиции O(n)            | O(n)                                    |

Все процедуры проходят список коэффициентов или элементов один раз, поэтому имеют линейную сложность по времени.