Изменения с прошлой демонстрации:

https://github.com/jefremof/FP-lab-2/blob/main/test/pbtests.ml

• Рефакторинг кода property-based тестов
• Добавлен pb-test операции map из одного типа в другой
• В тестах со сравнением Bag - использован bag compare, а не приведение к спискам

---

FP-lab-1

Функциональное программирование
Отчет по лабораторной работе №1

Выполнил:
Ефремов Марк Андреевич

Группа:
P3334

Преподаватель:
Пенской Александр Владимирович

Требования:

Реализовать PrefixTree с интерфейсом Bag (Multiset). Реализованная структура данных должна быть полиморфной, для неё должны быть реализованы следующие операции:

• Добавление элементов
• Удаление элементов
• Свёртка, правая и левая
• Фильтрация
• Отображение (полиморфное)
• Сравнения (только через интерфейс)

Структура должна быть иммутабельной.

Структура должна представлять собой моноид.

Помимо разработки структуры данных, необходимо также протестировать её с помощью unit и property-based тестирования.

Ключевые элементы реализации:

Префиксное дерево в данной реализации не выделяет минимальные префиксы, а сразу разбивает элемент на полную последовательность неделимых префиксов.

Дерево требует выделения префиксов, поэтому PrefixTree является функтором, который строит модуль дерева для конкретного типа данных, если передать ему модуль типа Prefixes.S0.

Модуль Prefixes.S0 содержит тип элемента (используется в интерфейсе Bag), а также тип его префиксов. От пользователя требуется определить операции дробления элемента на префиксы и их слияние обратно.

Из-за строгости системы типов Ocaml, реализация операции отображения в Bag с другим типом элементов, возможна только с помощью выделения её в отдельный модуль.

Сравнение Bag также выделено в отдельный модуль, чтобы гарантировать, что он использует только операции из интерфейса.

Операция отображения меняет структуру дерева, что вызывает сложности, поскольку необходимо сохранять правильный порядок префиксов. Поэтому было решено реализовать её через свёртку дерева в само себя с помощью операции добавления элементов.

Тесты:

В рамках property-based тестирования были проверены следующие свойства:

1. Преобразование списка в Bag не должно изменять набор элементов
2. Добавление n вхождений элемента в Bag должно приводить к тому, что количество вхождений увеличивается на n
3. Удаление n вхождений элемента из Bag должно приводить к тому, что количество вхождений уменьшается на n, но не меньше 0.
4. Сравнение должно быть коммутативным
5. -7. Свойства моноида

Тестирование позволило выявить ошибки:

1. Переполнения
2. Появление элементов с отрицательной "частотой"

Выводы:

Ocaml обладает строгой системой типов, которая поддерживает только очень ограниченный полиморфизм (I уровня ?). При работе с ним следует руководствоваться прагматичностью, упрощать структуру программы.