14 занимательных эссе о языке Haskell и функциональном программировании

Душкин Р. В.
14 занимательных эссе
о языке Haskell
и функциональном
программировании
Москва, 2016

ББК
32.973.26-018.2
Д86
Душкин Р. В.
 
14 занимательных эссе о  языке Haskell и функциональном программировании. – М.: ДМК
Пресс, 2011. – 222 с., ил.
ISBN 978-5-97060-360-4
В книге представлено 14 статей автора, которые в разное время были опубликованы или подготовлены к публикации в научно-популярном журнале для школьников и учителей «Потенциал». Статьи расположены и связаны таким образом, чтобы они представляли собой логически
последовательное повествование от начал к более сложным темам. Также в книге сделан упор на
практические знания, предлагается решение многих прикладных задач при помощи языка функционального программирования Haskell.
Книга будет интересна всем, кто живо интересуется функциональным программированием,
студентам технических ВУЗов, преподавателям информатики.
УДК 004.4
ББК 32.973.26-018.2
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими
бы то ни было средствами без письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все
равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В
связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.
© Душкин Р. В., 2011
   ISBN 978-5-97060-360-4
© Оформление ДМК Пресс, 2016

Принимаются благодарности
Вниманию всех читателей! Данная книга издана в электронном виде
и распространяется абсолютно бесплатно. Вы можете свободно использовать
е¼ для чтения, копировать е¼ для друзей, размещать в библиотеках на сайтах
в сети Интернет, рассылать по электронной почте и при помощи иных средств
передачи информации. Вы можете использовать текст книги частично или
полностью в своих работах при условии размещения ссылок на оригинал
и должном цитировании.
При
этом
автор
будет
несказанно
рад
получить
читательскую
благодарность, которая позволит как улучшить текст данной книги, так
и более качественно подойти к подготовке следующих книг. Благодарности
принимаются на сч¼т Яндекс.Деньги, на который можно перечислить малую
лепту, и при помощи терминалов:
4100137733052
Убедительная
просьба;
при
перечислении
благодарности
указывать
в пояснении к переводу наименование книги или какое-либо иное указание
на то, за что именно выражается благодарность.

Оглавление
От автора
8
Типовой процесс разработки программ на языке Haskell
10
Инструментальные средства . . . . . . . . . . . . . . . . . . . . . . . . .
11
Описание процесса разработки
. . . . . . . . . . . . . . . . . . . . . . .
14
Функциональный подход в программировании
20
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Общие
свойства
функций
в
функциональных
языках
программирования
. . . . . . . . . . . . . . . . . . . . . . . . . . .
22
Примеры определения функций . . . . . . . . . . . . . . . . . . . . . . .
25
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Алгебраические типы данных в языке Haskell
32
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
Простые перечисления . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Параметризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
Параметрический полиморфизм . . . . . . . . . . . . . . . . . . . . . . .
40
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Объектно-ориентированное
и
функциональное
программирование
44
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Именованные поля и структуры . . . . . . . . . . . . . . . . . . . . . . .
46
Классы типов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
Экземпляры классов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53

Оглавление
5
Окончательные замечания . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
Введение в λ-исчисление для начинающих
60
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
Неформальное описание теории . . . . . . . . . . . . . . . . . . . . . . .
62
Некоторые дополнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
Редукция как стратегия вычислений . . . . . . . . . . . . . . . . . . . .
66
Примеры кодирования данных и функций . . . . . . . . . . . . . . . . .
70
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
Комбинаторы?  Это просто!
80
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
Формальная теория . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
Примеры сложных комбинаторов . . . . . . . . . . . . . . . . . . . . . .
84
Модуль на языке Haskell для преобразования комбинаторов . . . . . .
88
Представление данных и функций . . . . . . . . . . . . . . . . . . . . .
91
Булевские значения . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
Нумералы Ч¼рча
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
Упорядоченные пары . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Общие замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
Ввод и вывод на языке Haskell
97
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
Основы функционального ввода/вывода . . . . . . . . . . . . . . . . . . 100
Стандартные функции ввода/вывода . . . . . . . . . . . . . . . . . . . . 103
Примеры программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Вывод результатов исполнения функции на экран . . . . . . . . . 108
Альтернатива: экран или файл . . . . . . . . . . . . . . . . . . . . 109
Копирование файлов . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Простой интерпретатор команд
114
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Постановка задачи
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Основной набор функций
. . . . . . . . . . . . . . . . . . . . . . . . . . 117

Оглавление
Вспомогательные типы данных . . . . . . . . . . . . . . . . . . . . 117
Цикл интерпретации
. . . . . . . . . . . . . . . . . . . . . . . . . . 119
Функции для исполнения команд . . . . . . . . . . . . . . . . . . . . . . 122
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Теория чисел и язык Haskell
128
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Простейшие задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Такие непростые простые числа . . . . . . . . . . . . . . . . . . . . . . . 132
Числа Мерсенна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Числа Ферма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Числа Софи Жермен . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Другие последовательности простых чисел . . . . . . . . . . . . . 137
Совершенству нет предела . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Магические квадраты и решение переборных задач
142
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Простейший вариант перебора
. . . . . . . . . . . . . . . . . . . . . . . 144
Перебор с использованием перестановок . . . . . . . . . . . . . . . . . . 148
Перебор с использованием размещений
. . . . . . . . . . . . . . . . . . 152
Дальнейшая универсализация алгоритма . . . . . . . . . . . . . . . . . 157
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Задача о ранце
162
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Классическая задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Реализация решения на языке Haskell . . . . . . . . . . . . . . . . . . . 166
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Кривая Дракона
172
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Что такое Кривая Дракона? . . . . . . . . . . . . . . . . . . . . . . . . . 176
Алгоритм построения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Реализация на языке Haskell . . . . . . . . . . . . . . . . . . . . . . . . . 180
Подготовительные описания геометрических образов
. . . . . . . 180
Построение Кривой Дракона . . . . . . . . . . . . . . . . . . . . . . 184

Оглавление
7
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Немного о шахматных задачах
188
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Вспомогательные программные сущности . . . . . . . . . . . . . . . . . 189
Задача о расстановке фигур . . . . . . . . . . . . . . . . . . . . . . . . . 193
Задача о ходе коня
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Генерация рекурсивных сказок
199
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Колобок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Теремок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
Обобщение функций и построение генератора
. . . . . . . . . . . . . . 211
Репка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Литература
220

От автора
В
период
с
2006
по
2009
год
в
образовательном
журнале
для старшеклассников и учителей ¾Потенциал¿ (ISSN 1814-6422) были
опубликованы
или
подготовлены
к
публикации
четырнадцать
научнопопулярных статей о функциональном программировании и языке Haskell.
Многие из данных статей нашли определ¼нный отклик в сердцах и умах
читателей, поэтому автором было решено свести их в одну книгу, выстроив
в более или менее стройную систему повествования.
Вместе
с
тем
со
времени
начала
публикации
научно-популярных
статей прошло достаточное количество времени, чтобы и язык Haskell,
и функциональное программирование в целом эволюционировали, поэтому
необходима и актуализация информации, приведение е¼ в более современный
вид. Вс¼ это значит, что в настоящей книге исходные статьи не только
не приведены в исходном порядке публикации, но и в некоторых случаях
достаточно серь¼зно переработаны.
Книга будет полезна школьникам старших классов, живо интересующимся
информатикой и смежными областями науки и техники, а также учителям,
которые проводят факультативные занятия по информатике и компьютерной
грамотности. Кроме того, я надеюсь, что книга также будет полезна
студентам технических высших учебных заведений, которые хотели бы
овладеть пониманием функционального программирования в целом и языка
Haskell в частности. Ну и в любом случае книга станет неплохим источником
идей, задач и их решений для всех, кто интересуется функциональным
программированием.
Я выражаю самую серь¼зную благодарность всем моим коллегам, которые
в той или иной мере способствовали появлению многих из привед¼нных в книге
статей на свет. Особо стоит отметить Антонюка Д. А. и Астапова Д. Е. (в том

числе и в качестве рецензента), чьи бессменные советы и предложения
по
улучшению
всегда
приходились
кстати.
Также
хочу
выразить
благодарность всему коллективу редакции журнала ¾Потенциал¿ за его
самоотверженный труд на поприще просвещения и популяризации науки среди
подрастающего поколения. Отдельно хотелось бы отметить Ворожцова А. В.,
редактора отдела ¾Информатика¿.
Буду
крайне
признателен
любым
конструктивным
комментариям,
замечаниям
и
предложениям,
которые
можно
присылать
по
адресу
электронной почты roman.dushkin@gmail.com. Также по этому адресу можно
присылать запросы на файлы с исходными кодами примеров, привед¼нных
в книге (указывайте, пожалуйста, наименования эссе, для которых необходимо
выслать исходные коды примеров).
В добрый путь.
Душкин Р. В.
Москва, 2011.

Типовой процесс разработки
программ на языке Haskell
Статья
была
подготовлена
к
публикации
в
один
из
номеров
журнала
¾Потенциал¿ в конце 2009 года. Опубликована не была.
В
эссе
рассказывается
о
типовом
процессе
разработки
программных
средств на функциональном языке программирования Haskell. Описываются
некоторые
из
имеющихся
на
текущий
момент
программных
средств
и
инструментов,
делающих
процесс
разработки
простым
и
быстрым.
Да¼тся краткая суммарная информация о том, где и на каких условиях
можно получить весь необходимый для работы инструментарий.
В дальнейшем изложении в настоящей книге приводятся разнообразнейшие
задачи из области математики и информатики,
а также описываются
решения этих задач при помощи языка функционального программирования
Haskell. Опыт общения автора с читателями показал, что имеется проблема
непосредственно практического характера  многие читатели просто не знают,
что
делать
с
приводимыми
примерами
и
исходными
кодами:
какой
инструментарий использовать, как компилировать программы, как загружать
дополнительные пакеты и т. д.
Осмысление проблемы привело к пониманию того, что язык Haskell
при всех его достоинствах очень сложно входит в русло практического
использования как любителями, так и профессиональными программистами.
В
связи
с
этим
возникает
необходимость
в
использовании
новой
парадигмы
популяризации
языка
Haskell
и
функционального
подхода
в программировании (впервые введена в книге [8]).