Голова и хвост списка

Список является рекурсивным составным объектом. Он состоит из двух

частей - головы, которой является первый элемент, и хвоста, которым явля-

ется список, включающий все последующие элементы. Хвост списка - всегда

список, голова списка - всегда элемент. Например:

головой [a, b, c] является a,

хвостом [a, b, c] является [b, c]

Что происходит, когда вы доходите до одноэлементного списка? Ответ

таков:

голова [c] есть c

хвост [c] есть []

Если выбирать первый элемент списка достаточное количество раз, вы

обязательно дойдете до пустого списка ([]).

Пустой список нельзя разделить на голову и хвост.

В концептуальном плане это значит, что список имеет структуру дере-

ва, как и другие составные объекты. Структура дерева [a, b, c, d] такова:

list

/ \

a list

/ \

b list

/ \

c list

/ \

d []

Далее. Одноэлементный список, как например [a], не то же самое, что

элемент, который в него входит, потому что [a] на самом деле - это сос-

тавная структура данных, как здесь показано:

list

/ \

a []