Коллекции и их обработка: списки, массивы, seq, map/filter/fold

Три рабочие коллекции F#: неизменяемый список, изменяемый массив и ленивая последовательность.

Список (list) в F# — неизменяемый односвязный список; массив (array) — изменяемый блок с быстрым доступом по индексу; seq — ленивая последовательность.

Список — рабочая лошадка

Список задают квадратными скобками с разделителем ;. Он неизменяем: операции возвращают новый список.

let xs = [1; 2; 3]
let ys = 0 :: xs        // добавление в начало — новый список
printfn "%A" xs
printfn "%A" ys

Вывод:

[1; 2; 3]
[0; 1; 2; 3]

Оператор :: добавляет элемент в начало за константное время; @ склеивает два списка. Добавление в начало дёшево, в конец — дорого (нужно пройти весь список).

Массив — быстрый доступ по индексу

Массив задают [| ... |]. Он изменяем и даёт доступ по индексу за константное время.

let arr = [| 10; 20; 30 |]
arr.[1] <- 99           // массив изменяем
printfn "%A" arr
printfn "%d" arr.[0]

Вывод:

[|10; 99; 30|]
10

seq — ленивая последовательность

seq (обёртка над IEnumerable) вычисляется лениво: элементы создаются по мере необходимости. Это позволяет работать с потенциально бесконечными потоками.

let firstFive =
    seq { 1 .. 1000000 }      // не материализуется целиком
    |> Seq.take 5
    |> Seq.toList
printfn "%A" firstFive

Вывод:

[1; 2; 3; 4; 5]

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

Диапазоны и генерация

Удобный синтаксис диапазонов работает для всех трёх коллекций.

let evens = [ for x in 1 .. 10 do if x % 2 = 0 then yield x ]
printfn "%A" evens

Вывод:

[2; 4; 6; 8; 10]

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

Список — цепочка ячеек (голова + ссылка на хвост), поэтому добавление в начало = создание одной ячейки, а индексация требует прохода. Массив — непрерывный блок памяти .NET с O(1) индексацией, но фиксированной длины. seq — это «рецепт» вычисления: при перечислении он порождает элементы по одному, не храня их все, что и даёт лень и экономию памяти.

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

• Часто добавлять в конец списка через @ в цикле — это O(n) на операцию, лучше собирать в обратном порядке.
• Ожидать от списка мутации по индексу — он неизменяем; для этого нужен массив.
• Перечислять seq несколько раз, если он с побочными эффектами — он вычисляется заново каждый раз.

Итоги

• Список — неизменяемый, дёшево добавлять в начало (::), дорого индексировать.
• Массив — изменяемый, быстрый доступ по индексу ([| |], arr.[i]).
• seq — ленивая последовательность, годится для больших и бесконечных потоков.
• Списковые включения [ for ... do yield ... ] генерируют коллекции декларативно.

Преобразования: map, filter, fold

map: преобразовать каждый элемент

Вместо цикла с накоплением нового списка List.map применяет функцию ко всем элементам, возвращая новую коллекцию той же длины.

let nums = [1; 2; 3; 4]
let squares = List.map (fun x -> x * x) nums
printfn "%A" squares

Вывод:

[1; 4; 9; 16]

filter: отобрать подходящие

List.filter оставляет лишь те элементы, для которых предикат истинен.

let nums = [1; 2; 3; 4; 5; 6]
let evens = List.filter (fun x -> x % 2 = 0) nums
printfn "%A" evens

Вывод:

[2; 4; 6]

fold: свернуть в одно значение

List.fold проходит коллекцию, накапливая результат. Сигнатура: начальный аккумулятор, функция (аккумулятор, элемент) -> новый аккумулятор, коллекция.

let nums = [1; 2; 3; 4]
let sum = List.fold (fun acc x -> acc + x) 0 nums
let product = List.fold (fun acc x -> acc * x) 1 nums
printfn "сумма %d, произведение %d" sum product

Вывод:

сумма 10, произведение 24

fold универсален: через него выражаются sum, max, подсчёт, построение строк — почти любая агрегация.

Конвейер из преобразований

Сила в комбинации: map, filter, fold складываются в конвейер, читаемый сверху вниз.

let result =
    [1 .. 10]
    |> List.filter (fun x -> x % 2 = 0)
    |> List.map (fun x -> x * x)
    |> List.sum
printfn "%d" result

Вывод:

220

Чётные из 1..10 → [2;4;6;8;10], в квадрат → [4;16;36;64;100], сумма → 220. Никаких циклов и временных переменных.

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

Все эти функции внутри — простые рекурсии или циклы по коллекции, но скрытые за чистым интерфейсом. map и filter создают новый список, не трогая исходный (неизменяемость сохраняется). fold — это «левая свёртка»: она обрабатывает элементы слева направо, передавая аккумулятор. Существует и foldBack (справа налево). Эти комбинаторы заменяют большинство ручных циклов.

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

• Путать порядок аргументов fold: функция получает (аккумулятор, элемент), а начальное значение идёт перед коллекцией.
• Использовать map ради побочного эффекта — для этого есть List.iter.
• Городить ручной цикл там, где хватает map/filter/fold.

Итоги

• map преобразует каждый элемент, длина сохраняется.
• filter оставляет элементы, удовлетворяющие предикату.
• fold сворачивает коллекцию в одно значение через аккумулятор.
• Комбинация в конвейере заменяет императивные циклы и читается декларативно.