Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Функциональное программирование на языке Haskell

Покупка
Артикул: 616233.03.99
Доступ онлайн
479 ₽
В корзину
Данная книга является первым в России изданием, рассматривающая функциональное программирование в полном объеме, достаточном для понимания новичку и для использования книги в качестве справочного пособия теми, кто уже использует парадигму функционального программирования в своей практике. Изучение прикладных основ показано на примере языка Haskell, на сегодняшний день являющегося самым мощным и развитым инструментом функционального программирования. Издание можно использовать и в качестве учебника по функциональному программированию, и в качестве самостоятельного учебного пособия по смежным дисциплинам, в первую очередь по комбинаторной логике и λ-исчислению. Также книга будет интересна тем, кто всерьез занимается изучением новых компьютерных технологий, искусственного интеллекта и экспертных систем. На сайте издательства дмк.рф размещены материалы с транслятором Haskell, а также различными библиотеками к нему, дополнительными утилитами и рабочими примерами программ, рассмотренных в книге.
Душкин, Р. В. Функциональное программирование на языке Haskell : практическое руководство / Р. В. Душкин. - 2-е изд. - Москва : ДМК Пресс, 2023. - 609 с. - ISBN 978-5-89818-623-4. - Текст : электронный. - URL: https://znanium.com/catalog/product/2108510 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Функциональное
программирование
на языке Haskell
Душкин Р. В.
Москва, 2023
2-е издание, электронное


Оглавление
19
1
Основы функционального программирования
27
1.1
История функционального программирования . . . . . . . . . . . .
28
1.2
Основные свойства функциональных языков . . . . . . . . . . . . .
44
1.3
Типовые
задачи,
решаемые
методами
функционального
программирования
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
1.4
Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . .
69
1.5
Доказательство свойств функций . . . . . . . . . . . . . . . . . . . .
86
2
Базовые принципы языка Haskell
99
2.1
Списки — основа функциональных языков
. . . . . . . . . . . . . . 100
2.2
Функции как описания процессов вычисления
. . . . . . . . . . . . 118
2.3
Типизация данных и функций . . . . . . . . . . . . . . . . . . . . . . 131
2.4
Элементы программирования . . . . . . . . . . . . . . . . . . . . . . 142
2.5
Модули и абстрактные типы данных . . . . . . . . . . . . . . . . . . 153
3
Классы и их экземпляры
164
3.1
Параметрический полиморфизм данных . . . . . . . . . . . . . . . . 165
3.2
Классы в языке Haskell как способ абстракции действительности . 170
3.3
Наследование и реализация . . . . . . . . . . . . . . . . . . . . . . . 180
3.4
Стандартные классы языка Haskell . . . . . . . . . . . . . . . . . . . 192
3.5
Сравнение с другими языками программирования . . . . . . . . . . 207


Оглавление
Монады
—
последовательное
выполнение
действий
в функциональной парадигме
213
4.1
Монада как тип-контейнер . . . . . . . . . . . . . . . . . . . . . . . . 214
4.2
Последовательное выполнение действий . . . . . . . . . . . . . . . . 222
4.3
Операции ввода/вывода в языке Haskell . . . . . . . . . . . . . . . . 239
4.4
Стандартные монады языка Haskell
. . . . . . . . . . . . . . . . . . 252
4.5
Разработка собственных монад . . . . . . . . . . . . . . . . . . . . . 262
5
Комбинаторная логика и λ-исчисление
273
5.1
Основы комбинаторной логики
. . . . . . . . . . . . . . . . . . . . . 274
5.2
Абстракция функций как вычислительных процессов . . . . . . . . 288
5.3
λ-исчисление
как
теоретическая
основа
функционального
программирования
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
5.4
Кодирование данных в λ-исчислении . . . . . . . . . . . . . . . . . . 307
5.5
Редукция и вычисления в функциональных языках . . . . . . . . . 315
6
Трансляторы программ
331
6.1
Математическая лингвистика . . . . . . . . . . . . . . . . . . . . . . 331
6.2
Краткое введение в теорию построения трансляторов . . . . . . . . 346
6.3
Реализация трансляторов на языке Haskell
. . . . . . . . . . . . . . 360
6.4
Библиотеки для создания трансляторов . . . . . . . . . . . . . . . . 372
6.5
Частичные
вычисления,
трансформация
программ
и суперкомпиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
7
Функциональное
программирование
и
искусственный
интеллект
395
7.1
Основные задачи искусственного интеллекта . . . . . . . . . . . . . 396
7.2
Нечеткая математика и функциональное программирование . . . . 407
7.3
Логический вывод на знаниях . . . . . . . . . . . . . . . . . . . . . . 429
7.4
Общение с компьютером на естественном языке . . . . . . . . . . . 443
7.5
Перспективы функционального программирования
. . . . . . . . . 454
Заключение
463
Ответы на задачи для самостоятельного решения
465
Решения задач из главы 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 465


Оглавление
Решения задач из главы 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Решения задач из главы 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
Решения задач из главы 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Решения задач из главы 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
Решения задач из главы 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
A Функциональные языки программирования и Интернет-ресурсы
по функциональному программированию
496
Функциональные языки программирования . . . . . . . . . . . . . . 496
Русские Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . . . . 502
Иностранные Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . 503
B Опции различных сред разработки на языке Haskell
506
Интегрированная среда разработки HUGS 98 . . . . . . . . . . . . . 506
Компилятор GHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
Компилятор NHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
Компилятор компиляторов Happy . . . . . . . . . . . . . . . . . . . . 528
C Описание стандартного модуля Prelude
531
Функции
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
Описание некоторых операторов языка Haskell . . . . . . . . . . . . 586
D Краткий
словарь
терминов
из
области
функционального
программирования
589
Литература
599
Общая литература по функциональному программированию . . . . 599
Книги, руководства и статьи по языку Haskell
. . . . . . . . . . . . 601
Комбинаторная логика и λ-исчисление . . . . . . . . . . . . . . . . . 602
Математическая лингвистика и теория построения трансляторов . 603
Искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . 604


Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Краткая биография автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
О пользовании книгой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22
Состав и структура представления информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
Контактная информация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1
Основы функционального программирования . . . . . . . . . . . . . . . . . . 27
В этой главе рассматриваются основополагающие принципы функционального
программирования как отдельного направления в математической науке и технологии создания программного обеспечения. Приводится история развития
функционального программирования, описываются предпосылки его развития.
В главе рассматривается больше теоретического материала, нежели практического, поэтому пока изложение ведется без рассмотрения синтаксиса языка
Haskell. Однако для приведения примеров используется именно этот язык наряду с математическими формулами. Изложение знаний о языке Haskell начинается с главы 2.
1.1
История функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Краткая история развития теории функционального программирования в мире
и в России. Разработка функциональных языков для подтверждения теоретических выкладок. Проблемы, с которыми столкнулись исследователи при разработке функциональных языков программирования. Современное состояние
теории функционального
программирования.
Стандарт
Haskell
98
как
результат унификации и стандартизации процессов развития функционального
программирования.
Предпосылки создания функционального программирования ........................ 34
История языка Haskell ..............................................................38


Заключительные слова ..............................................................42
Основные свойства функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
Описание основных свойств функциональных языков программирования. Краткость и простота, строгая типизация, модульность, функциональные значения и объекты, чистота и отложенные вычисления. Понимание свойств функциональных языков на примере языка Haskell.
Краткость и простота .............................................................44
Строгая типизация ................................................................ 48
Модульность ........................................................................50
Функции — это значения и объекты вычисления ................................... 51
Чистота (отсутствие побочных эффектов и детерминированность) ............. 53
Отложенные (ленивые) вычисления ................................................ 55
1.3
Типовые задачи, решаемые методами ФП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Краткое описание семи типовых задач, которые решаются методами функционального программирования. Получение остаточной процедуры. Построение
математического описания функций. Определение формальной семантики языка программирования. Описание динамических структур данных. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой. Доказательство наличия некоторого свойства программы. Эквивалентная трансформация программ.
Получение остаточной процедуры .................................................. 60
Построение математического описания функций .................................. 62
Определение формальной семантики языка программирования ..................... 64
Описание динамических структур данных ..........................................64
Автоматическое построение функций по описанию структур данных ............. 66
Доказательство наличия некоторого свойства программы .........................67
Эквивалентная трансформация программ .......................................... 68
1.4
Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Описание метода конструирования функций, предложенного Ч. Хоаром (синтаксически ориентированное конструирование). Метаязык для конструирования функций. Примеры определения типов и функций для обработки этих типов.
Декартово произведение ............................................................ 70
Размеченное объединение ............................................................71


Примеры определения типов данных ................................................72
Доказательство свойств функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86
Задача доказательства свойств функций. Описание процесса доказательства
свойств функций в зависимости от типа области определения функций. Примеры доказательства свойств функций.
Область определения D — линейно-упорядоченное множество .....................88
Множество D определяется как индуктивный класс ...............................89
Рассмотрение некоторых примеров доказательства свойств функций .............91
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2
Базовые принципы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
Глава посвящена введению в основные положения языка Haskell, приводится описание синтаксиса для решения основных задач по созданию отдельных функций
и законченных модулей. Рассматриваются базовые объекты «список» и «функция» для изучения в рамках функционального программирования, а также их
реализация на языке Haskell.
2.1
Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
Понятие списка в функциональном программировании. Списки как основная
структура для работы с функциональными языками. Базисные операции для работы со списками. Списки и списочные структуры. Программная реализация
списков в функциональных языках. Списки в языке Haskell. Генераторы списков
и математические последовательности. Бесконечные списки и другие структуры данных. Кортежи.
Проекция списков в язык Haskell ...................................................101
Несколько слов о программной реализации .........................................104
Примеры ........................................................................... 106
Определители списков и математические последовательности .................. 110
Кортежи .......................................................................... 117
2.2
Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118
Функция — основной объект изучения функционального программирования. Соглашения по именованию объектов в языке Haskell. Описание и определение
функций на языке Haskell. Образцы и клозы. Передача параметров и возвращение
значений функциями. Инфиксный способ записи функций. Функция как объект


для передачи в другие функции. Программа на языке Haskell — функция, описывающая процесс вычисления.
Соглашения по именованию ........................................................118
Общий вид определения функции .................................................. 119
Образцы и клозы ................................................................... 119
Вызовы функций ................................................................... 125
Использование λ-исчисления ....................................................... 126
Инфиксный способ записи функций ................................................ 127
Несколько слов о функциях высшего порядка ...................................... 131
2.3
Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131
Структуры и типы данных. Типы функций. Каррированные и некаррированные
функции. Язык Haskell и его механизмы для организации каррированных и некаррированных функций. Описание типов функций на языке Haskell. Частичное
применение. Ленивые (отложенные) вычисления на языке Haskell.
Структуры данных и их типы .................................................... 132
Синонимы типов .................................................................. 136
Типы функций в функциональных языках ..........................................137
Полиморфные типы ................................................................140
2.4
Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142
Охраняющие выражения и конструкции. Локальные переменные для оптимизации кода на функциональном языке и на языке Haskell. Использование накапливающего параметра (аккумулятора) для оптимизации процесса вычислений.
Принципы построения определений функций с накапливающим параметром. Головная и хвостовая рекурсии.
Охрана ............................................................................. 143
Ветвление алгоритма ............................................................. 145
Локальные переменные .............................................................146
Двумерный синтаксис ............................................................. 149
Накапливающий параметр — аккумулятор ....................................... 150
Принципы построения определений с накапливающим параметром ............... 152
2.5
Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
Модули как способы структуризации и организации программ на языке Haskell.
Импорт и экспорт данных при помощи модулей. Сокрытие данных. Абстрактные типы данных и интерфейсы. Иные аспекты использования модулей.


Абстрактные типы данных ....................................................... 156
Другие аспекты использования модулей ........................................... 157
Литературный код ................................................................ 158
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .160
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .161
3
Классы и их экземпляры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Эта
глава
посвящена
рассмотрению
симбиоза
парадигм
функционального
и объектно-ориентированного программирования. Большинство современных
функциональных языков поддерживают механизмы и методы, разработанные в
рамках объектно-ориентированного программирования, в том числе и такие базовые концепты, как «наследование», «инкапсуляция» и «полиморфизм». Не обошел своим вниманием этот аспект и язык Haskell, в котором имеются достаточные средства для программирования в объектно-ориентированном стиле.
3.1
Параметрический полиморфизм данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Понятие класса и его реализации в языке Haskell. Чистый (параметрический)
полиморфизм на языке Haskell. Примеры параметрического полиморфизма в императивных и функциональных языках, а также в языке Haskell.
3.2
Классы в языке Haskell как способ абстракции действительности . . . . . 170
Расширенное описание понятия класса в языке Haskell. Класс как высшая абстракция данных и методов для их обработки. Методы класса — шаблоны функций для реализации обработки данных. Минимальное описание методов класса
и связь методов.
Модель типизации Хиндли-Милнера ...............................................171
Определение классов ............................................................... 176
3.3
Наследование и реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Наследование классов и наследование методов. Экземпляры классов — реализация интерфейсов, предоставляемых реализуемым классом. Реализация методов
для обработки данных. Класс — шаблон типа, реализация класса — тип данных.
Наследование .......................................................................180
Реализация .........................................................................182
Реализация для существующих типов ............................................ 186
Сорта типов ...................................................................... 187
Дополнительные возможности при определении типов данных ...................189


Стандартные классы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192
Краткое описание всех стандартных классов, разработанных для облегчения
программирования на языке Haskell. Дерево наследования стандартных классов.
Типичные способы использования стандартных классов языка Haskell. Реализация стандартных классов — типы в языке Haskell.
Класс Bounded ......................................................................192
Класс Enum ......................................................................... 193
Класс Eq ........................................................................... 195
Класс Floating .................................................................... 195
Класс Fractional .................................................................. 196
Класс Functor ......................................................................197
Класс Integral .................................................................... 198
Класс Ix ........................................................................... 199
Класс Monad ........................................................................ 199
Класс Num .......................................................................... 200
Класс Ord .......................................................................... 201
Класс Read ......................................................................... 202
Класс Real ......................................................................... 203
Класс RealFloat ................................................................... 203
Класс RealFrac .................................................................... 204
Класс Show ......................................................................... 206
3.5
Сравнение с другими языками программирования . . . . . . . . . . . . . . . . . . . . . 207
Более или менее полное сравнение понятий «класс» и «реализация класса» в языке Haskell с объектно-ориентированными языками программирования (на примере языков C++ и Java, а также некоторых других языков). Глобальные отличия
понятия «класс» в функциональных и объектно-ориентированных языках.
Окончательные замечания .........................................................209
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211
4
Монады
—
последовательное
выполнение
действий
в функциональной парадигме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
Глава описывает такое незаурядное понятие, введенное в функциональной парадигме программирования, как «монада». Монады, основанные на математической теории категорий, позволяют внедрить в функциональный подход опре
Доступ онлайн
479 ₽
В корзину