382 lines
15 KiB
Markdown
382 lines
15 KiB
Markdown
# Отчёт по лабораторной работе №2
|
||
|
||
**Университет ИТМО**
|
||
**Факультет программной инженерии и компьютерной техники**
|
||
|
||
**Студент:** Владимиров Владислав Александрович
|
||
**Группа:** P3322
|
||
|
||
**Тема:** Реализация Red-Black Tree с ленивыми вычислениями
|
||
**Лабораторная работа №2**
|
||
**Дисциплина:** Функциональное программирование
|
||
|
||
---
|
||
|
||
## Требования к разработанному ПО
|
||
|
||
### Цель работы
|
||
Цель: освоиться с построением пользовательских типов данных, полиморфизмом, рекурсивными алгоритмами и средствами тестирования (unit testing, property-based testing), а также разделением интерфейса и особенностей реализации.
|
||
|
||
В рамках лабораторной работы вам предлагается реализовать одну из предложенных классических структур данных (список, дерево, бинарное дерево, hashmap, граф...).
|
||
|
||
Требования:
|
||
|
||
1. Функции:
|
||
- добавление и удаление элементов;
|
||
- фильтрация;
|
||
- отображение (map);
|
||
- свертки (левая и правая);
|
||
- структура должна быть [моноидом](https://ru.m.wikipedia.org/wiki/Моноид).
|
||
2. Структуры данных должны быть неизменяемыми.
|
||
3. Библиотека должна быть протестирована в рамках unit testing.
|
||
4. Библиотека должна быть протестирована в рамках property-based тестирования (как минимум 3 свойства, включая свойства моноида).
|
||
5. Структура должна быть полиморфной.
|
||
6. Требуется использовать идиоматичный для технологии стиль программирования. Примечание: некоторые языки позволяют получить большую часть API через реализацию небольшого интерфейса. Так как лабораторная работа про ФП, а не про экосистему языка -- необходимо реализовать их вручную и по возможности -- обеспечить совместимость.
|
||
7. Обратите внимание:
|
||
- API должно быть реализовано для заданного интерфейса и оно не должно "протекать". На уровне тестов -- в первую очередь нужно протестировать именно API (dict, set, bag).
|
||
- Должна быть эффективная реализация функции сравнения (не наивное приведение к спискам, их сортировка с последующим сравнением), реализованная на уровне API, а не внутреннего представления.
|
||
|
||
|
||
|
||
### Вариант задания
|
||
**Red-Black Tree Lazy** - красно-чёрное дерево на ленивых вычислениях.
|
||
|
||
### Функциональные требования
|
||
|
||
1. **Основные операции:**
|
||
- Добавление элементов (`insert`)
|
||
- Удаление элементов (`delete`)
|
||
- Фильтрация (`filter`)
|
||
- Отображение (`map`)
|
||
- Свёртки левая и правая (`fold_left`, `fold_right`)
|
||
|
||
2. **Структурные требования:**
|
||
- Структура должна быть моноидом
|
||
- Неизменяемые структуры данных
|
||
- Полиморфная реализация
|
||
- Использование ленивых вычислений
|
||
|
||
3. **Требования к тестированию:**
|
||
- Unit testing для всех функций
|
||
- Property-based тестирование (минимум 3 свойства)
|
||
- Тестирование свойств моноида
|
||
|
||
### Технические требования
|
||
|
||
- **Язык программирования:** Gleam
|
||
- **Сложность операций:** O(log n) для insert, delete, lookup
|
||
- **API не должно "протекать"**
|
||
- **Эффективная реализация сравнения деревьев**
|
||
- **Идиоматичный стиль программирования**
|
||
|
||
---
|
||
|
||
## Ключевые элементы реализации
|
||
|
||
### Основные типы данных
|
||
|
||
```gleam
|
||
// Цвета узлов красно-черного дерева
|
||
pub type Color {
|
||
Red
|
||
Black
|
||
}
|
||
|
||
// Ленивое значение для отложенных вычислений
|
||
pub type Lazy(a) {
|
||
Thunk(fn() -> a) // Отложенное вычисление
|
||
Value(a) // Уже вычисленное значение
|
||
}
|
||
|
||
// Красно-черное дерево с ленивыми вычислениями
|
||
pub type RBTree(k, v) {
|
||
Empty // Пустое дерево
|
||
Node(
|
||
color: Color, // Цвет узла
|
||
key: k, // Ключ
|
||
value: v, // Значение
|
||
left: Lazy(RBTree(k, v)), // Левое поддерево (ленивое)
|
||
right: Lazy(RBTree(k, v)), // Правое поддерево (ленивое)
|
||
)
|
||
}
|
||
```
|
||
|
||
### Управление ленивыми вычислениями
|
||
|
||
```gleam
|
||
// Форсирует вычисление ленивого значения
|
||
fn force(lazy: Lazy(a)) -> a {
|
||
case lazy {
|
||
Value(val) -> val
|
||
Thunk(f) -> f()
|
||
}
|
||
}
|
||
|
||
// Создаёт ленивое значение из функции
|
||
fn delay(f: fn() -> a) -> Lazy(a) {
|
||
Thunk(f)
|
||
}
|
||
```
|
||
|
||
### Балансировка красно-чёрного дерева
|
||
|
||
Реализованы 4 случая нарушения инвариантов Red-Black Tree:
|
||
|
||
```gleam
|
||
n balance(
|
||
color: Color,
|
||
key: k,
|
||
value: v,
|
||
left: Lazy(RBTree(k, v)),
|
||
right: Lazy(RBTree(k, v)),
|
||
) -> RBTree(k, v) {
|
||
let left_tree = force(left)
|
||
let right_tree = force(right)
|
||
|
||
case color, left_tree, right_tree {
|
||
// Случай 1: красный левый дедушка с красными детьми
|
||
Black, Node(Red, lk, lv, ll, lr), r ->
|
||
case force(ll) {
|
||
Node(Red, llk, llv, lll, llr) ->
|
||
Node(
|
||
Red,
|
||
lk,
|
||
lv,
|
||
delay(fn() { Node(Black, llk, llv, lll, llr) }),
|
||
delay(fn() { Node(Black, key, value, lr, Value(r)) }),
|
||
)
|
||
_ ->
|
||
case force(lr) {
|
||
Node(Red, lrk, lrv, lrl, lrr) ->
|
||
Node(
|
||
Red,
|
||
lrk,
|
||
lrv,
|
||
delay(fn() { Node(Black, lk, lv, ll, lrl) }),
|
||
delay(fn() { Node(Black, key, value, lrr, Value(r)) }),
|
||
)
|
||
_ -> Node(color, key, value, left, right)
|
||
}
|
||
}
|
||
|
||
// Случай 3: красный правый дедушка с красным левым внуком
|
||
Black, l, Node(Red, rk, rv, rl, rr) ->
|
||
case force(rl) {
|
||
Node(Red, rlk, rlv, rll, rlr) ->
|
||
Node(
|
||
Red,
|
||
rlk,
|
||
rlv,
|
||
delay(fn() { Node(Black, key, value, Value(l), rll) }),
|
||
delay(fn() { Node(Black, rk, rv, rlr, rr) }),
|
||
)
|
||
_ ->
|
||
case force(rr) {
|
||
Node(Red, rrk, rrv, rrl, rrr) ->
|
||
Node(
|
||
Red,
|
||
rk,
|
||
rv,
|
||
delay(fn() { Node(Black, key, value, Value(l), rl) }),
|
||
delay(fn() { Node(Black, rrk, rrv, rrl, rrr) }),
|
||
)
|
||
_ -> Node(color, key, value, left, right)
|
||
}
|
||
}
|
||
|
||
// Базовый случай - балансировка не нужна
|
||
_, _, _ -> Node(color, key, value, left, right)
|
||
}
|
||
}
|
||
```
|
||
|
||
### Основные операции
|
||
|
||
**Главное - сравнение**
|
||
```gleam
|
||
// Вспомогательная функция для структурного сравнения деревьев
|
||
// Использует замыкание при первом несовпадении
|
||
fn equal(
|
||
tree1: RBTree(k, v),
|
||
tree2: RBTree(k, v),
|
||
key_compare: fn(k, k) -> Bool,
|
||
value_compare: fn(v, v) -> Bool,
|
||
) -> Bool {
|
||
case tree1, tree2 {
|
||
// Оба дерева пустые - равны
|
||
Empty, Empty -> True
|
||
|
||
Empty, _ -> False
|
||
_, Empty -> False
|
||
|
||
Node(color1, key1, value1, left1, right1),
|
||
Node(color2, key2, value2, left2, right2)
|
||
-> {
|
||
color1 == color2
|
||
// Ключи должны быть равны
|
||
&& key_compare(key1, key2)
|
||
// Значения должны быть равны
|
||
&& value_compare(value1, value2)
|
||
// Рекурсивно проверяем левые поддеревья (ленивые)
|
||
&& equal_helper(force(left1), force(left2), key_compare, value_compare)
|
||
// Рекурсивно проверяем правые поддеревья (ленивые)
|
||
&& equal_helper(force(right1), force(right2), key_compare, value_compare)
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
**Вставка элемента:**
|
||
```gleam
|
||
pub fn insert(tree: RBTree(k, v), key: k, value: v,
|
||
compare: fn(k, k) -> Order) -> RBTree(k, v) {
|
||
let result = insert_helper(tree, key, value, compare)
|
||
make_black(result) // Корень всегда чёрный
|
||
}
|
||
```
|
||
|
||
**Поиск элемента:**
|
||
```gleam
|
||
pub fn lookup(tree: RBTree(k, v), key: k,
|
||
compare: fn(k, k) -> Order) -> Option(v) {
|
||
case tree {
|
||
Empty -> None
|
||
Node(_, k, v, left, right) ->
|
||
case compare(key, k) {
|
||
order.Lt -> lookup(force(left), key, compare)
|
||
order.Gt -> lookup(force(right), key, compare)
|
||
order.Eq -> Some(v)
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### Функции высшего порядка
|
||
|
||
**Отображение:**
|
||
```gleam
|
||
pub fn map(tree: RBTree(k, v), f: fn(v) -> w) -> RBTree(k, w) {
|
||
case tree {
|
||
Empty -> Empty
|
||
Node(color, key, value, left, right) ->
|
||
Node(color, key, f(value),
|
||
delay(fn() { map(force(left), f) }),
|
||
delay(fn() { map(force(right), f) }))
|
||
}
|
||
}
|
||
```
|
||
|
||
**Левая свёртка:**
|
||
```gleam
|
||
pub fn fold_left(tree: RBTree(k, v), acc: a, f: fn(a, k, v) -> a) -> a {
|
||
case tree {
|
||
Empty -> acc
|
||
Node(_, key, value, left, right) -> {
|
||
let left_acc = fold_left(force(left), acc, f)
|
||
let current_acc = f(left_acc, key, value)
|
||
fold_left(force(right), current_acc, f)
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### Операции моноида
|
||
|
||
```gleam
|
||
// Нейтральный элемент
|
||
pub fn mempty() -> RBTree(k, v) {
|
||
empty()
|
||
}
|
||
|
||
// Операция объединения
|
||
pub fn concat(tree1: RBTree(k, v), tree2: RBTree(k, v),
|
||
compare: fn(k, k) -> Order) -> RBTree(k, v) {
|
||
fold_left(tree2, tree1, fn(acc, key, value) {
|
||
insert(acc, key, value, compare)
|
||
})
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## Тесты и метрики
|
||
|
||
### Unit тесты
|
||
- `empty_tree_test()` - создание пустого дерева и проверка `is_empty()`, `size()`
|
||
- `single_insert_test()` - вставка одного элемента, проверка `lookup()` и размера
|
||
- `multiple_insert_test()` - множественные вставки с проверкой всех элементов
|
||
- `delete_test()` - удаление элементов с проверкой корректности
|
||
- `update_existing_key_test()` - обновление существующих ключей
|
||
- `filter_test()` - фильтрация четных чисел, проверка размера и содержимого
|
||
- `map_test()` - отображение значений (умножение на 2), проверка корректности
|
||
- `fold_left_test()` - левая свёртка для суммирования значений
|
||
- `fold_right_test()` - правая свёртка для конкатенации строк
|
||
- `to_from_list_test()` - конвертация дерево→список→дерево с проверкой эквивалентности
|
||
- `red_black_invariant_test()` - работа с большим деревом (10 элементов), проверка балансировки
|
||
- `semantic_equal_test()` - семантическое равенство (независимо от структуры)
|
||
- `structure_equal_test()` - структурное равенство без учёта цветов узлов
|
||
|
||
### Property-based тесты
|
||
|
||
1. **Свойства основных операций:**
|
||
```gleam
|
||
pub fn insert_lookup_property_test() // insert -> lookup инвариант
|
||
pub fn insert_size_property_test() // размер увеличивается корректно
|
||
pub fn filter_property_test() // фильтр сохраняет структуру
|
||
pub fn map_property_test() // map сохраняет структуру
|
||
```
|
||
|
||
2. **Свойства свёрток:**
|
||
```gleam
|
||
pub fn fold_property_test() // корректность левой/правой свёртки
|
||
```
|
||
|
||
3. **Свойства преобразований:**
|
||
```gleam
|
||
pub fn list_roundtrip_property_test() // to_list -> from_list эквивалентность
|
||
```
|
||
|
||
### Тесты моноида
|
||
|
||
```gleam
|
||
// Левая единица: mempty ∘ a = a
|
||
pub fn monoid_left_identity_test()
|
||
|
||
// Правая единица: a ∘ mempty = a
|
||
pub fn monoid_right_identity_test()
|
||
|
||
// Ассоциативность: (a ∘ b) ∘ c = a ∘ (b ∘ c)
|
||
pub fn monoid_associativity_test()
|
||
|
||
// Коммутативность (для непересекающихся множеств ключей)
|
||
pub fn monoid_commutativity_test()
|
||
```
|
||
|
||
### Отчёт тестирования
|
||
|
||
```
|
||
> gleam test
|
||
Compiling lab2
|
||
Compiled in 0.46s
|
||
Running lab2_test.main
|
||
.......................
|
||
23 passed, no failures
|
||
```
|
||
|
||
### Метрики производительности
|
||
|
||
| Операция | Сложность|
|
||
|----------|------------------------|
|
||
| lookup | O(log n) |
|
||
| insert | O(log n) |
|
||
| delete | O(log n) |
|
||
| size | O(n) |
|
||
| map | O(n) |
|
||
| filter | O(n log n) |
|
||
| fold | O(n) |
|
||
|
||
---
|
||
|
||
## Выводы
|
||
Использование ленивых вычислений повышает эффективность использования памяти при операциях со структурами данных высокой вложенности (в нашем случае) ценой cpu на вычисление значения.
|
||
Также использовал типы, а ещё писал своё сравнение без высокоуровневых абстракций. |