Набор задач по функциональному программированию: структуры данных, вычисление значений по точкам и описание поведения через состояния. Три примера можно посмотреть в браузере, без установки среды разработки.
В функциональном программировании программу строят из функций и преобразований данных. Эти работы показывают подход на небольших задачах, которые можно проверить:
- Дерево поиска хранит числа в порядке и перестраивается после вставки или удаления, сохраняя баланс. В демо видно, как меняются связи между узлами.
- Интерполяция Лагранжа строит полином по известным точкам. Можно сравнить его с исходной функцией и увидеть, почему больше точек не всегда означает меньшую ошибку.
- Конечный автомат описывает поведение как состояния и переходы. На примере светофора можно проследить, как нажатие кнопки меняет дальнейший цикл.
Предмет — функциональное программирование; язык — F#. Учебные темы: рекурсия, неизменяемые структуры данных, функции высшего порядка, сопоставление с образцом и проверка свойств программы.
Исходные работы расположены в FP.Task01–FP.Task04. Браузерная демонстрация «Алгоритмы в движении» добавлена в 2026 году и использует модули дерева, интерполяции и автомата из FP.Task02–FP.Task04, включая внесённые исправления. Это учебные реализации, а не библиотеки для промышленной эксплуатации.
Открыть демонстрацию → · Разбор реализации · Проверки
| Демонстрация | Что попробовать | Что показывает |
|---|---|---|
| Дерево поиска | «Двойной поворот», затем шаг назад и вперёд | Неизменяемые структуры, поддержание порядка и баланса |
| Интерполяция | Функция Рунге, 11 равноотстоящих узлов | Полином проходит через узлы, но ошибка между ними может расти |
| Конечный автомат | Нажатие кнопки на шаге 3 | Условия перехода, изменение состояния и реакция на событие |
Установка не нужна. При первом открытии загружается .NET WebAssembly. В браузере выполняются F# модули из этого репозитория, подключённые в проект через ссылки на исходные файлы. JavaScript рисует результат, но не подменяет алгоритмы.
- Неизменяемое дерево поиска с балансировкой после вставки и удаления.
- Интерполяцию Лагранжа с проверкой входных данных и численной визуализацией.
- Обобщённый конечный автомат и модель светофора.
- Исправления граничных случаев: удаление из дерева, повторяющиеся узлы интерполяции, нулевой шаг генератора, короткий ввод распознавателя, отсутствие терминального состояния.
- 23 автоматических тестовых случая в современной сборке: порядок и баланс после каждой операции, сравнение с
Set, свойства полинома и переходы автомата.
Исходные задания — учебные работы ИТМО. В исторических проектах остаются примеры и тесты Expecto/FsCheck. Современный каталог lab/ добавляет .NET 10, отдельные xUnit-проверки, браузерный интерфейс и GitHub Pages.
Демо непосредственно использует модули FP.Task02, FP.Task03 и FP.Task04, включая исправления 2026 года. Оно не запускает старые консольные проекты целиком. История авторства сохранена в Git.
Нужны .NET SDK 10 и PowerShell 7.
dotnet test lab/Tests/Tests.fsproj -c Release
./Build-Lab.ps1 -BasePath /Откройте artifacts/site через HTTP-сервер, например python -m http.server 8080 --directory artifacts/site. GitHub Actions выполняет тесты на Windows/Linux и публикует master на Pages.
| Файл | Что посмотреть |
|---|---|
| BinarySearchTree.fs | Рекурсивные операции, повороты и баланс |
| LagrangeInterpolator.fs | Интерполяция и проверка узлов |
| StateMachine.fs | Переходы и ограничение числа итераций |
| Api.fs | Снимки дерева, точки кривой и кадры автомата |
| Tests.fs | Регрессии и проверки свойств |