Линейный список. Логическое описание: голова и хвост

Модуль "Линейные списки" • урок 2 из 9 • ~5 минут

Исторический контекст (Prolog и Lisp)

В языке C встроенного логического типа "список" не существует - его логика слита с физической реализацией через указатели. Однако в функциональных (Lisp) и логических (Prolog) языках программирования список является главной встроенной структурой данных.

В Прологе логика списков выражена наиболее наглядно. По определению, список - это либо пустой список (обозначается []), либо рекурсивная структура, состоящая из головы и хвоста.

Как описывается список в Лиспе (Lisp)?

В языке Lisp списки описываются круглыми скобками, а элементы внутри них разделяются пробелами. Например: (1 2 3) или (A B C).

Главная особенность Лиспа заключается в том, что списки служат одновременно и структурой данных, и исполняемым кодом. По умолчанию интерпретатор пытается вычислить любой переданный список, воспринимая первый элемент как имя функции, а остальные - как ее аргументы (например, список (+ 1 2) вычислится в 3).

Чтобы создать список именно как набор данных, в коде используются два разных инструмента:

Оператор quote (одинарная кавычка ') - полностью блокирует вычисление. Он дает команду интерпретатору воспринимать содержимое буквально, "как есть".

Пример: '(A B C) вернет список (A B C). Без кавычки интерпретатор выдал бы ошибку, попытавшись вызвать несуществующую функцию A.

Функция list - в отличие от quote, сначала вычисляет каждый переданный ей аргумент, и только затем собирает полученные результаты в новый список.

Пример: (list 1 (+ 1 1) 3) вычислит центральное выражение и вернет готовый список данных (1 2 3).

Линейный список. Логическое описание: разделение на голову и хвост

Базовая операция в Прологе - отделение головы от хвоста. Если мы применим эту операцию к списку [1, 2, 3], то:

• Голова получит значение 1 (первый элемент).
• Хвост станет списком [2, 3] (остаток).

Любые алгоритмы на таком списке программируются рекурсивно: мы отщепляем голову, выполняем нужные действия (например, прибавляем единицу к счетчику длины), и вызываем ту же самую функцию для оставшегося хвоста. Этот процесс продолжается, пока мы не упремся в пустой список.

Эмуляция логики Пролога на C

Чтобы лучше понять суть разделения на "голову" и "хвост", посмотрим, как список можно построить в C в функциональном стиле. Для этого понадобится функция Cons, склеивающая элемент-голову и хвост:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int head;             /* Голова (элемент) */
    struct Node* tail;    /* Хвост (весь остальной список) */
} Node;

/* Функция склеивания Головы и Хвоста */
Node* Cons(int head, Node* tail) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->head = head;
    newNode->tail = tail;
    return newNode;
}

int main(void) {
    /* Строим список [1, 2, 3] рекурсивно, как в Lisp/Prolog: */
    Node* list = Cons(1, Cons(2, Cons(3, NULL)));
    
    /* Логическое отделение головы от хвоста: */
    int first_element = list->head;      /* 1 */
    Node* rest_of_list = list->tail;     /* Список [2, 3] */
    
    return 0;
}