Курс знакомит слушателей с функциональными языками программирования и методами программирования на этих языках.

Мы рассмотрим отличия функционального подхода к программированию от традиционного императивного, познакомимся с лямбда-исчислением, как теоретической основой функционального программирования, изучим системы типов функциональных языков и алгоритм вывода типов Хиндли-Дамаса-Милнера.

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

Мы изучим основные классы типов из стандартной библиотеки Хаскелла, в том числе функторы, аппликативные функторы и монады. Мы обсудим различные стратегии свертки и обхода списков, деревьев и познакомимся с обобщением этих операций в классах типов Foldable и Traversable.

Мы научимся программировать, используя стандартные монады, в частности обсудим проблему ввода-вывода в чистых языках и его реализацию в Хаскелле с помощью монады IO, а также работу с изменяемым состоянием с помощью монады State и родственных ей монад.

Литература

Основная:

• Miran Lipovaca, Learn You a Haskell for Great Good! A Beginner’s Guide 2011 http://learnyouahaskell.com/chapters (русский перевод: Миран Липовача, Изучай Haskell во имя добра! Издательство: ДМК Пресс, 2012)

Дополнительная:

• Х. Барендрегт, Ламбда-исчисление, его синтаксис и семантика, М.:Мир, 1985

• Филд А., Харрисон П., Функциональное программирование, М.:Мир, 1993

• John Harrison, Introduction to Functional Programming http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jrh-1996/ (русский перевод: http://code.google.com/p/funprog-ru/)

• Bryan O’Sullivan, Don Stewart, and John Goerzen, Real World Haskell O’Reilly Media, 2008 http://book.realworldhaskell.org/read/

• Simon Peyton Jones, The Implementation of Functional Programming Languages, Prentice Hall, 1987 http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm

• Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002 http://www.cis.upenn.edu/ bcpierce/tapl (русский перевод: Бенджамин Пирс, Типы в языках программирования, Издательство: Лямбда пресс, Добросвет, 2012 http://newstar.rinet.ru/ goga/tapl/)

• Henk Barendregt, Lambda calculi with types, Handbook of logic in computer science (vol. 2), Oxford University Press, 1993