О предрассудках:
Из старого треда:

Список, насколько моя знать, это объект, удовлетворяющий следующему индуктивному определению:

1) Пустой список есть список.
2) Если L - список, а t - объект, могущий быть элементом списка рассматриваемого вида, то результат "приписывания" t к L - тоже список.

Суть этого определения в том, что любой "реальный" список можно эффективно "раздеть" до пустого

Утверждение про "раздеть" кажется интуитивно абсолютно очевидным. Я тоже на несколько секунд купился. Тем более, что определение списка дано верно. Тем не менее утверждение про "раздевание" абсолютно неверно - в реальности там совершенно жуткий зверинец, более всего напоминающий по структуре что-то фрактальное или из области бесконечных счетных ординалов (возможно просто им и соотвествущее 1 в 1).

При том, что речь идет о реальных списках в реальных языках программирования.

PS: Еще очень забавная вещь происходит, если на отношение равенства списков посмотреть с точки зрения принципа тождества неразличимых (в компьютерном варианте) - там очень странные вещи начинают происходить - например из того, что B /= C, не следует,
что A++B /= A++C (++ - конкатенация) - во многих примерах они реально будут различны, но способов обнаружить этот факт не будет.

Забавная на самом деле вещь - "интуитивная очевидность конструктивной математики" :)