Последовательности и операции высших порядков

Специальная форма `quote`

Напомним, что с некоторыми S-выражениями в языке Scheme связаны специальные правила вычисления, отличные от «превратить выражение в само себя». Например, слова (типа mod, div, + и т.п.) преобразуются в объект, к ним привязанный. Последовательности либо вычисляются согласно аппликативному порядку, либо (если первый элемент – одно из нескольких ключевых слов) вычисляются особым образом.

Если хочется получить именно то выражение, которое написано, можно взять его внутрь специальной формы quote:

(display        (+ 2 3))   ;; напечатает число 5
(newline)
(display (quote (+ 2 3)))  ;; напечатает последовательность (+ 2 3)

Специальная форма quote настолько часто встречается, что для неё есть специальный синтаксис: одинарная кавычка.

;; следующие два выражения на самом деле -- совсем одно и тоже
(quote (+ 2 3))
'(+ 2 3)

Последовательности

Последовательности (или, как их ещё называют, односвязные списки) – структура данных, лежащая в основе языка Scheme и прочих диалектов LISP (собственно, название LISP является аббревиатурой от LISt Processor).

С точки зрения математики, последовательность – это одно из двух: пустая последовательность или же пара вида «первый элемент, остальная последовательность». В Scheme последовательности устроены ровно по этому же принципу:

(display (car '(1 2 3)))   ;; 1
(newline)
(display (cdr '(1 2 3)))   ;; (2 3)
(newline)
(display (cons 1 '(2 3)))  ;; (1 2 3)
(newline)
(display (null? '(1 2 3))) ;; #f

Названия car, cdr – традиционные. Никакого особого смысла они в себе в настоящее время не несут (CAR и CDR – это нечто вроде Contents of Address Register и Contents of Destination Register; что именно – никто точно не помнит). Также определены функции наподобие cadr (второй элемент списка), caddr (третий элемент списка) и прочие подобные.

Функции, работающие с последовательностями, определяются «индукцией по структуре последовательности»:

;; аналог стандартной length
(define (длина последовательность)
  (if (null? последовательность)
    0
    (+ 1 (длина (cdr последовательность)))))
    

(define (сумма последовательность)
  (if (null? последовательность)
    0
    (+ (car последовательность) (сумма (cdr последовательность)))))

Общая схема этих определений в науке называется «правой свёрткой»:

(define (foldr f y xs)
  (if (null? xs)
    y
    (f (car xs) (foldr f y (cdr xs)))))

Например, операции длина и сумма в терминах foldr выражаются так:

(define (длина xs)
  (define (плюсодин a b) (+ 1 b))
  
  (foldr плюсодин 0 xs))

(define (сумма xs) (foldr + 0 xs))

Определение операции длина при этом выглядит несколько громоздко засчёт вспомогательной операции плюсодин. Язык Scheme позволяет явно включать операцию в код, не давая ей имя, при помощи лямбда-выражений, которые играют роль псевдолитералов для функций:

;; ещё раз длина
(define (длина xs) (foldr (lambda (a b) (+ 1 b)) 0 xs))

;; не слишком эффективная реализация разворота
(define (развернуть xs)
  (foldr (lambda (x ys) (append ys (cons x '()))) '() xs))

Операции высших порядков

Операция foldr принимает на вход элемент, последовательность, а также – ещё одну операцию. Операции, манипулирующие операциями, обычно называют комбинаторами или же операциями высших порядков.

Два, по всей видимости, наиболее распространённых комбинатора в программировании – map и filter:

;; map и filter уже определены в стандартной библиотеке

;; превращает (x_1 x_2 ... x_n) в ((f x_1) (f x_2) ... (f x_n))
(define (map f xs)
  (if (null? xs) 
    xs 
    (cons (f (car xs)) (cdr xs))))

;; выбирает из последовательности xs элементы, которые удовлетворяют свойству p
(define (filter p xs)
  (cond [(null? xs)   xs]
        [(p (car xs)) (cons (car xs) (filter p (cdr xs))]
        [else         (filter p (cdr xs))]))

Приведём несколько простых примеров использования этих комбинаторов:

;; ещё одна реализация длины
(define (длина xs) (foldr + 0 (map (lambda (x) 1) xs)))


;; сортировка двоичным разбиением
(define (упорядочить xs)
  (if (null? xs)
    xs
    (append (упорядочить (filter (lambda (x) (<  x (car xs))) (cdr xs)))
            (car xs)
            (упорядочить (filter (lambda (x) (>= x (car xs))) (cdr xs))))))

Правая свёртка

В прошлой главе мы рассматривали вторую распространённую схему рекурсии – цикл. Общая схема цикла описывается комбинатором «левой свёртки»:

(define (foldl f y xs)
  (if (null? xs)
    y
    (foldl f (f y (car xs)) (cdr xs))))

Пример (показательный, но немного громоздкий) использования левой свёртки для реализации цикла:

;; диапазон от a до b
(define (range a b)
  (if (< a b)
    (cons a (range (+ 1 a) b))
    '()))

(define (factorial n)
  (car (foldl 
    (lambda (state k) 
      (list                  ;; list делает из указанных объектов последовательность
        (* (car state) k) 
        (+ (cadr state) 1)))  
    '(1 1) 
    (range 1 (+ n 1)))))

В некоторых случаях (для ассоциативной операции f и нейтрального элемента y) разница между foldl и foldr минимальна:

(foldr + 0 '(1 2 3))  ;; преобразуется в (+ 1 (+ 2 (+ 3 0)))
(foldl + 0 '(1 2 3))  ;; эквивалентно (+ (+ (+ 0 1) 2) 3), но эффективнее по памяти

Упражнения

На самом деле, последовательности можно отлично (хотя и не очень эффективно) эмулировать функциями:

(define (car x)   (x #t))
(define (cdr x)   (x #f))
(define empty     (lambda (s) #f))
(define (null? x) (not (cdr x)))

Допишите функцию cons.

Реализуйте эффективный разворот при помощи foldl и лябмда-выражения. Под эффективностью понимается линейная зависимость времени работы от длины последовательности. Реализация должна выглядеть так:

(define (разворот xs)
  (foldl ??? ??? xs))

Что делает следующий комбинатор? Почему?