УДК 004.4 ББК 32.973.26-018.2 Д86 Душкин Р. В. Д86 14 занимательных эссе о языке Haskell и функциональном программирова- нии. — Изд. 2-ое, исп., 2011. — 284 с., ил. В книге представлено 14 статей автора, которые в разное время были опубликованы или подготовлены к публикации в научно-популярном жур- нале для школьников и учителей «Потенциал». Статьи расположены и связаны таким образом, чтобы они представляли собой логически после- довательное повествование от начал к более сложным темам. Также в книге сделан упор на практические знания, предлагается решение многих прикладных задач при помощи языка функционального программирования Haskell. Книга будет интересна всем, кто живо интересуется функциональным программированием, студентам технических ВУЗов, преподавателям ин- форматики. УДК 004.4 ББК 32.973.26-018.2 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владель- цев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероят- ность технических ошибок всё равно существует, издательство не может гарантировать абсо- лютную точность и правильность приводимых сведений. В связи с этим издательство не несёт ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-5-94074-691-1 © Душкин Р. В., 2011 © Иллюстрации: журнал «Потенциал» © Оформление: ДМК Пресс, 2011 14 занимательных эссе о языке Haskell и функциональном про- граммировании ДУШКИН Роман Викторович [email protected] Москва, 2011 Принимаются благодарности Вниманию всех читателей! Данная книга издана в электронном виде и распространяется абсолютно бесплатно. Вы можете свободно использовать её для чтения, копировать её для друзей, размещать в библиотеках на сайтах в сети Интернет, рассылать по электронной почте и при помощи иных средств передачи информации. Вы може- те использовать текст книги частично или полностью в своих рабо- тах при условии размещения ссылок на оригинал и должном цитиро- вании. При этом автор будет несказанно рад получить читательскую бла- годарность, которая позволит как улучшить текст данной книги, так и более качественно подойти к подготовке следующих книг. Благо- дарности принимаются на счета наиболее распространённых элек- тронных платёжных систем:  Яндекс.Деньги: 4100137733052  WebMoney: R211895623295 Также на счета в этих платёжных системах малую лепту можно перечислить при помощи терминалов мгновенной оплаты. Убедительная просьба. По возможности, при перечислении бла- годарности указывать в пояснении к переводу наименование книги или какое-либо иное указание на то, за что именно выражается бла- годарность. Также лиц, заинтересованных в сотрудничестве по вопросам из- дания, распространения, написания новых книг и т. д., прошу обра- щаться по адресу электронной почты [email protected]. Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании 3 Содержание ОТ АВТОРА................................................................................................................................ 7 ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ ............................................................................ 8 ЭССЕ 1. ТИПОВОЙ ПРОЦЕСС РАЗРАБОТКИ НА ЯЗЫКЕ HASKELL ..... 12 ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА .................................................................................... 14 ОПИСАНИЕ ПРОЦЕССА РАЗРАБОТКИ ............................................................................... 16 ЭССЕ 2. ФУНКЦИОНАЛЬНЫЙ ПОДХОД В ПРОГРАММИРОВАНИИ ... 23 ВВЕДЕНИЕ ............................................................................................................................. 24 ОБЩИЕ СВОЙСТВА ФУНКЦИЙ В ФУНКЦИОНАЛЬНЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ ........................................................................................................ 26 ПРИМЕРЫ ОПРЕДЕЛЕНИЯ ФУНКЦИЙ .............................................................................. 29 ЗАКЛЮЧЕНИЕ ....................................................................................................................... 37 ЭССЕ 3. АЛГЕБРАИЧЕСКИЕ ТИПЫ ДАННЫХ В ЯЗЫКЕ HASKELL ...... 38 ВВЕДЕНИЕ ............................................................................................................................. 38 ПРОСТЫЕ ПЕРЕЧИСЛЕНИЯ ................................................................................................. 40 ПАРАМЕТРИЗАЦИЯ .............................................................................................................. 46 ПАРАМЕТРИЧЕСКИЙ ПОЛИМОРФИЗМ ............................................................................. 49 ЗАКЛЮЧЕНИЕ ....................................................................................................................... 53 ЭССЕ 4. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ ...................................................................................... 55 ВВЕДЕНИЕ ............................................................................................................................. 56 4 Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании ИМЕНОВАННЫЕ ПОЛЯ И СТРУКТУРЫ .............................................................................. 58 КЛАССЫ ТИПОВ .................................................................................................................... 63 ЭКЗЕМПЛЯРЫ КЛАССОВ ..................................................................................................... 67 ОКОНЧАТЕЛЬНЫЕ ЗАМЕЧАНИЯ ........................................................................................ 71 ЗАКЛЮЧЕНИЕ ....................................................................................................................... 74 ЭССЕ 5. ВВЕДЕНИЕ В Λ-ИСЧИСЛЕНИЕ ДЛЯ НАЧИНАЮЩИХ .............. 76 ВВЕДЕНИЕ ............................................................................................................................. 77 НЕФОРМАЛЬНОЕ ОПИСАНИЕ ТЕОРИИ ............................................................................. 78 НЕКОТОРЫЕ ДОПОЛНЕНИЯ ............................................................................................... 81 РЕДУКЦИЯ КАК СТРАТЕГИЯ ВЫЧИСЛЕНИЙ ................................................................... 83 ПРИМЕРЫ КОДИРОВАНИЯ ДАННЫХ И ФУНКЦИЙ ......................................................... 88 ЗАКЛЮЧЕНИЕ ....................................................................................................................... 97 ЭССЕ 6. КОМБИНАТОРЫ? — ЭТО ПРОСТО! ................................................ 99 ВВЕДЕНИЕ ............................................................................................................................. 99 ФОРМАЛЬНАЯ ТЕОРИЯ ..................................................................................................... 100 ПРИМЕРЫ СЛОЖНЫХ КОМБИНАТОРОВ ........................................................................ 105 МОДУЛЬ НА ЯЗЫКЕ HASKELL ДЛЯ ПРЕОБРАЗОВАНИЯ КОМБИНАТОРОВ .............. 109 ПРЕДСТАВЛЕНИЕ ДАННЫХ И ФУНКЦИЙ ....................................................................... 112 Булевские значения ........................................................................................................ 113 Нумералы Чёрча ............................................................................................................... 114 Упорядоченные пары ..................................................................................................... 116 Общие замечания ............................................................................................................. 117 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 117 ЭССЕ 7. ВВОД И ВЫВОД НА ЯЗЫКЕ HASKELL .......................................... 120 ВВЕДЕНИЕ ........................................................................................................................... 120 ОСНОВЫ ФУНКЦИОНАЛЬНОГО ВВОДА/ВЫВОДА ........................................................ 123 СТАНДАРТНЫЕ ФУНКЦИИ ВВОДА/ВЫВОДА ................................................................ 128 ПРИМЕРЫ ПРОГРАММ ....................................................................................................... 133 Вывод результатов исполнения функции на экран .................................. 134 Альтернатива: экран или файл ............................................................................ 136 Копирование файлов ..................................................................................................... 139 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 141 ЭССЕ 8. ПРОСТОЙ ИНТЕРПРЕТАТОР КОМАНД ....................................... 142 Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании 5 ВВЕДЕНИЕ ........................................................................................................................... 142 ПОСТАНОВКА ЗАДАЧИ ...................................................................................................... 143 ОСНОВНОЙ НАБОР ФУНКЦИЙ.......................................................................................... 146 Вспомогательные типы данных ........................................................................... 147 Цикл интерпретации ................................................................................................... 149 ФУНКЦИИ ДЛЯ ИСПОЛНЕНИЯ КОМАНД ........................................................................ 153 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 158 ЭССЕ 9. ТЕОРИЯ ЧИСЕЛ И ЯЗЫК HASKELL ............................................... 159 ВВЕДЕНИЕ ........................................................................................................................... 159 ПРОСТЕЙШИЕ ЗАДАЧИ ...................................................................................................... 161 ТАКИЕ НЕПРОСТЫЕ ПРОСТЫЕ ЧИСЛА ........................................................................... 165 Числа Мерсенна ................................................................................................................ 168 Числа Ферма ....................................................................................................................... 170 Числа Софи Жермен ....................................................................................................... 171 Другие последовательности простых чисел ................................................ 172 СОВЕРШЕНСТВУ НЕТ ПРЕДЕЛА ....................................................................................... 173 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 176 ЭССЕ 10. МАГИЧЕСКИЕ КВАДРАТЫ И РЕШЕНИЕ ПЕРЕБОРНЫХ ЗАДАЧ ...................................................................................................................... 178 ВВЕДЕНИЕ ........................................................................................................................... 179 ПРОСТЕЙШИЙ ВАРИАНТ ПЕРЕБОРА ............................................................................... 181 ПЕРЕБОР С ИСПОЛЬЗОВАНИЕМ ПЕРЕСТАНОВОК ........................................................ 186 ПЕРЕБОР С ИСПОЛЬЗОВАНИЕМ РАЗМЕЩЕНИЙ ........................................................... 190 ДАЛЬНЕЙШАЯ УНИВЕРСАЛИЗАЦИЯ АЛГОРИТМА ....................................................... 197 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 201 ЭССЕ 11. ЗАДАЧА О РАНЦЕ .............................................................................. 203 ВВЕДЕНИЕ ........................................................................................................................... 203 КЛАССИЧЕСКАЯ ЗАДАЧА .................................................................................................. 205 РЕАЛИЗАЦИЯ РЕШЕНИЯ НА ЯЗЫКЕ HASKELL ............................................................. 209 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 215 ЭССЕ 12. КРИВАЯ ДРАКОНА ........................................................................... 217 ВВЕДЕНИЕ ........................................................................................................................... 217 ЧТО ТАКОЕ КРИВАЯ ДРАКОНА? ..................................................................................... 221 6 Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании АЛГОРИТМ ПОСТРОЕНИЯ ................................................................................................. 225 РЕАЛИЗАЦИЯ НА ЯЗЫКЕ HASKELL ................................................................................. 226 Подготовительные описания геометрических образов ........................ 226 Построение Кривой Дракона ................................................................................... 231 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 234 ЭССЕ 13. НЕМНОГО О ШАХМАТНЫХ ЗАДАЧАХ ...................................... 236 ВВЕДЕНИЕ ........................................................................................................................... 236 ВСПОМОГАТЕЛЬНЫЕ ПРОГРАММНЫЕ СУЩНОСТИ ..................................................... 237 ЗАДАЧА О РАССТАНОВКЕ ФИГУР .................................................................................... 243 ЗАДАЧА О ХОДЕ КОНЯ ....................................................................................................... 245 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 247 ЭССЕ 14. ГЕНЕРАЦИЯ РЕКУРСИВНЫХ СКАЗОК ...................................... 248 ВВЕДЕНИЕ ........................................................................................................................... 248 КОЛОБОК ............................................................................................................................. 250 ТЕРЕМОК .............................................................................................................................. 258 ОБОБЩЕНИЕ ФУНКЦИЙ И ПОСТРОЕНИЕ ГЕНЕРАТОРА .............................................. 264 РЕПКА ................................................................................................................................... 270 ЗАКЛЮЧЕНИЕ ..................................................................................................................... 274 ЛИТЕРАТУРА ........................................................................................................ 276 Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании 7 От автора В период с 2006 по 2009 год в образовательном журнале для старшеклассников и учителей «Потенциал» (ISSN 1814-6422) были опубликованы или подготовлены к публикации четырнадцать научно-популярных статей о функциональном программировании и языке Haskell. Многие из данных статей нашли определённый от- клик в сердцах и умах читателей, поэтому автором было решено све- сти их в одну книгу, выстроив в более или менее стройную систему повествования. Вместе с тем со времени начала публикации научно-популярных статей прошло достаточное количество времени, чтобы и язык Haskell, и функциональное программирование в целом эволюциони- ровали, поэтому необходима и актуализация информации, приведе- ние её в более современный вид. Всё это значит, что в настоящей книге исходные статьи не только не приведены в исходном порядке публикации, но и в некоторых случаях достаточно серьёзно перера- ботаны.