indirect enum і рекурсивні структури даних

1. Дерево даних

Перш ніж говорити про рекурсивні структури даних, корисно познайомитися з однією простою моделлю — деревом. Дерево — це структура, де елементи можуть містити інші елементи того самого типу. Тому вона виходить вкладеною.

Найзнайоміший приклад — файлова система. Папка може містити файли й інші папки. А всередині кожної папки знову можуть бути файли й папки. Якщо намалювати таку структуру, вона виглядає приблизно так:

flowchart TD
    A["Документи"] --> B["report.pdf"]
    A --> C["Проєкти"]
    C --> D["code.swift"]
    C --> E["Архів"]
    E --> F["old.txt"]

Такі структури називають деревами, тому що вони справді нагадують дерево:

• є корінь — верхній елемент
• є гілки — елементи, які містять інші елементи
• є листки — елементи без вкладених елементів

У нашому прикладі:

• Документи, Проєкти, Архів — вузли
• report.pdf, code.swift, old.txt — листки

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

2. Рекурсивні структури даних

Коли дані мають таку вкладену форму, їх називають рекурсивними структурами даних. Це означає, що тип даних може містити значення того самого типу. Наприклад, математичний вираз:

2 + (3 + 4)

Зовні це додавання. Але праворуч теж є додавання.

Якщо зобразити структуру виразу, вийде дерево:

flowchart TD
    A["+"] --> B["2"]
    A --> C["+"]
    C --> D["3"]
    C --> E["4"]

Тут:

• числа — листки
• операції — вузли, які з’єднують підвирази

Виходить цікава ситуація: вираз може складатися з інших виразів. Саме тут виникає природне запитання: як у Swift описати тип, який може містити самого себе?

Звичайні структури й перелічення так описати напряму не можна — компілятор має розуміти розмір значення в пам’яті. Тому Swift використовує спеціальний механізм для таких випадків. У наступних розділах я познайомлю вас з інструментом, який дає змогу описувати такі структури: рекурсивний enum із ключовим словом indirect.

3. Швидкий огляд enum і case з даними

enum як «один варіант із кількох»

Слово enum (enumeration) звучить серйозно, але на базовому рівні це просто тип, який може зберігати один із кількох станів. За змістом це дуже схоже на switch: там ви обираєте гілку за значенням, а enum дозволяє заздалегідь сказати: «ось які варіанти взагалі бувають».

Важливо: ми ще не вивчаємо enum повноцінно (це буде окрема тема пізніше). Сьогодні — лише стільки, скільки потрібно, щоб зрозуміти рекурсивну структуру.

Найпростіший enum виглядає так:

import Foundation

enum LampState {
    case on
    case off
}

let state: LampState = .on
print(state) // on

Зверніть увагу на крапку .on: Swift часто дозволяє не писати ім’я типу ліворуч (LampState.on), якщо компілятор і так розуміє контекст.

І типовий спосіб «розкрити» enum — це switch:

import Foundation

enum LampState { case on, off }

func describe(_ state: LampState) -> String {
    switch state {
    case .on:  return "Лампа світить"
    case .off: return "Лампа відпочиває"
    }
}

print(describe(.off)) // Лампа відпочиває

case з корисним навантаженням

До цього case on/off були просто мітками. Але в enum є особливість: case може зберігати дані. Це схоже на те, ніби ви сказали: «Повідомлення буває двох типів: текст або число», і тоді в «тексту» буде рядок усередині, а в «числа» — число.

Приклад:

import Foundation

enum Input {
    case number(Int)
    case text(String)
}

let x: Input = .number(42)
print(x) // number(42)

Дістаємо дані через switch — і це виглядає майже як акуратне розпакування «контейнера»:

import Foundation

enum Input { case number(Int), text(String) }

func printInput(_ value: Input) {
    switch value {
    case .number(let n):
        print("Число: \(n)")        // Число: 42
    case .text(let s):
        print("Рядок: \(s)")
    }
}

printInput(.number(42))

Ось цей запис case .number(let n) — фундаментальна техніка. І саме вона буде головним інструментом, коли ми почнемо обробляти рекурсивну структуру: кожен вузол «розкривається» через switch, ми дивимося, що всередині, і вирішуємо, що робити далі.

4. Рекурсивний enum і ключове слово indirect

Проблема: як описати вкладеність у типах

Тепер до суті. Хочемо дуже спрощено описати вираз:

• вираз може бути числом
• або сумою двох виразів

Тобто тип виглядає приблизно так:

• number(Int)
• add(Expr, Expr) — ліворуч вираз і праворуч вираз

І тут у голові виникає маленька паніка: «Зачекайте… Expr містить Expr… отже Expr містить Expr, який містить Expr… це ж нескінченно!»

Якби компілятор спробував зберігати таке значення цілком усередині, йому знадобилася б нескінченна пам’ять. Тому Swift вимагає явного механізму, який скаже: «Рекурсивна частина зберігається не напряму, а через спеціальну опосередкованість».

І ось тут з’являється ключове слово indirect. Воно буквально означає саме це: зберігати «опосередковано».

indirect enum: мінімальна робоча модель дерева

Тепер зберемо наш «тип виразу». Запам’ятовувати синтаксис напам’ять не треба — важлива сама ідея: лист і вузол.

import Foundation

enum Expr {
    case number(Int)
    indirect case add(Expr, Expr)
}

Пояснімо по-людськи:

• Expr.number(5) — це лист дерева: усередині просто число.
• Expr.add(left, right) — це вузол дерева: усередині два підвирази.

Ключове слово indirect стоїть на кейсі add, тому що саме він рекурсивно звертається до Expr ще раз.

Створимо значення:

import Foundation

enum Expr {
    case number(Int)
    indirect case add(Expr, Expr)
}

let expr: Expr = .add(.number(2), .add(.number(3), .number(4)))
print(expr) // add(number(2), add(number(3), number(4)))

І ось це важливо: ми вже отримали вкладену структуру даних. Поки що ми її не обчислюємо і не розбираємо глибше — лише навчилися описувати і будувати.

Листок і вузол як спосіб мислити

Щоб не плутатися, тримайте просту таблицю-підказку:

.number(…)

.add(left, right)

Вкладеність виникає автоматично: якщо left/right теж Expr, то вони можуть бути і листками, і вузлами, і вузлами з вузлів — і так далі.

Два способи записати indirect

Коли структура невелика, частіше пишуть indirect на конкретному кейсі, як ми й зробили. Але Swift дозволяє оголосити опосередкованість одразу для всього перелічення, якщо ви наперед знаєте, що рекурсія з’явиться в багатьох місцях.

Виглядає це так:

import Foundation

indirect enum Expr {
    case number(Int)
    case add(Expr, Expr)
}

Обидва варіанти правильні, але між ними є невелика різниця:

• indirect case add(...) — точково: «ось цей кейс рекурсивний».
• indirect enum Expr — загалом: «це перелічення може бути рекурсивним».

Для навчальних прикладів точковий indirect case часто читається простіше: ви одразу бачите, де починається магія вкладеності.

5. Мініпроєкт: Expression Playground

Вбудовуємо в консольний застосунок

Щоб не залишати Expr музейним експонатом у стилі «подивіться й не чіпайте», додамо його до маленького консольного застосунку: читаємо введення, обираємо сценарій, друкуємо результат. Це буде той самий стиль коду верхнього рівня, який ви вже використовували раніше, тільки тепер дані будуть вкладеними.

Зробімо вибір із двох готових виразів: простого й вкладеного.

import Foundation

enum Expr {
    case number(Int)
    indirect case add(Expr, Expr)
}

let choice = Int(readLine() ?? "") ?? 1

let expr: Expr = (choice == 1)
    ? .add(.number(2), .number(3))
    : .add(.number(2), .add(.number(3), .number(4)))

print(expr)
// choice=1 -> add(number(2), number(3))
// choice=2 -> add(number(2), add(number(3), number(4)))

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

Чому без indirect не можна

Часта реакція новачків: «Навіщо це ключове слово? Чому Swift сам не здогадається?»

Проблема в тому, що якби Expr.add(Expr, Expr) зберігав Expr напряму, то розмір Expr у пам’яті мав би включати розмір двох Expr, кожен із яких включає розмір двох Expr, і так далі до нескінченності. Компілятор не може обрати скінченний розмір для такого значення.

indirect каже компілятору: «Рекурсивна частина зберігатиметься опосередковано (через окрему коробочку або посилання)». Вам не потрібно зараз запам’ятовувати, як саме це зроблено всередині — достатньо знати, що це спосіб розв’язати рекурсію в даних, а не в коді.

Мікро-розширення: додамо ще один вузол

Щоб переконатися, що indirect enum — це не «трюк заради трюку», розширимо вираз ще одним варіантом, наприклад множенням. Суть та сама: листки й вузли.

import Foundation

enum Expr {
    case number(Int)
    indirect case add(Expr, Expr)
    indirect case mul(Expr, Expr)
}

let expr: Expr = .mul(.add(.number(2), .number(3)), .number(4))
print(expr) // mul(add(number(2), number(3)), number(4))

Зверніть увагу, що модель стала багатшою, а код створення значення залишився зрозумілим: ми просто збираємо дерево, як конструктор із кубиків.

6. Типові помилки

Помилка №1: спроба «зрозуміти рекурсивний enum», не виділяючи лист і вузол.
Якщо ви не домовилися самі з собою, який кейс є «простим» (листом), а який — «складеним» (вузлом), то тип починає виглядати як каша: усе змішано. У таких моделях майже завжди потрібно явно мати хоча б один базовий варіант на кшталт .number, .text, .file — те, що не містить у собі значення того самого типу.

Помилка №2: забули indirect і здивувалися помилці компілятора.
Це класика: написали case add(Expr, Expr) без indirect і отримали повідомлення, схоже на recursive enum is not marked ‘indirect’. Це не прискіпливість Swift і не «зламаний компілятор», а захист від нескінченного розміру значення. Або ставте indirect на рекурсивні кейси, або робіть indirect для всього enum.

Помилка №3: спроба одразу парсити вираз із рядка.
Щойно ви намагаєтеся перетворити "2 + (3 + 4)" на внутрішню структуру, ви раптово впираєтеся в токени, пробіли, пріоритет операторів, дужки й питання «а що, якщо користувач увів нісенітницю». Це окрема задача. У навчальній моделі сьогодні краще чесно будувати дерево вручну або обирати з кількох заготовок через readLine().

Помилка №4: змішування структури даних і логіки обробки.
Дуже хочеться зробити enum Expr і одразу всередині написати все підряд: і друк, і обчислення, і підрахунок вузлів, і перевірку коректності. На першому знайомстві це перевантажує і заважає побачити головне: indirect enum — це насамперед форма даних (лист/вузол), а «що ми з нею робимо» — окремий шар.

Помилка №5: очікування, що print(expr) виведе гарно.
За замовчуванням вивід enum — це радше діагностичний рядок, а не математичний запис. Побачити add(number(2), add(...)) — нормально. «Людське» форматування — окреме завдання, і воно стає зрозумілим саме тоді, коли ви вже впевнено розрізняєте лист і вузол та можете обробляти їх через switch.