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

14 занимательных эссе о языке Haskell и функциональном программировании к v . Ш\ . . ■ Душкин Р. В здатёдьст=• Душкин Р. В. 14 занимательных эссе о языке Haskell и функциональном программировании издат ьство Москва, 2011 УДК 004. 4 ББК 32. 973. 26-018. 2 Д86 Душкин Р. В. Д86 14 занимательных эссе о языке Haskell и функциональном программировании. - М. : ДМК Пресс, 2011. - 140 с, ил. ISBN 978-5-94074-691-1 В книге представлено 14 статей автора, которые в разное время были опубликованы или подготовлены к публикации в научно-популярном журнале для школьников и учителей «Потенциал». Статьи расположены и связаны таким образом, чтобы они представляли собой логически последовательное повествование от начал к более сложным темам. Также в книге сделан упор на практические знания, предлагается решение многих прикладных задач при помощи языка функционального программирования Haskell. Книга будет интересна всем, кто живо интересуется функциональным программированием, студентам технических ВУЗов, преподавателям информатики. УДК 004. 4 ББК 32. 973. 26-018. 2 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-5-94074-691-1 ©Душкин Р. В. , 2011 © Оформление ДМК Пресс, 2011 3 Принимаются благодарности Вниманию всех читателей! Данная книга издана в электронном виде и распространяется абсолютно бесплатно. Вы можете свободно использовать её для чтения, копировать её для друзей, размещать в библиотеках на сайтах в сети Интернет, рассылать по электронной почте и при помощи иных средств передачи информации. Вы можете использовать текст книги частично или полностью в своих работах при условии размещения ссылок на оригинал и должном цитировании. При этом автор будет несказанно рад получить читательскую благодарность, которая позволит как улучшить текст данной книги, так и более качественно подойти к подготовке следующих книг. Благодарности принимаются на счёт Ян деке. Деньги, на который можно перечислить малую лепту, и при помощи терминалов: 4100137733052 Убедительная просьба; при перечислении благодарности указывать в пояснении к переводу наименование книги или какое-либо иное указание на то, за что именно выражается благодарность. Оглавление От автора 7 Типовой процесс разработки программ на языке Haskell 8 Инструментальные средства 8 Описание процесса разработки 11 Функциональный подход в программировании 15 Введение 15 Общие свойства функций в функциональных языках программирования 16 Примеры определения функций 17 Заключение 21 Алгебраические типы данных в языке Haskell 22 Введение 22 Простые перечисления 23 Параметризация 25 Параметрический полиморфизм 27 Заключение 28 Объектно-ориентированное и функциональное программирование 30 Введение 30 Именованные поля и структуры 31 Классы типов 34 Экземпляры классов 35 Окончательные замечания 37 Заключение 39 Введение в Л-исчисление для начинающих 40 Введение 40 Неформальное описание теории 41 Некоторые дополнения 43 Редукция как стратегия вычислений 43 Примеры кодирования данных и функций 46 Заключение 51 Комбинаторы? — Это просто! 52 Введение 52 Формальная теория 52 Примеры сложных комбинаторов 55 Модуль на языке Haskell для преобразования комбинаторов 57 Оглавление 5 Представление данных и функций 59 Булевские значения 59 Нумералы Чёрча 60 Упорядоченные пары 60 Общие замечания 61 Заключение 61 Ввод и вывод на языке Haskell 63 Введение 63 Основы функционального ввода/вывода 64 Стандартные функции ввода/вывода 66 Примеры программ 69 Вывод результатов исполнения функции на экран 69 Альтернатива: экран или файл 70 Копирование файлов 71 Заключение 72 Простой интерпретатор команд 73 Введение 73 Постановка задачи 73 Основной набор функций 74 Вспомогательные типы данных 75 Цикл интерпретации 76 Функции для исполнения команд 78 Заключение 80 Теория чисел и язык Haskell 81 Введение 81 Простейшие задачи 82 Такие непростые простые числа 83 Числа Мерсенна 85 Числа Ферма 86 Числа Софи Жермен 86 Другие последовательности простых чисел 86 Совершенству нет предела 87 Заключение 89 Магические квадраты и решение переборных задач 90 Введение 90 Простейший вариант перебора 91 Перебор с использованием перестановок 94 Перебор с использованием размещений 96 Дальнейшая универсализация алгоритма 99 Заключение 102 Задача о ранце 103 Введение 103 Классическая задача 104 Реализация решения на языке Haskell 105 Заключение 108 6 Оглавление Кривая Дракона 109 Введение 109 Что такое Кривая Дракона? 111 Алгоритм построения 113 Реализация на языке Haskell 113 Подготовительные описания геометрических образов 114 Построение Кривой Дракона 116 Заключение 118 Немного о шахматных задачах 119 Введение 119 Вспомогательные программные сущности 119 Задача о расстановке фигур 122 Задача о ходе коня 123 Генерация рекурсивных сказок 126 Введение 126 Колобок 127 Теремок 131 Обобщение функций и построение генератора 133 Репка 136 Заключение 138 Литература 139 От автора В период с 2006 по 2009 год в образовательном журнале для старшеклассников и учителей «Потенциал» (ISSN 1814-6422) были опубликованы или подготовлены к публикации четырнадцать научно- популярных статей о функциональном программировании и языке Haskell.