Richard Bird, Thinking Functionally with Haskell, 2014

Ричард Бёрд безусловно велик. Это уже его третья книга по программированию на Haskell: ещё в 1988 он вместе с Филиппом Вадлером написал An Introduction To Functional Programming (Хаскеля тогда ещё не было, а книжка уже была!), спустя десять лет было второе издание, Introduction to Functional Programming using Haskell, уже без Вадлера. Книга 2014 года представляет собой тщательно пересмотренное и замещающее всё предыдущее издание. Она позиционируется как учебник для математически ориентированных (любителей “Mordor ot Mathematics”) студентов первого или второго курсов (что, сразу отмечу, в точности так и есть).

Во главу угла Бёрд при изучении функционального программирования ставит формальные рассуждения. Он обожает, пользуясь эквивалентными преобразованиями, выводить эффективные реализации из неэффективных. Этот подход достигает апогея в его Жемчужинах проектирования алгоритмов, поэтому для чтения “Жемчужин” эта книга Бёрда может считаться пререквизитом. Ясно, что при таком подходе ждать чего-то особенно практического от Бёрда не стоит, но, как говорится, любим мы его не за это!

Книга состоит из 12 глав, к каждой главе прилагаются упражнения, как простые, так и сложные, обычно около десятка, их решения, а также замечания об истории вопроса по темам глав. Главы такие:

• “Что такое функциональное программирование?” — здесь рассказывают о функциях и базовых типах, списках и кортежах, о композиции функций, о том, как это всё запускать (Haskell Platform), рассматриваются два больших примера (поиск наиболее часто встречающихся слов в тексте, построение словесного наименования заданного числа).
• “Выражения, типы и значения” — подробнее об интерпретаторе GHCi, порядок вычисления значений, типы и классы типов, модули.
• “Работа с числами” — среди прочего здесь разными способами вычисляется функция пола для вещественного числа — с применением функций высшего порядка, бинарного поиска и эквивалентных преобразований.
• “Списки”
• “Простой решатель Судоку” — сложная глава, эдакое введение в проектирование функциональных алгоритмов по заданной спецификации.
• “Доказательства” — введение в доказательство свойств функциональных программ: индукция на числах и списках, свойства свёрток (есть fusion!), задача на поиск сегмента списка с максимальной суммой.
• “Эффективность” — ленивые вычисления, слежение за использованием памяти и времени, использование аккумулирующих параметров, эффективные сортировки.
• “Красивая печать” (pretty-printing) — расширенный пример построения библиотеки (или EDSL) для печати выражений, классическая задача.
• “Бесконечные списки” — основные идеи (паттерны) использования бесконечных списков в языке с ленивыми вычислениями, с доказательствами свойств, реализуется игра “Камень–ножницы–бумага” (со случайностью и анализом возможных стратегий), идея потокового взаимодействия, двусвязные списки.
• “Императивное функциональное программирование” — монада IO и введение в монады вообще (честно говоря, не самое лучшее, что есть в книге), монады State и ST, изменяемые массивы.
• “Разбор” (parsing) — прекрасное изложение монадического разбора и комбинатор-парсеров, уже три года я читаю соответствующую лекцию очень близко к тексту этой главы.
• “Простой вычислитель эквивалентных преобразований” — реализация вычислителя эквивалентных преобразований выражений на функциональном языке на основе заданного набора правил преобразований, фактически это элементарный доказыватель теорем (ссылка на Coq инклюдед!).

Всё, что пишет Бёрд, прекрасно, но местами довольно сложно. Эту книгу действительно можно использовать для обучения студентов, но нужно понимать, что устроиться на работу с этими знаниями не получится, а вот заняться исследованиями, скажем, в области теории языков программирования — вполне, это неплохой старт. В любом случае всякий, преподающий Haskell, должен эту книгу прочитать, ну а любители делать HTTP-запросы и обращаться к базам данных могут идти лесом. Вы что, думали вас в университете будут готовить к работе в индустрии?