Функциональное программирование

Бакалавриат 2024/2025

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 3-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Дашков Евгений Владимирович, Соколов Павел Павлович

Язык: русский

Кредиты: 5

Полная версия программы учебной дисциплины

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

Владеть общей информацией об императивном и функциональном стилях программирования, их сильных и слабых сторонах, уметь выбирать правильный стиль в зависимости от задачи.
Знать теоретические основы функционального программирования (лямбда-исчисление, начала теории категорий и проч.).
Понимать код программ на языке Haskell.
Уметь решать задачи средней сложности в программировании на языке Haskell, в т.ч. применяя стандартные монады.
Уметь разрабатывать библиотеки и приложения CLI на языке Haskell.
Уметь оценивать эффективность алгоритмов, реализованных в функциональном стиле.

Содержание учебной дисциплины

Вычисление как «редукция» (неформальное введение). Бестиповое лямбда-исчисление. Редукции, нормальные формы, теорема Чёрча-Россера.
Представление логических значений и натуральных чисел, пар, условного перехода. Итерация.
Неподвижная точка и различные виды рекурсии. Минимизация. Представление вычислимых функций. Неразрешимость бестипового лямбда-исчисления. Более сложные типы данных.
Лямбда-исчисление с простыми типами. Вывод типов. Представление логических и арифметических функций. Понятие о более сильных исчислениях.
Программа на языке Haskell. Переменные и функции. Важнейшие типы данных. Каррирование, лямбды, let in, разбор случаев, гарды, рекурсия.
Полиморфизм. Классы. Типы с параметрами. Списки и работа с ними.
Функции высших порядков. Свертки.
Алгебраические типы данных. Определение типов и классов.
Отложенные и строгие вычисления. Параллелизм.
Ввод и вывод. Генераторы случайных чисел.
Программа в целом. Система модулей. Обработка аргументов командной строки. Библиотека QuickCheck.
Функторы, аппликативные функторы и монады. Понятие о категориях.
Моноиды. Классы Foldable и Traversable.
Монады Writer, Reader и State.
Эффективная реализация алгоритмов в ФП.
Преобразователи монад.
«Застежки» (zippers) и «оптика».

Элементы контроля

Домашнее задание
Домашнее задание выдается частями приблизительно раз в две недели; при выдаче каждой части указывается срок ее сдачи. Все задания письменные.
Контрольная работа
Письменная Контрольная работа проводится в начале второго модуля. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем.
Самостоятельная работа (мини-проект)
При желании студенты согласовывают с семинаристом задачу для индивидуальной самостоятельной работы. При этом предполагаются решение достаточно сложной задачи по программированию и самостоятельное получение студентом недостающих сведений. Самостоятельная работа должна быть сдана до 15-го декабря.
Экзамен
Письменный экзамен проводится в конце курса. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем.

Промежуточная аттестация

2024/2025 2nd module
Итог = ОКРУГЛ (min(10, 0.15 * Сам + 0.23 * КР + 0.27 * ДЗ + 0.5 * Экз)).

Список литературы

Авторы

Сысоева Алевтина Александровна

Программа дисциплины