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

УДК
004.4

ББК
32.973.26018.2
Д86

Душкин Р. В.

Д86
Функциональное программирование на языке Haskell. М.: ДМК Пресс, 200 .
ил.

ISBN 5940743358

Данная книга является первым в России изданием, рассматривающая

функциональное программирование в полном объеме, досточном для понимания новичку и для использования книги в качестве справочного пособия
теми, кто уже использует парадигму функционального программирования в
своей практике.  Изучсние прикладных основ показано на примере языка
Haskell, на сегодняшний день являющегося самым мощным и развитым инструментом функционального программирования.

Издание можно использоватьи в качестве учебника по функциональному

программированию, и в качестве самостоятельного учебного пособия по
смежным дисциплинам, в первую очередь по комбинаторной логике и λисчислению.

Также книга будет интересна тем, кто всерьез занимается изучением новых компьютерных технологий, искусственного интеллекта и экспертных
систем.

К книге придагается компактдиск с транслятором Haskell, а также различными библиотеками к нему, дополнительными утилитами и рабочими
примерами программ, рассмотренных в книге.

УДК 004.4
ББК 32.973.26018.2

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то

ни было форме и какими бы то ни было средствами без письменного разрешения владельцев
авторских прав.

Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность

технических ошибок все равно существует, издательство не может гарантировать абсолютную
точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

© Душкин Р. В.

ISBN 5940743358
© Оформление ДМК Пресс

8

Оглавление

Содержание
5

Введение
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

Оглавление
3

4
Монады
—
последовательное
выполнение
действий
в функциональной парадигме
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

1.2
Основные свойства функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . .44

Описание основных свойств функциональных языков программирования. Краткость и простота, строгая типизация, модульность, функциональные значения и объекты, чистота и отложенные вычисления. Понимание свойств функциональных языков на примере языка Haskell.

Краткость и простота .............................................................44

Строгая типизация ................................................................ 48

Модульность ........................................................................50

Функции — это значения и объекты вычисления ................................... 51

Чистота (отсутствие побочных эффектов и детерминированность) ............. 53

Отложенные (ленивые) вычисления ................................................ 55

1.3
Типовые задачи, решаемые методами ФП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Краткое описание семи типовых задач, которые решаются методами функционального программирования. Получение остаточной процедуры. Построение
математического описания функций. Определение формальной семантики языка программирования. Описание динамических структур данных. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой. Доказательство наличия некоторого свойства программы. Эквивалентная трансформация программ.

Получение остаточной процедуры .................................................. 60

Построение математического описания функций .................................. 62

Определение формальной семантики языка программирования ..................... 64

Описание динамических структур данных ..........................................64

Автоматическое построение функций по описанию структур данных ............. 66

Доказательство наличия некоторого свойства программы .........................67

Эквивалентная трансформация программ .......................................... 68

1.4
Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Описание метода конструирования функций, предложенного Ч. Хоаром (синтаксически ориентированное конструирование). Метаязык для конструирования функций. Примеры определения типов и функций для обработки этих типов.

Декартово произведение ............................................................ 70

Размеченное объединение ............................................................71

Содержание
7

Примеры определения типов данных ................................................72

1.5
Доказательство свойств функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .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.
Импорт и экспорт данных при помощи модулей. Сокрытие данных. Абстрактные типы данных и интерфейсы. Иные аспекты использования модулей.

Содержание
9

Абстрактные типы данных ....................................................... 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

Содержание

3.4
Стандартные классы языка 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

Глава описывает такое незаурядное понятие, введенное в функциональной парадигме программирования, как «монада». Монады, основанные на математической теории категорий, позволяют внедрить в функциональный подход опре