Ленивость, бесконечные структуры и потоки данных

Есть задачи, где обычный подход ломается не из-за алгоритма, а из-за порядка вычислений. Файл на 40 ГБ не помещается в память. Список простых чисел не имеет конца. Цепочка map -> filter -> take 3 над миллионом элементов делает миллион лишних вызовов ради трёх результатов. Во всех трёх случаях проблема одна: язык вычисляет всё, что видит, а не то, что понадобилось.

Ленивость — это ответ на эту боль. Она меняет не результат программы, а объём и момент проделанной работы. Обзорный взгляд на парадигму есть в статье Функциональное программирование; здесь мы разберём ленивость до уровня «умею применять и знаю, где обожгусь».

Три боли, из которых вырастает ленивость

Боль первая: промежуточные коллекции

# Найти первые три пользователя из большого списка, у кого баланс после
# начисления бонуса превысил порог.
result = [u for u in
          [apply_bonus(u) for u in load_all_users()]   # копия №1: 1 000 000
          if u.balance > 10_000][:3]                   # копия №2: ~400 000

Мы построили два полных массива, чтобы взять три элемента. Это не гипотетика: точно так же ведут себя Enum.map |> Enum.filter в Elixir, array.map().filter() в JavaScript, Select().Where().ToList() в C#, если материализовать каждый шаг.

Кажется, что решение — слить всё в один цикл руками. Но тогда мы теряем композицию: код перестаёт быть набором независимых переиспользуемых шагов и превращается в один монолитный for с четырьмя if внутри. Композиция — ровно то, ради чего мы строили конвейеры в статье Композиция, каррирование, частичное применение и конвейеры. Ленивость позволяет сохранить и композицию, и однопроходность.

Боль вторая: структура, у которой нет конца

Как записать «список всех натуральных чисел» или «последовательность Фибоначчи»? В строгом языке — никак: попытка построить такой список повесит процесс. Приходится заранее решать, сколько элементов нам понадобится, и зашивать это число в функцию-генератор. Знание «сколько» протекает из места использования в место порождения — это утечка абстракции.

Боль третья: вычисление, которое может не понадобиться

# Дорогая правая часть считается всегда, даже если ключ есть в кэше.
value = cache.get(key, expensive_default())

Это классическая ловушка: expensive_default() вызывается до get. Строгий порядок вычисления аргументов заставляет платить за то, что не пригодилось.

Что такое ленивость на самом деле

Три стратегии передачи аргументов, которые надо различать:

Практическая ленивость — это почти всегда call-by-need: отложить + запомнить. Механизм называется thunk — замыкание без аргументов, которое хранит «рецепт вычисления», а после первого запуска подменяет себя результатом.

Ручная реализация thunk на TypeScript помогает увидеть, что никакой магии нет:

// Thunk: отложенное вычисление с мемоизацией (call-by-need своими руками).
type Thunk<T> = () => T;

function lazy<T>(compute: () => T): Thunk<T> {
  let evaluated = false;
  let value: T;
  return () => {
    if (!evaluated) {
      value = compute();   // считаем ровно один раз
      evaluated = true;
      // Ссылку на compute стоит обнулить: иначе замыкание держит
      // весь захваченный контекст живым — типичный источник утечки.
    }
    return value;
  };
}

const config = lazy(() => JSON.parse(readFileSync("huge-config.json", "utf8")));
// Файл ещё не прочитан.
if (needConfig) console.log(config().timeout);  // прочитан здесь, один раз

Жизненный цикл thunk удобно держать в голове как автомат:

Состояние «Зациклен» — не выдумка: в Haskell выражение let x = x + 1 in x даёт рантайм-ошибку <<loop>>. А вот let xs = 1 : xs работает и даёт бесконечный список единиц — потому что вычисление останавливается на первом конструкторе.

WHNF: ленивость вычисляет «на один шаг»

Ключевая деталь, без которой ленивость кажется мистикой: значение вычисляется не «до конца», а до слабой заголовочной нормальной формы (weak head normal form) — до внешнего конструктора данных или лямбды.

-- Вычислено до WHNF: известно, что список непустой, его голова = 1.
-- Про хвост не известно ничего: там лежит невычисленный thunk.
xs = 1 : (map expensive [2..])

-- Спросили длину — пришлось раскрутить весь костяк списка,
-- но сами элементы так и остались thunk'ами: length их не трогает.
n = length xs

Именно поэтому «ленивый список» — это не «список, который где-то лежит целиком», а пара «текущий элемент + рецепт получения остального».

Ленивость, которая у вас уже есть

Ленивость не привилегия Haskell. Она встроена в каждый язык, просто в конкретных местах:

# Короткое замыкание: правая часть не вычисляется, если левая всё решила.
if user is not None and user.is_active():   # is_active() не вызовется при None
    ...

# Тернарник, if, while — все они ленивы по ветвям.
timeout = cfg["timeout"] if "timeout" in cfg else compute_default()

Если бы and был строгим, user.is_active() падал бы на None. Мы пользуемся ленивостью ежедневно — просто она зашита в синтаксис, а не доступна как инструмент. Ленивые структуры данных — это обобщение того же приёма на произвольные значения.

Генераторы: ленивость в мейнстриме

В большинстве языков ленивые последовательности реализуются через итераторы/генераторы. Модель — pull: потребитель вызывает «дай следующий», и только этот вызов запускает работу.

Обратите внимание на направление стрелок: спрос идёт справа налево, данные — слева направо. Это и есть pull-модель, и у неё бесплатно получается backpressure — источник физически не может произвести больше, чем потребитель забрал.

Python: генераторы и itertools

from itertools import count, islice, takewhile

def naturals():
    """Бесконечный источник. Ни одна строка не выполнится до первого next()."""
    n = 0
    while True:
        yield n
        n += 1

# Конвейер строится мгновенно и не делает ничего.
pipeline = (u for u in map(apply_bonus, load_all_users()) if u.balance > 10_000)
top3 = list(islice(pipeline, 3))    # вот здесь начинается работа — и сразу же кончается

Идиоматичный ленивый разбор большого файла — тот случай, где генераторы окупаются немедленно:

def parse_log(path):
    """O(1) по памяти независимо от размера файла: строка живёт ровно один шаг."""
    with open(path, encoding="utf-8") as f:
        for line in f:                        # файловый объект — сам генератор
            if line.startswith("#"):
                continue
            yield parse_line(line)

errors = (e for e in parse_log("app.log") if e.level == "ERROR")
first_batch = list(islice(errors, 100))

Важная особенность Python: генератор одноразовый. Пройти по нему второй раз нельзя, повторный for молча даст ноль элементов — самая частая ошибка новичка. Если нужен повторный проход, материализуйте (list(...)) или пересоздайте генератор.

Elixir: Enum строгий, Stream ленивый

Elixir по умолчанию строгий, но даёт явный ленивый двойник для каждой операции:

# Строго: два полных промежуточных списка.
1..1_000_000
|> Enum.map(&(&1 * 3))       # список на миллион
|> Enum.filter(&(rem(&1, 7) == 0))  # ещё один список
|> Enum.take(3)

# Лениво: ни одного промежуточного списка, ~7 итераций всего.
1..1_000_000
|> Stream.map(&(&1 * 3))
|> Stream.filter(&(rem(&1, 7) == 0))
|> Enum.take(3)              # Enum.* — точка, где конвейер запускается

Правило запоминается легко: Stream.* описывает работу, Enum.* её выполняет. Модуль Stream умеет и порождать бесконечное:

# Бесконечная последовательность Фибоначчи через unfold.
fibs = Stream.unfold({0, 1}, fn {a, b} -> {a, {b, a + b}} end)
Enum.take(fibs, 10)   # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Ресурс с гарантированным закрытием — правильный способ читать файл потоком.
File.stream!("app.log")
|> Stream.map(&String.trim/1)
|> Stream.filter(&String.contains?(&1, "ERROR"))
|> Stream.take(100)
|> Enum.to_list()

# Stream.resource/3: открыть, тянуть, закрыть — даже если потребитель прервался.
Stream.resource(
  fn -> :gen_tcp.connect(~c"host", 1234, []) |> elem(1) end,
  fn socket ->
    case :gen_tcp.recv(socket, 0) do
      {:ok, data} -> {[data], socket}
      {:error, :closed} -> {:halt, socket}
    end
  end,
  fn socket -> :gen_tcp.close(socket) end
)

Подробнее об экосистеме — в курсе Elixir. Документация Stream: https://hexdocs.pm/elixir/Stream.html.

TypeScript: генераторы и Iterator Helpers

// Бесконечный источник.
function* naturals(): Generator<number> {
  for (let n = 0; ; n++) yield n;
}

// Ленивые комбинаторы пишутся в три строки каждый.
function* mapIter<A, B>(src: Iterable<A>, f: (a: A) => B): Generator<B> {
  for (const x of src) yield f(x);
}
function* filterIter<A>(src: Iterable<A>, p: (a: A) => boolean): Generator<A> {
  for (const x of src) if (p(x)) yield x;
}
function takeIter<A>(src: Iterable<A>, n: number): A[] {
  const out: A[] = [];
  for (const x of src) {
    if (out.length >= n) break;   // break корректно закрывает генератор (вызовет return())
    out.push(x);
  }
  return out;
}

const squares = mapIter(naturals(), (n) => n * n);
const bigOdd = filterIter(squares, (n) => n % 2 === 1 && n > 1000);
console.log(takeIter(bigOdd, 3));   // [1089, 1225, 1369] — посчитано ровно 3 квадрата сверх порога

В современных рантаймах (Node 22+, актуальные браузеры) те же операции есть прямо на итераторах — Iterator Helpers, вошедшие в ES2025:

const result = naturals()
  .map((n) => n * n)
  .filter((n) => n % 2 === 1 && n > 1000)
  .take(3)
  .toArray();

Разница с Array.prototype.map принципиальна: массивные методы строгие и на бесконечном источнике просто зависнут. Подробнее о типизации итераторов — в курсе TypeScript.

Haskell: ленивость по умолчанию

-- Список всех натуральных чисел. Обычное значение, не «специальный тип».
naturals :: [Integer]
naturals = [0..]

-- Фибоначчи, определённые через самих себя. Работает только при ленивости:
-- к моменту, когда нужен n-й элемент, первые n-1 уже вычислены и закэшированы.
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- take 10 fibs == [0,1,1,2,3,5,8,13,21,34]

-- Конвейер из первой боли — и никаких промежуточных списков благодаря fusion.
top3 = take 3 (filter ((> 10000) . balance) (map applyBonus users))

Строка fibs = 0 : 1 : zipWith (+) fibs (tail fibs) — не трюк ради красоты, а демонстрация того, что ленивость даёт разделяемое самоссылающееся определение: каждый элемент вычисляется один раз, потому что fibs — одно значение в памяти, а не функция. Это приём «завязывания узла» (tying the knot).

Корекурсия: рекурсия наоборот

Рекурсия, которую мы разбирали в статье Рекурсия, хвостовые вызовы и как не переполнить стек, потребляет конечную структуру и должна дойти до базового случая. Ленивость даёт зеркальный инструмент — корекурсию: она производит потенциально бесконечную структуру и обязана лишь выдавать очередной конструктор за конечное время.

Канонический комбинатор корекурсии — unfold, точный дуал fold:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

-- Тот же Фибоначчи, но развёрткой из зерна.
fibs' = unfoldr (\(a, b) -> Just (a, (b, a + b))) (0, 1)

-- Метод Ньютона: бесконечная последовательность приближений,
-- отдельно — правило остановки. Классический пример из "Why FP Matters".
next :: Double -> Double -> Double
next n x = (x + n / x) / 2

within :: Double -> [Double] -> Double
within eps (a : b : rest)
  | abs (a - b) <= eps = b
  | otherwise          = within eps (b : rest)

sqrt' :: Double -> Double -> Double
sqrt' eps n = within eps (iterate (next n) n)

Вот в чём сила: «как приближаться» и «когда остановиться» — два независимых, тестируемых, переиспользуемых куска. Поменяли критерий остановки на относительную погрешность — генератор не тронули. В строгом языке эти два решения обычно склеены внутри одного цикла while. Именно этот аргумент Джон Хьюз разворачивает в статье «Why Functional Programming Matters» (https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf) — ленивость называется там одним из двух «клеёв», делающих ФП модульным.

Тот же приём на Python — без всякого Haskell:

from itertools import islice

def iterate(f, x):
    """Бесконечная последовательность x, f(x), f(f(x)), ..."""
    while True:
        yield x
        x = f(x)

def within(eps, seq):
    prev = next(seq)
    for cur in seq:
        if abs(cur - prev) <= eps:
            return cur
        prev = cur

sqrt2 = within(1e-12, iterate(lambda x: (x + 2 / x) / 2, 2.0))

«Порождай и отбирай»: ленивость как способ мыслить

Ленивость делает практичной стратегию, которая в строгом языке выглядит безумием: породить всё пространство кандидатов и отфильтровать нужное.

from itertools import count

def primes():
    """Простые числа — бесконечно. Пробное деление до корня."""
    found = []
    for n in count(2):
        if all(n % p for p in found if p * p <= n):
            found.append(n)
            yield n

# Первое простое больше миллиона — не зная заранее, сколько их придётся перебрать.
p = next(x for x in primes() if x > 1_000_000)

Похожая структура — минимакс с альфа-бета отсечением: ленивое дерево игры порождается «сколько понадобится», а отсечение просто не запрашивает лишние ветви. В строгом языке приходится вплетать глубину и отсечение прямо в генератор ходов.

Честное предупреждение: знаменитый однострочник

primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

решето Эратосфена не реализует — это пробное деление с ужасной асимптотикой, и Мелисса О’Нил разбирает это в статье «The Genuine Sieve of Eratosthenes» (https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf). Красивая ленивая запись не отменяет анализа сложности — про сложность см. курс Алгоритмы.

Потоки данных: pull, push и backpressure

Ленивые последовательности — это pull-потоки внутри одного процесса. Как только источник становится внешним и асинхронным (сокет, Kafka, очередь), появляется вторая модель.

Гибридный протокол — это то, что стоит за спецификацией Reactive Streams (https://www.reactive-streams.org/) и за GenStage в Elixir (https://hexdocs.pm/gen_stage/GenStage.html). Идея та же ленивость, но спрос выражен явным числом и передаётся между процессами:

# Потребитель объявляет, сколько готов принять; producer не шлёт больше.
defmodule Consumer do
  use GenStage

  def init(_), do: {:consumer, :ok, subscribe_to: [{Producer, max_demand: 500, min_demand: 250}]}

  def handle_events(events, _from, state) do
    Enum.each(events, &process/1)
    {:noreply, [], state}     # спрос пополнится автоматически
  end
end

Без backpressure быстрый producer и медленный consumer дают классическую аварию: очередь сообщений растёт, память кончается, процесс убит OOM-killer’ом. Ленивая pull-модель делает такую ситуацию структурно невозможной. Прикладные аспекты потоковой обработки — в курсе Инженерия данных.

Честная цена ленивости

Здесь начинается часть, которую в восторженных статьях обычно пропускают.

1. Space leak: отложенная работа накапливается

Самая известная проблема Haskell. Классика:

-- Строит цепочку из 10 миллионов thunk'ов, потом раскручивает её — и падает
-- с переполнением стека или съедает гигабайты.
sumBad = foldl (+) 0 [1..10000000]

-- Форсирует аккумулятор на каждом шаге: константная память.
sumGood = foldl' (+) 0 [1..10000000]

Ленивый аккумулятор не считает 0 + 1 + 2 + ..., а накапливает выражение. Пока никто не потребовал результат, в памяти лежит гигантское дерево отложенных сложений. Лечение — принудительная строгость: foldl', seq, $!, BangPatterns, строгие поля в записях (!Int). Разбор проблемы: https://wiki.haskell.org/Foldr_Foldl_Foldl%27.

Ловушка того же рода бывает и вне Haskell. Замыкание генератора удерживает всё, что захватило:

def read_records(conn):
    rows = conn.execute("SELECT * FROM big_table")   # курсор жив, пока жив генератор
    for row in rows:
        yield transform(row)

g = read_records(conn)
first = next(g)
# g не дочитан и не закрыт -> транзакция и курсор висят,
# пока сборщик мусора не доберётся до g. На пуле соединений это авария.

Правило: ленивое значение держит живым весь свой контекст. Если генератор не дочитан — закрывайте явно (g.close(), try/finally, contextlib.closing).

2. Память перестаёт быть предсказуемой

В строгой программе понятно, сколько занимает список из миллиона Int. В ленивой — зависит от того, что успело вычислиться: невычисленный thunk может весить в разы больше результата (заголовок объекта + указатель на код + захваченные ссылки). Профиль памяти становится функцией от порядка обращения к данным, а не от структуры данных. Для сервиса с жёстким SLO по latency это неприятная нелинейность: сборка мусора и «раскрутка» большого thunk’а могут выстрелить в произвольный момент.

3. Эффекты выполняются не там, где написаны

# Что напечатается первым?
def log_and_yield(items):
    for x in items:
        print("обрабатываю", x)
        yield x

gen = log_and_yield([1, 2, 3])
print("генератор создан")     # печатается ПЕРВЫМ — тело ещё не запущено
list(gen)

Пока эффект — print, это забавно. Когда эффект — запись в БД, отправка письма или захват блокировки, «отложенный побочный эффект» превращается в источник трудноуловимых багов. Правило: в ленивом конвейере держите только чистые функции; всё, что имеет эффект, выполняйте на границе, где конвейер форсируется. Это ровно та же дисциплина, что в статье Чистые функции, побочные эффекты и почему это меняет всё, а системный вариант границы — в статье Эффекты и ввод-вывод.

Отдельный случай — «ленивый IO» в Haskell (readFile/hGetContents): хендл закрывается по достижении конца, и легко получить чтение из уже закрытого файла или файл, не закрытый вовсе. Сообщество давно решило это через conduit, pipes и streaming — библиотеки, где потоки явно управляют ресурсами.

4. Исключение прилетает из другого места

Ленивое вычисление переносит не только работу, но и ошибки: деление на ноль, записанное в одном модуле, взорвётся в другом — там, где значение впервые понадобилось. Стектрейс покажет точку потребления, а не точку создания. Отладка ленивого кода — известная сложность: пошаговый дебаггер показывает не тот порядок, в котором вы читаете исходник.

5. Ленивость не бесплатна по константе

Каждый ленивый шаг — это аллокация замыкания, косвенный вызов и проверка «вычислено ли». На маленьких коллекциях строгий вариант выигрывает уверенно:

# На списке из 100 элементов Enum быстрее Stream: накладные расходы
# на построение композиции замыканий превышают экономию на проходах.
Enum.map(small, &f/1) |> Enum.filter(&p/1)     # быстрее
Stream.map(small, &f/1) |> Stream.filter(&p/1) |> Enum.to_list()  # медленнее

Эмпирическое правило: ленивость окупается, когда коллекция большая, шагов конвейера много, или потребитель забирает малую долю элементов (take, first, any). Меряйте, а не угадывайте — Benchee в Elixir, timeit в Python, criterion в Haskell.

6. Ленивость — не единственный способ убрать промежуточные коллекции

Есть две альтернативы, решающие ту же боль без отложенных вычислений:

• Fusion на уровне компилятора. GHC умеет превращать map f . filter p . map g в один цикл (short-cut fusion, foldr/build) — промежуточные списки не создаются вообще.
• Трансдьюсеры (Clojure). Композиция шагов преобразования, независимая от структуры источника: (comp (map f) (filter p) (take 3)) даёт одну функцию-редьюсер, которую можно применить к вектору, каналу или потоку. Промежуточных коллекций нет, а вычисление остаётся строгим и предсказуемым. Описание: https://clojure.org/reference/transducers.

Общая картина выбора:

Типичные ошибки

Многократный обход ленивой последовательности. В C#/LINQ отложенное выполнение означает, что каждый foreach заново выполняет запрос:

// Запрос к БД выполнится ДВА раза: Count() и foreach — два обхода.
var q = db.Orders.Where(o => o.Total > 1000);
Console.WriteLine(q.Count());
foreach (var o in q) { /* ... */ }

// Правильно: материализовать один раз.
var orders = db.Orders.Where(o => o.Total > 1000).ToList();

Анализаторы ловят это как «possible multiple enumeration» — не игнорируйте предупреждение. Подробнее о LINQ — в курсе C#.

Захват изменяемой переменной в ленивом замыкании. Ленивость откладывает чтение переменной до момента форсирования — к тому времени она уже другая:

funcs = [lambda: i for i in range(3)]
[f() for f in funcs]        # [2, 2, 2], а не [0, 1, 2]

funcs = [lambda i=i: i for i in range(3)]   # фиксируем значение при создании
[f() for f in funcs]        # [0, 1, 2]

Ленивый конвейер поверх ресурса, который закрывается раньше.

def bad():
    with open("data.csv") as f:
        return (line.split(",") for line in f)   # файл закроется на return

rows = bad()
next(rows)   # ValueError: I/O operation on closed file

Ресурс должен жить дольше конвейера: либо yield внутри with (тогда генератор владеет файлом), либо Stream.resource/3 в Elixir, либо bracket/ResourceT в Haskell.

Бесконечный источник плюс операция, требующая всей коллекции. sum(naturals()), Enum.sort(infinite_stream), length [1..] — зависание. Любая операция, которой нужен весь вход (сортировка, sum, max, reverse, группировка), несовместима с бесконечностью и обязана стоять после ограничителя.

Ленивость как «оптимизация по умолчанию». Оборачивать в Stream каждый пайплайн — карго-культ. Отладка усложняется, константа растёт, а выигрыш появляется только при выполнении условий из квадранта выше.

Как это выглядит в проде

• Обработка больших файлов и выгрузок. Построчный ленивый конвейер вместо read().split("\n") — самая частая и самая окупаемая победа: память из O(размер файла) становится O(размер строки).
• Пагинация внешних API. Оборачиваем «страница -> курсор -> следующая страница» в генератор: потребитель работает с плоской бесконечной последовательностью и не знает про пагинацию.

def paginate(fetch_page):
    """Скрывает пагинацию: снаружи — обычная последовательность."""
    cursor = None
    while True:
        page = fetch_page(cursor)
        yield from page.items          # HTTP-запрос — только когда исчерпана прошлая страница
        if not page.next_cursor:
            return
        cursor = page.next_cursor

• Курсорные выборки из БД. Server-side cursor (psycopg named cursor, Ecto.Repo.stream/2) + ленивый конвейер = выгрузка миллионов строк на константной памяти. Обязательное условие — держать транзакцию и явно её закрывать.
• Событийные конвейеры. Kafka/RabbitMQ-консьюмеры с явным спросом (GenStage/Broadway, Akka Streams, Reactor) — там ленивость превращается в контракт о нагрузке между сервисами.
• Мемоизация как частный случай call-by-need. functools.lru_cache, lazy val в Scala, Lazy<T> в .NET, React.lazy для кода компонентов — везде та же формула «отложить + запомнить».

Мини-итог

• Ленивость решает три конкретные боли: промежуточные коллекции, структуры без конца, вычисления «на всякий случай».
• Практическая ленивость — это call-by-need: thunk, который вычисляется при первом обращении и кэширует результат. Вычисление идёт до WHNF, то есть «на один конструктор вперёд».
• Итераторы и генераторы — pull-модель: спрос идёт от потребителя к источнику, и backpressure получается бесплатно. Push-модель (Observable) требует строить его вручную; гибрид (Reactive Streams, GenStage) передаёт спрос явным числом.
• Корекурсия — дуал рекурсии: unfold производит структуру, fold её потребляет. Это позволяет разделить «как порождать» и «когда остановиться» на два независимых куска.
• Stream в Elixir, генераторы в Python и TypeScript, IEnumerable в C#, Iterator Helpers в ES2025 — один и тот же инструмент с разными вывесками.
• Цена реальна: space leak и непредсказуемая память, эффекты и исключения не там, где написаны, тяжёлая отладка, накладные расходы на маленьких данных.
• Держите в ленивом конвейере только чистые функции. Эффекты — на границе форсирования, ресурсы — под явным управлением.
• Ленивость — не единственный ответ на промежуточные коллекции: fusion в компиляторе и трансдьюсеры решают ту же задачу строго и предсказуемо.

Что дальше

Ленивость дала нам структуры, которые не существуют целиком. Следующий шаг — структуры, которые существуют целиком, но переиспользуют друг друга: персистентные списки, деревья и HAMT, за счёт которых «копия при каждом изменении» стоит не O(n), а O(log n). Разберём их внутреннее устройство, реальные константы и то, где неизменяемость всё-таки обходится дороже, чем обещают.

Персистентные структуры данных и их реальная стоимость