Списки и их устройство

Список в Haskell — это либо пусто, либо «элемент впереди другого списка». Из этого простого правила вырастает всё.

Список [1,2,3] — на самом деле 1 : 2 : 3 : []. Понять оператор : — значит понять списки целиком.

Списки — самая ходовая структура данных в Haskell. Элементы в списке всегда одного типа: [Int], [String], [Bool]. Записать список можно явно или через диапазон:

nums   = [1, 2, 3, 4, 5]
range  = [1..10]            -- [1,2,3,4,5,6,7,8,9,10]
evens  = [2, 4 .. 10]      -- [2,4,6,8,10] — шаг 2
letters = ['a' .. 'e']      -- "abcde"

Оператор «двоеточие» — сердце списка

Оператор : (cons) добавляет элемент в начало списка. Любой список строится из : и пустого списка []:

[1, 2, 3]  ==  1 : 2 : 3 : []
0 : [1,2,3]  ==  [0,1,2,3]

        :                список [1,2,3]
       / \
      1   :              читается как
         / \            1 «впереди» (2 «впереди» (3 «впереди» []))
        2   :
           / \
          3   []

Оператор ++ склеивает два списка целиком: [1,2] ++ [3,4] даёт [1,2,3,4]. Важная деталь: : добавляет один элемент спереди (быстро), а ++ соединяет списки (тем дольше, чем длиннее левый).

Полезные функции

head [1,2,3]     -- 1   (первый элемент)
tail [1,2,3]     -- [2,3] (всё кроме первого)
length [1,2,3]   -- 3
null []          -- True (пустой ли список)
take 2 [1,2,3]   -- [1,2]
drop 2 [1,2,3]   -- [3]
elem 2 [1,2,3]   -- True (есть ли элемент)
[1,2,3] !! 0     -- 1   (по индексу)

В Python списки устроены иначе (это массивы), но «голова и хвост» и склейка прекрасно иллюстрируют идею:

# Та же идея на Python: голова, хвост, склейка
xs = [1, 2, 3]

head = xs[0]        # 1
tail = xs[1:]       # [2, 3]
print(head, tail)

# cons (:) — добавление в начало
print([0] + xs)     # [0, 1, 2, 3]

# ++ — склейка
print([1, 2] + [3, 4])   # [1, 2, 3, 4]

# диапазон как [1..5]
print(list(range(1, 6)))  # [1, 2, 3, 4, 5]

Голова, хвост и вся работа со списками

Стоит увидеть список как «голова плюс хвост», и почти любая операция над ним складывается сама собой. Сумма? Сложить голову с суммой хвоста. Длина? Единица плюс длина хвоста. Разворот, фильтрация, преобразование — всё описывается через один и тот же узор разбора (x:xs). Именно поэтому оператор : и пустой список [] — не просто синтаксис, а строительные блоки, из которых собран любой список. Стоит помнить и про производительность: добавление в начало через : мгновенно, а склейка ++ тем дороже, чем длиннее левый список, потому что его приходится проходить целиком. Поэтому накапливают обычно в начало, а потом при необходимости разворачивают. Освоив мышление «голова + хвост», вы получаете ключ не только к спискам, но и к рекурсии, сопоставлению с образцом и свёрткам разом.

Как это мыслить

Представляйте список как «голова + хвост». Почти все операции естественно описываются рекурсивно: что-то делаем с головой, рекурсивно обрабатываем хвост. Именно поэтому образец (x:xs) из раздела про сопоставление встречается на каждом шагу.

Полезно держать в голове и то, что список — не всегда лучший выбор структуры данных, хотя он и самый удобный для обучения. Доступ к элементу по индексу через !! работает за линейное время, потому что приходится пройти список от начала, а не прыгнуть сразу в нужную ячейку, как в массиве. Если в задаче много обращений по индексу или нужны быстрые вставки в середину, разумнее взять специализированные структуры из пакета containers — например, Map для ассоциаций ключ-значение или Seq для эффективного доступа с обоих концов. Но для последовательной обработки «голова за хвостом», для которой списки и созданы, они идеальны: ленивые, простые и прекрасно сочетающиеся с рекурсией, свёртками и генераторами.

Частые ошибки

Вызвать head или tail на пустом списке. Это ошибка времени выполнения; сначала проверяйте null или используйте сопоставление с [].
Смешивать типы в списке. [1, "two"] не скомпилируется — элементы должны быть одного типа.
Часто использовать ++ слева в цикле. Накопление через многократный ++ в начале бывает медленным; добавляйте через :.

Best practices

Для добавления одного элемента в начало используйте :, а не ++ [x].
Предпочитайте безопасные варианты разбора через сопоставление с [] и (x:xs).
Диапазоны ([1..n]) — компактный способ создать последовательность.

Итог. Список — это x : xs или []. Оператор : добавляет элемент спереди, ++ склеивает списки, а функции head, tail, take, drop дают базовый инструментарий. Мышление «голова + хвост» открывает почти всю работу со списками.