map, filter и fold

Заменяем циклы тремя функциями высшего порядка — map, filter и fold, которые выражают почти любую обработку коллекции.

fold (свёртка) — обобщённая операция, которая сводит список к одному значению, применяя функцию-аккумулятор к каждому элементу.

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

map — преобразование

List.map (fun x -> x * x) [1; 2; 3; 4]
(* [1; 4; 9; 16] *)
List.map string_of_int [1; 2; 3]
(* ["1"; "2"; "3"] *)

Тип: ('a -> 'b) -> 'a list -> 'b list. Тип элементов может меняться (int в string).

filter — отбор

List.filter (fun x -> x > 0) [-2; 3; -1; 5; 0]
(* [3; 5] *)

Тип: ('a -> bool) -> 'a list -> 'a list. Длина результата меньше или равна исходной.

fold — свёртка

List.fold_left f acc l идёт по списку слева направо, обновляя аккумулятор: acc' = f acc элемент.

List.fold_left (fun acc x -> acc + x) 0 [1; 2; 3; 4]
(* (((0+1)+2)+3)+4 = 10 *)

List.fold_left (fun acc x -> acc ^ x) "" ["a"; "b"; "c"]
(* "abc" *)

Через fold можно выразить и map, и filter, и сумму, и максимум — это «универсальный растворитель» обработки списков.

fold_left против fold_right

fold_left сворачивает слева: f (f (f acc x1) x2) x3. fold_right — справа: f x1 (f x2 (f x3 acc)).

List.fold_right (fun x acc -> (x * 2) :: acc) [1; 2; 3] []
(* [2; 4; 6] *)

Практическая разница: fold_left хвостовая и работает в постоянной памяти стека. fold_right не хвостовая и на очень длинных списках может переполнить стек, зато естественно сохраняет порядок. По умолчанию предпочитайте fold_left.

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

Все три функции — это завёрнутая в библиотеку рекурсия по списку. map и filter строят новый список, не трогая исходный. fold_left реализован с аккумулятором в хвостовой позиции, поэтому компилятор превращает его в цикл. Понимание этого помогает выбирать: цепочка map |> filter читаема, но проходит список несколько раз; одна свёртка может сделать всё за один проход.

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

Перепутать порядок аргументов в свёртке. В fold_left — fun acc x -> ..., в fold_right — fun x acc -> ....
Использовать fold_right на огромных списках. Риск переполнения стека.
Городить рекурсию вручную там, где хватит map/filter/fold.

Итоги

map преобразует каждый элемент, filter отбирает по предикату, fold сворачивает в одно значение.
fold_left хвостовой и безопасный по стеку; fold_right сохраняет порядок, но не хвостовой.
Через fold выражаются почти все остальные операции обработки списков.