Бакалавриат
2024/2025![Цель освоения дисциплины](/f/src/global/i/edu/objectives.svg)
![Планируемые результаты обучения](/f/src/global/i/edu/results.svg)
![Содержание учебной дисциплины](/f/src/global/i/edu/sections.svg)
![Элементы контроля](/f/src/global/i/edu/controls.svg)
![Промежуточная аттестация](/f/src/global/i/edu/intermediate_certification.svg)
![Список литературы](/f/src/global/i/edu/library.svg)
Функциональное программирование
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Дашков Евгений Владимирович
Язык:
русский
Кредиты:
5
Контактные часы:
56
Программа дисциплины
Аннотация
Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП в целом и популярного языка 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 * Экз)).
Список литературы
Рекомендуемая основная литература
- Hutton, G. (2007). Programming in Haskell. Cambridge, UK: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=206716
- Lipovača, M. (2011). Learn You a Haskell for Great Good! : A Beginner’s Guide. San Francisco, Calif: No Starch Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=440054
Рекомендуемая дополнительная литература
- Okasaki, C. (1998). Purely Functional Data Structures. Cambridge, U.K.: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=502386