List<A>

Иммутабельные связные списки.

Теория

Структура связного списка

List<A> — это классический функциональный связный список (singly-linked list):

List<A> = Cons<A> | Nil

  Cons(1, Cons(2, Cons(3, Nil)))

  Визуализация:

  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌─────┐
  │ 1 │ ──┼──►│ 2 │ ──┼──►│ 3 │ ──┼──►│ Nil │
  └───┴───┘   └───┴───┘   └───┴───┘   └─────┘
   head tail   head tail   head tail

  head(list) = 1
  tail(list) = Cons(2, Cons(3, Nil))

Ключевые свойства

┌─────────────────────────────────────────┐
│ Свойства List<A>:                       │
│                                         │
│ • Иммутабельный                         │
│ • Prepend (cons) — O(1)                 │
│ • Head/tail — O(1)                      │
│ • Append — O(n) (неэффективно!)         │
│ • Доступ по индексу — O(n)              │
│ • Structural sharing при prepend        │
│ • Рекурсивная структура                 │
└─────────────────────────────────────────┘

Structural Sharing

При добавлении в начало (prepend) хвост разделяется между старым и новым списком:

original = [2, 3, 4]

  ┌───┐   ┌───┐   ┌───┐
  │ 2 ├──►│ 3 ├──►│ 4 ├──► Nil
  └───┘   └───┘   └───┘
    ▲
    │
new = prepend(1, original)

  ┌───┐
  │ 1 ├──► (указывает на original)
  └───┘

  Обе структуры разделяют хвост [2, 3, 4].
  Копирования не происходит — O(1)!

Концепция ФП

Cons-list в функциональном программировании

Связный список — одна из фундаментальных структур данных в ФП. В Haskell:

Haskell              Effect-ts
─────────            ──────────
[1, 2, 3]           List.make(1, 2, 3)
1 : [2, 3]          List.prepend(List.make(2, 3), 1)
[]                   List.nil()
head xs              List.head(list)
tail xs              List.tail(list)
map f xs             List.map(list, f)
foldr f z xs         List.reduce(list, z, f)

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

List идеально подходит для рекурсивных алгоритмов — разделение на голову и хвост:

sum([])      = 0                   // базовый случай
sum(x :: xs) = x + sum(xs)        // рекурсивный случай

sum([1, 2, 3])
= 1 + sum([2, 3])
= 1 + 2 + sum([3])
= 1 + 2 + 3 + sum([])
= 1 + 2 + 3 + 0
= 6

Создание List

nil — пустой список

const empty = List.nil<number>()
// List.Nil — пустой список

make — из значений

const list = List.make(1, 2, 3, 4, 5)
// List.Cons<number> — непустой список

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

const single = List.of(42)
// List.Cons<number>

fromIterable — из Iterable

const fromArray = List.fromIterable([1, 2, 3])
const fromSet = List.fromIterable(new Set([1, 2, 3]))

cons — добавление в начало (prepend)

const tail = List.make(2, 3, 4)
const full = List.cons(1, tail)
// List(1, 2, 3, 4)

API Reference

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

Добавление

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

Head и Tail

const list = List.make(10, 20, 30)

const head = List.head(list)
// Some(10)

const tail = List.tail(list)
// Some(List(20, 30))

// Пустой список
List.head(List.nil()) // None
List.tail(List.nil()) // None

Prepend — основная операция O(1)

const list = List.make(2, 3, 4)

// Добавление в начало — самая эффективная операция
const withOne = List.prepend(list, 1)
// List(1, 2, 3, 4)

// Цепочка prepend
const full = List.nil<number>().pipe(
  List.prepend(3),
  List.prepend(2),
  List.prepend(1)
)
// List(1, 2, 3)

Reverse

const list = List.make(1, 2, 3, 4, 5)
const reversed = List.reverse(list)
// List(5, 4, 3, 2, 1)

Конкатенация

const a = List.make(1, 2, 3)
const b = List.make(4, 5, 6)

const combined = List.appendAll(a, b)
// List(1, 2, 3, 4, 5, 6)
// ⚠️ O(n) — нужно пройти весь первый список

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

map

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

flatMap

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

filter

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

reduce — свёртка

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

partition

const [left, right] = List.partition(
  List.make(1, 2, 3, 4, 5),
  (n) => n % 2 === 0
)
// left: List(1, 3, 5) — не удовлетворяют предикату
// right: List(2, 4) — удовлетворяют

forEach

List.forEach(List.make("a", "b", "c"), (s) => {
  console.log(s)
})

take / drop

const list = List.make(1, 2, 3, 4, 5)

List.take(list, 3)  // List(1, 2, 3)
List.drop(list, 2)  // List(3, 4, 5)

Конвертация

const list = List.make(1, 2, 3)

// В массив
const arr = List.toArray(list)
// [1, 2, 3]

// В Chunk
const chunk = Chunk.fromIterable(list)

List vs Chunk vs Array

┌──────────────────┬──────────────┬───────────────┬───────────────┐
│ Операция         │ List         │ Chunk         │ Array (RO)    │
├──────────────────┼──────────────┼───────────────┼───────────────┤
│ Prepend          │ O(1) ✅      │ O(1) amort    │ O(n)          │
│ Append           │ O(n)         │ O(1) amort ✅ │ O(1) amort    │
│ Concat           │ O(n)         │ O(1) amort ✅ │ O(n+m)        │
│ Index access     │ O(n)         │ O(log n)      │ O(1) ✅       │
│ Head/Tail        │ O(1) ✅      │ O(1)          │ O(1)          │
│ Immutable        │ ✅           │ ✅            │ ⚠️ ReadonlyArr│
│ Structural eq    │ ✅           │ ✅            │ ❌            │
│ Pattern match    │ head/tail ✅ │ ❌            │ ❌            │
│ Structural share │ ✅           │ Partial       │ ❌            │
├──────────────────┼──────────────┼───────────────┼───────────────┤
│ Лучший для       │ Prepend,     │ Concat,       │ Index access, │
│                  │ рекурсия,    │ Stream,       │ interop       │
│                  │ stack-like   │ batch ops     │               │
└──────────────────┴──────────────┴───────────────┴───────────────┘

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

✅ Используйте List:
  • Частые prepend операции (добавление в начало)
  • Stack-like паттерн (LIFO)
  • Рекурсивная обработка head/tail
  • Structural sharing важен для экономии памяти
  • Алгоритмы, обрабатывающие элементы последовательно

❌ Не используйте List:
  • Частый доступ по индексу
  • Частое добавление в конец (append)
  • Нужна эффективная конкатенация → используйте Chunk
  • Interop с DOM/сторонними API → используйте Array

Паттерны использования

Stack (LIFO)

// List — идеальная структура для стека
type Stack<A> = List.List<A>

const emptyStack = <A>(): Stack<A> => List.nil()

const push = <A>(stack: Stack<A>, value: A): Stack<A> =>
  List.prepend(stack, value) // O(1)

const pop = <A>(stack: Stack<A>): Option.Option<readonly [A, Stack<A>]> =>
  List.isCons(stack)
    ? Option.some([stack.head, stack.tail] as const)
    : Option.none()

const peek = <A>(stack: Stack<A>): Option.Option<A> =>
  List.head(stack)

// Использование
const stack = pipe(
  emptyStack<number>(),
  (s) => push(s, 1),
  (s) => push(s, 2),
  (s) => push(s, 3)
)
// Stack: [3, 2, 1] — 3 на вершине

Undo History

interface EditorState<A> {
  readonly current: A
  readonly history: List.List<A>
}

const init = <A>(value: A): EditorState<A> => ({
  current: value,
  history: List.nil()
})

const update = <A>(state: EditorState<A>, newValue: A): EditorState<A> => ({
  current: newValue,
  history: List.prepend(state.history, state.current) // O(1)
})

const undo = <A>(state: EditorState<A>): Option.Option<EditorState<A>> =>
  List.isCons(state.history)
    ? Option.some({
        current: state.history.head,
        history: state.history.tail
      })
    : Option.none()

Построение списка в обратном порядке

// Эффективное построение: prepend + reverse
const buildList = (n: number): List.List<number> => {
  let result = List.nil<number>()
  for (let i = n; i >= 1; i--) {
    result = List.prepend(result, i) // O(1)
  }
  return result
}
// List(1, 2, 3, ..., n)

// Или: prepend в прямом порядке + reverse
const buildListAlt = (n: number): List.List<number> => {
  let result = List.nil<number>()
  for (let i = 1; i <= n; i++) {
    result = List.prepend(result, i) // O(1)
  }
  return List.reverse(result) // O(n) — один раз
}

Упражнения

import { List } from "effect"

const sumAndProduct = (list: List.List<number>): { readonly sum: number; readonly product: number } => {
  // Ваш код
}

// sumAndProduct(List.make(1,2,3,4)) → { sum: 10, product: 24 }

import { List } from "effect"

const interleave = <A>(a: List.List<A>, b: List.List<A>): List.List<A> => {
  // Ваш код
  // interleave(List(1,2,3), List(4,5,6)) → List(1,4,2,5,3,6)
}

import { List, Order } from "effect"

const mergeSort = <A>(list: List.List<A>, ord: Order.Order<A>): List.List<A> => {
  // Ваш код
}

// mergeSort(List.make(5,3,1,4,2), Order.number)
// → List(1, 2, 3, 4, 5)