14 занимательных эссе о языке Haskell и функциональном программировании (1500,00 руб.)

Стр.3

Стр.5

Стр.6

Стр.7

Стр.8

УДК 004.4 ББК 32.973.26-018.2 Д86 Д86 Душкин, Роман Викторович. 14 занимательных эссе о языке Haskell и функциональном программировании / Р. В. Душкин. — 2-е изд., эл. — 1 файл pdf : 223 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный. ISBN 978-5-89818-621-0 В книге представлено 14 статей автора, которые в разное время были опубликованы или подготовлены к публикации в научно-популярном журнале для школьников и учителей «Потенциал». Статьи расположены и связаны таким образом, чтобы они представляли собой логически последовательное повествование от начал к более сложным темам. Также в книге сделан упор на практические знания, предлагается решение многих прикладных задач при помощи языка функционального программирования Haskell. Книга будет интересна всем, кто живо интересуется функциональным программированием, студентам технических вузов, преподавателям информатики. УДК 004.4 ББК 32.973.26-018.2 Электронное издание на основе печатного издания: 14 занимательных эссе о языке Haskell и функциональном программировании / Р.В. Душкин. — Москва : ДМК Пресс, 2016. — 222 с. — ISBN 978-5-97060-360-4. — Текст : непосредственный. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации. ISBN 978-5-89818-621-0 © Душкин Р. В., 2011 © Оформление ДМК Пресс, 2016

Стр.3

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

Стр.5

Оглавление 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

Стр.6

6 Оглавление Вспомогательные типы данных . . . . . . . . . . . . . . . . . . . . 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

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

Стр.8