УМНАЯ ЛЕНИВОСТЬ

Множество раз слышала, что нужен умнó ленивый сотрудник. То есть человек, который сможет сделать поставленную задачу минимальным числом усилий. Языки программирования подражают своим создателям и обладают свойством ленивости. На человеческий: «не делай, пока тебя реально не попросят». Такое свойство позволяет, например, работать с бесконечными структурами данных.

Посмотрим такие штуки на примере моего любимого Lisp. Для начала немного теории.

Есть три базовые функции:
▪cons — принимает на вход два аргумента и делает из них точечную пару. Пример: (cons 2 3) создаёт точечную пару, где первый элемент — 2, а второй — 3.
▪car — принимает на вход точечную пару, возвращает её первый элемент.
▪cdr — соответственно, возвращает второй.

(car (cons 2 3))  → 2
(cdr (cons 2 3))  → 3

Точечная пара, которая вторым элементом имеет NIL, — это список из одного элемента.
То есть (cons 100 NIL) — это список с одним элементом [100].
NIL можно рассматривать как терминатор. Если когда-нибудь пробовали написать список сами на C/C++, то, вероятно, использовали похожую структуру:

struct my_list {
    int value;
    struct my_list* next;
};

В последнем элементе списка next равен NULL, то есть «дальше ничего нет».
В Lisp то же самое. Если пробовали когда-то писать вставку в список, то cons — это добавление элементов в начало.

Чтобы сделать список длиннее:

(cons 100 (cons 200 (cons 300 NIL)))  → [100, 200, 300]

Всё! Теперь вы профессиональный программист на Lisp. Это основная структура данных в языке.

Давайте попробуем создать бесконечный список:

(defun infinite-list (element)
  (cons element (lambda () (infinite-list (+ 1 element)))))

Функция принимает на вход элемент, делает его первым элементом точечной пары, а второй элемент — это рекурсивный вызов (немного странный, но об этом позже).
Внимательный читатель заметил, что мы не написали условий для остановки рекурсии, то есть выглядит так, будто структура будет считаться бесконечно.

Но, как уже сказала, языки программирования обладают свойством «ленивости».
Иными словами, если нужны только первые несколько элементов списка, то программа успешно завершится. А если вдруг по невнимательности программист создал такую структуру, но никогда не интересовался ни одним из элементов, интерпретатор вообще ничего не посчитает.

Попробуем напечатать первые три элемента нашей бесконечной структуры:

(let ((test-list (infinite-list 100)))
  (pprint (car test-list))
  (pprint (car (cdr test-list)))
  (pprint (car (cdr (cdr test-list)))))

Создали список с первым элементом 100, напечатали по отдельности каждый из первых трёх элементов.
Если вычислить как есть, то первый элемент выведется корректно, а вот на втором получите ошибку:
CAR: #<FUNCTION :LAMBDA NIL (INFINITE-LIST (+ 1 ELEMENT))> is not a list

Так-так-так. Мы же бесконечный список создавали?
А теперь нам говорят, что уже на второй итерации у нет списка?
Дело в том странном рекурсивном вызове, который обёрнут в лямбда-выражение. Именно эта «обёртка» позволяет нам что-то отложить.

(cons element (lambda () (infinite-list (+ 1 element))))

Таким вызовом мы создали точечную пару из числа и функции, которая может посчитать хвост списка, но мы её ещё не запускали.
Чтобы вызвать функцию, можно воспользоваться специальной функцией funcall. Тогда можно переписать car в виде новой функции head:

(defun head (my-list)
  (cond
    ((functionp my-list) (head (funcall my-list)))
    (t (car my-list))))

С помощью functionp проверяем, что объект является функцией. Если да — вычисляем и пробуем взять голову. Если объект обычный — просто возвращаем.

В итоге получаем такой код:

(defun head (my-list)
  (cond
    ((functionp my-list) (head (funcall my-list)))
    (t (car my-list))))

(defun tail (my-list)
  (cond
    ((functionp my-list) (tail (funcall my-list)))
    (t (cdr my-list))))

(let ((test-list (infinite-list 100)))
  (pprint (head test-list))
  (pprint (head (tail test-list)))
  (pprint (head (tail (tail test-list)))))

#бабанюра_программирует #itstudy