Chunk<A>

Иммутабельные массивы с оптимизированной конкатенацией.

Теория

Проблема мутабельных массивов

Стандартный JavaScript Array — мутабельная структура данных. Это создаёт проблемы в функциональном и конкурентном программировании:

Проблемы Array:

  const arr = [1, 2, 3]
  someFunction(arr)
  // arr мог измениться! 💥

  ┌───────────────────────────────────────┐
  │  1. push/pop/splice изменяют оригинал │
  │  2. Нет structural equality           │
  │  3. Конкатенация — O(n+m)             │
  │  4. Небезопасно при конкурентности    │
  └───────────────────────────────────────┘

Что такое Chunk

Chunk<A> — это иммутабельная, упорядоченная коллекция элементов типа A:

Chunk<number> = [1, 2, 3, 4, 5]

  ┌───────────────────────────────────────┐
  │           Chunk<number>               │
  │                                       │
  │  Свойства:                            │
  │  • Иммутабельная (нельзя изменить)    │
  │  • Упорядоченная (индексы стабильны)  │
  │  • Structural equality                │
  │  • Оптимизирована для конкатенации    │
  │  • Implements Iterable                │
  └───────────────────────────────────────┘

Внутренняя структура

Chunk использует “rope-like” структуру для оптимизации конкатенации:

Обычный массив — конкатенация O(n):
  [1,2,3] + [4,5] → копирование → [1,2,3,4,5]

Chunk — конкатенация O(1) (amortized):
  Chunk(1,2,3) + Chunk(4,5) → AppendAll node
                               /           \
                    Chunk(1,2,3)    Chunk(4,5)

  Материализация в массив происходит лениво, только при доступе.

Зачем Chunk если есть Array

┌────────────────────┬──────────────┬────────────────────┐
│    Операция        │   Array      │   Chunk            │
├────────────────────┼──────────────┼────────────────────┤
│ Конкатенация       │ O(n + m)     │ O(1) amortized     │
│ Append 1 элемент   │ O(n) (copy)  │ O(1) amortized     │
│ Prepend 1 элемент  │ O(n)         │ O(1) amortized     │
│ Индексный доступ   │ O(1)         │ O(log n) worst     │
│ Иммутабельность    │ Нет          │ Да                 │
│ Structural eq      │ Нет          │ Да (Equal)         │
│ Итерация           │ O(n)         │ O(n)               │
│ Использование в FP │ ⚠️ Unsafe    │ ✅ Safe            │
└────────────────────┴──────────────┴────────────────────┘

⚠️ Когда использовать Chunk: Chunk оптимизирован для повторной конкатенации (например, при построении результатов в Stream). Для случаев, не связанных с повторной конкатенацией, обычный ReadonlyArray может быть эффективнее.

Создание Chunk

empty — пустой Chunk

const empty = Chunk.empty<number>()
// Chunk<number> — пустой

make — из набора значений

// NonEmptyChunk<number> — компилятор знает, что не пустой
const chunk = Chunk.make(1, 2, 3)

of — одноэлементный Chunk

const single = Chunk.of(42)
// NonEmptyChunk<number> с одним элементом

fromIterable — из любого Iterable

// Из массива (создаёт копию)
const fromArray = Chunk.fromIterable([1, 2, 3])

// Из Set
const fromSet = Chunk.fromIterable(new Set([1, 2, 3]))

// Из генератора
function* range(start: number, end: number) {
  for (let i = start; i <= end; i++) yield i
}
const fromGenerator = Chunk.fromIterable(range(1, 5))

unsafeFromArray — без копирования

// ⚠️ НЕ создаёт копию! Используйте осторожно
const chunk = Chunk.unsafeFromArray([1, 2, 3])
// Если исходный массив будет изменён — Chunk тоже "изменится"

⚠️ unsafeFromArray нарушает гарантию иммутабельности. Используйте только когда уверены, что исходный массив не будет модифицирован (например, массив создан как литерал прямо в вызове).

API Reference

Основные свойства

Добавление элементов

Удаление элементов

Основные операции

Добавление и конкатенация

const base = Chunk.make(1, 2, 3)

// Добавление в конец — O(1)
const withFour = Chunk.append(base, 4)
// Chunk(1, 2, 3, 4)

// Добавление в начало — O(1)
const withZero = Chunk.prepend(base, 0)
// Chunk(0, 1, 2, 3)

// Конкатенация — O(1)
const merged = Chunk.appendAll(
  Chunk.make(1, 2),
  Chunk.make("a", "b")
)
// Chunk(1, 2, "a", "b") — NonEmptyChunk<string | number>

Доступ к элементам

const chunk = Chunk.make(10, 20, 30, 40, 50)

// Безопасный доступ — Option
const third = Chunk.get(chunk, 2)
// Some(30)

const outOfBounds = Chunk.get(chunk, 10)
// None

// Первый и последний
Chunk.head(chunk) // Some(10)
Chunk.last(chunk) // Some(50)

// Небезопасный доступ — throws если нет
const value = Chunk.unsafeGet(chunk, 0) // 10

Срезы

const chunk = Chunk.make(1, 2, 3, 4, 5)

// Взять первые 3 элемента
Chunk.take(chunk, 3)
// Chunk(1, 2, 3)

// Убрать первые 2
Chunk.drop(chunk, 2)
// Chunk(3, 4, 5)

// Взять последние 2
Chunk.takeRight(chunk, 2)
// Chunk(4, 5)

// Убрать последние 2
Chunk.dropRight(chunk, 2)
// Chunk(1, 2, 3)

// Условные срезы
Chunk.takeWhile(chunk, (n) => n < 4)
// Chunk(1, 2, 3)

Chunk.dropWhile(chunk, (n) => n < 3)
// Chunk(3, 4, 5)

Разделение

const chunk = Chunk.make(1, 2, 3, 4, 5, 6)

// splitAt — разделить по индексу
const [left, right] = Chunk.splitAt(chunk, 3)
// left: Chunk(1, 2, 3), right: Chunk(4, 5, 6)

// splitWhere — разделить по условию
const [before, after] = Chunk.splitWhere(chunk, (n) => n > 3)
// before: Chunk(1, 2, 3), after: Chunk(4, 5, 6)

Трансформации

map — преобразование элементов

const doubled = Chunk.map(Chunk.make(1, 2, 3), (n) => n * 2)
// Chunk(2, 4, 6)

flatMap — плоская трансформация

const expanded = Chunk.flatMap(
  Chunk.make(1, 2, 3),
  (n) => Chunk.make(n, n * 10)
)
// Chunk(1, 10, 2, 20, 3, 30)

filter — фильтрация

const evens = Chunk.filter(
  Chunk.make(1, 2, 3, 4, 5, 6),
  (n) => n % 2 === 0
)
// Chunk(2, 4, 6)

partition — разделение по предикату

const [odds, evens] = Chunk.partition(
  Chunk.make(1, 2, 3, 4, 5),
  (n) => n % 2 === 0
)
// odds: Chunk(1, 3, 5)
// evens: Chunk(2, 4)

reduce — свёртка

const sum = Chunk.reduce(
  Chunk.make(1, 2, 3, 4, 5),
  0,
  (acc, n) => acc + n
)
// 15

compact — убрать None

const withNones = Chunk.make(
  Option.some(1),
  Option.none(),
  Option.some(3),
  Option.none(),
  Option.some(5)
)

const compacted = Chunk.compact(withNones)
// Chunk(1, 3, 5)

dedupe — удаление дубликатов

const unique = Chunk.dedupe(Chunk.make(1, 2, 2, 3, 3, 3, 4))
// Chunk(1, 2, 3, 4)

reverse — реверс

const reversed = Chunk.reverse(Chunk.make(1, 2, 3))
// Chunk(3, 2, 1)

sort — сортировка

const sorted = Chunk.sort(Order.number)(
  Chunk.make(3, 1, 4, 1, 5, 9)
)
// Chunk(1, 1, 3, 4, 5, 9)

zip — попарное объединение

const zipped = Chunk.zip(
  Chunk.make("a", "b", "c"),
  Chunk.make(1, 2, 3)
)
// Chunk(["a", 1], ["b", 2], ["c", 3])

Поиск и фильтрация

findFirst / findLast

const chunk = Chunk.make(1, 2, 3, 4, 5)

const firstEven = Chunk.findFirst(chunk, (n) => n % 2 === 0)
// Some(2)

const lastEven = Chunk.findLast(chunk, (n) => n % 2 === 0)
// Some(4)

some / every

const chunk = Chunk.make(2, 4, 6, 8)

Chunk.some(chunk, (n) => n > 5)  // true
Chunk.every(chunk, (n) => n % 2 === 0) // true

Конвертация

В ReadonlyArray

// Chunk → ReadonlyArray
const arr = Chunk.toReadonlyArray(Chunk.make(1, 2, 3))
// readonly [number, ...number[]] — тип сохраняет NonEmpty информацию

const emptyArr = Chunk.toReadonlyArray(Chunk.empty())
// readonly never[]

declare const genericChunk: Chunk.Chunk<number>
const genericArr = Chunk.toReadonlyArray(genericChunk)
// readonly number[]

Сравнение (structural equality)

const a = Chunk.make(1, 2, 3)
const b = Chunk.make(1, 2, 3)
const c = Chunk.make(1, 2, 4)

Equal.equals(a, b) // true — structural equality!
Equal.equals(a, c) // false

// Сравнение с самим собой
Equal.equals(a, a) // true

Chunk в экосистеме Effect

Chunk — основная коллекция в экосистеме Effect. Он используется повсеместно:

В Stream

// Stream.runCollect возвращает Chunk
const result = Stream.make(1, 2, 3, 4, 5).pipe(
  Stream.filter((n) => n % 2 === 0),
  Stream.runCollect
)

Effect.runPromise(result).then(console.log)
// { _id: 'Chunk', values: [ 2, 4 ] }

В Cause

// Cause.failures возвращает Chunk
const program = Effect.gen(function* () {
  const cause = yield* Effect.cause(Effect.fail("error"))
  const failures = Cause.failures(cause)
  // Chunk<string>
})

В Queue

const program = Effect.gen(function* () {
  const queue = yield* Queue.bounded<number>(10)
  yield* Queue.offerAll(queue, [1, 2, 3])
  const chunk = yield* Queue.takeAll(queue)
  // chunk: Chunk<number>
})

Производительность

Бенчмарки конкатенации

Повторная конкатенация (10 000 итераций):

  Array.concat:    ~150ms   (каждый раз полное копирование)
  Chunk.appendAll: ~5ms     (ленивые узлы, без копирования)
  Speedup:         ~30x

Когда использовать Chunk

✅ Используйте Chunk:
  • Stream processing (runCollect, Sink)
  • Повторная конкатенация в циклах
  • Когда нужна structural equality
  • При работе с Effect API (Queue, Cause)
  • При построении результата из частей

❌ Используйте ReadonlyArray:
  • Частый доступ по индексу
  • Однократное создание без конкатенации
  • Interop с DOM API / сторонними библиотеками
  • Когда производительность доступа критичнее конкатенации

Упражнения

import { Chunk, pipe } from "effect"

const result = // Ваш код

// Ожидается: Chunk(4, 8, 12, 16, 20)

import { Chunk } from "effect"

const toPairs = <A>(chunk: Chunk.Chunk<A>): Chunk.Chunk<readonly [A, A]> => {
  // Ваш код
  // Chunk(1,2,3,4) → Chunk([1,2], [3,4])
  // Если нечётное количество — последний элемент отбрасывается
}

import { Chunk } from "effect"

const slidingWindow = <A>(
  chunk: Chunk.Chunk<A>,
  windowSize: number
): Chunk.Chunk<Chunk.Chunk<A>> => {
  // Ваш код
  // Chunk(1,2,3,4,5), size=3 → Chunk(Chunk(1,2,3), Chunk(2,3,4), Chunk(3,4,5))
}

import { Chunk } from "effect"

type RLEEntry<A> = { readonly value: A; readonly count: number }

const encode = <A>(chunk: Chunk.Chunk<A>): Chunk.Chunk<RLEEntry<A>> => {
  // Ваш код
  // Chunk("a","a","b","b","b","c") → Chunk({value:"a",count:2}, {value:"b",count:3}, {value:"c",count:1})
}

const decode = <A>(encoded: Chunk.Chunk<RLEEntry<A>>): Chunk.Chunk<A> => {
  // Ваш код
}