Списки и модуль List

Знакомимся со списками — иммутабельной односвязной структурой, на которой держится функциональная обработка данных.

Список в OCaml — неизменяемая односвязная последовательность элементов одного типа, построенная из [] и операции добавления в голову ::.

Список — самая узнаваемая структура функциональных языков. В OCaml он односвязный и неизменяемый: вы не меняете список, а создаёте новый. Понимание устройства объясняет, почему одни операции дёшевы, а другие дороги.

Устройство: голова и хвост

let a = []                 (* пустой: 'a list *)
let b = 1 :: 2 :: 3 :: []  (* [1; 2; 3] *)
let c = [1; 2; 3]          (* то же, синтаксический сахар *)
let d = 0 :: c             (* [0; 1; 2; 3] — добавление в голову *)

Элементы разделяются точкой с запятой ;, а не запятой (запятая создала бы кортеж!). Все элементы одного типа: [1; "a"] — ошибка.

Рекурсивная обработка

let rec sum = function
  | [] -> 0
  | head :: tail -> head + sum tail

let total = sum [10; 20; 30]   (* 60 *)

Образец head :: tail разбирает непустой список: head — первый элемент, tail — остаток. Эта схема — основной приём работы со списками.

Ключевые функции модуля List

Функция	Что делает
`List.length l`	число элементов
`List.rev l`	разворот списка
`l1 @ l2`	конкатенация (дорогая по длине l1)
`List.nth l i`	элемент по индексу (линейный)
`List.map f l`	применить f к каждому
`List.filter p l`	оставить подходящие

let evens = List.filter (fun x -> x mod 2 = 0) [1;2;3;4;5;6]
(* [2; 4; 6] *)

Как работает под капотом

Каждый :: — это ячейка в куче из двух полей: значение и указатель на хвост. Поэтому добавление в голову занимает O(1) — создаётся одна ячейка, указывающая на старый список, который не копируется (он неизменяем). А доступ по индексу List.nth и конкатенация @ требуют пройти список — это O(n). Практическое правило: накапливайте добавлением в голову, а в конце делайте List.rev. Для быстрого доступа по индексу используйте массивы.

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

Разделять элементы запятой: [1, 2, 3] — это список из одного кортежа. Нужна точка с запятой.
Часто использовать @ в цикле. Накопление через @ даёт квадратичную сложность. Лучше :: + rev.
Обращаться по индексу как в массиве. List.nth линеен.

Итоги

Список — неизменяемая односвязная структура из [] и ::; элементы разделяются ;.
Обработка — рекурсия с разбором на голову и хвост через сопоставление с образцом.
Добавление в голову — O(1), индексация и конкатенация — O(n).