Функциональные языки программирования весна 2025

Общие сведения

Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП в целом и популярного языка Haskell в частности. Попутно сообщаются начальные сведения из области лямбда-исчислений, теории типов, теории категорий.

Команда курса

• Руководитель курса: Дашков Евгений

План курса

• 1. Вычисление как «редукция» (неформальное введение). Бестиповое лямбда-исчисление. Редукции, нормальные формы, теорема Чёрча-Россера.
• 2. Представление логических значений и натуральных чисел, пар, условного перехода. Итерация.
• 3. Неподвижная точка и различные виды рекурсии. Минимизация. Представление вычислимых функций. Неразрешимость бестипового лямбда-исчисления.

Более сложные типы данных.

• 4. Лямбда-исчисление с простыми типами. Вывод типов. Представление логических и арифметических функций. Понятие о более сильных исчислениях.
• 5. Программа на языке Haskell. Переменные и функции. Важнейшие типы данных. Каррирование, лямбды, let in, разбор случаев, гарды, рекурсия.
• 6. Полиморфизм. Классы. Типы с параметрами. Списки и работа с ними.
• 7. Функции высших порядков. Свертки.
• 8. Алгебраические типы данных. Определение типов и классов.
• 9. Отложенные и строгие вычисления. Параллелизм.
• 10. Ввод и вывод. Генераторы случайных чисел.
• 11. Программа в целом. Система модулей. Обработка аргументов командной строки. Библиотека QuickCheck.
• 12. Функторы, аппликативные функторы и монады. Понятие о категориях.
• 13. Моноиды. Классы Foldable и Traversable.
• 14. Монады Writer, Reader и State.
• 15. Эффективная реализация алгоритмов в ФП.
• 16. Преобразователи монад.
• 17. «Застежки» (zippers) и «оптика».

Полезные ссылки

• Код к лекциям: https://github.com/edashkov/hse-fp-22
• Видео прошлых лет: https://youtube.com/playlist?list=PL1Uob8iPTHGQcHjYxkXKfNihme3cjNiRg&si=Wg45z8MHTkcHcSbP

Критерии получения оценки

• Оценка выставляется по домашним заданиям и одной контрольной работе по формуле:

• ОКРУГЛ(0.65 * ДЗ + 0.35 * КР)

• Значения ДЗ и КР лежат от 0 до 10.

• ДОМАШНЕЕ ЗАДАНИЕ разбито на пять или шесть частей и выдается постепенно.