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

Функциональное

программирование

на языке Haskell

Душкин Р. В.

Москва, 2016

Оглавление

Содержание
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

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

Содержание
11

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

4.1
Монада как тип-контейнер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

Описание монады как типа-контейнера. Использование монад в функциональ-
ных языках. Свойства монадических типов. Операции связывания с передачей
и без передачи результата выполнения операции на предыдущем шаге. Правила
построения монад.

Определение понятия «монада» ................................................... 215

Нотация do ........................................................................ 218

Правила построения монад ........................................................ 220

4.2
Последовательное выполнение действий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222

Действие — элемент функциональной парадигмы. Императивный код внутри
функционального. Выполнение действий и возвращение результата. Сокращен-
ный способ записи последовательности действий. Списки действий. Програм-
мирование при помощи действий.

Класс Computations ................................................................ 224

Монада State ...................................................................... 227

4.3
Операции ввода/вывода в языке Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .239

Более или менее полное описание базовых операций ввода/вывода в языке Haskell.
Монада IO. Обработка исключений. Использование файлов, каналов и обработчи-
ков. Нарушение теоретических принципов функционального программирования
в монаде IO.

Действия ввода/вывода ............................................................240

Программирование при помощи действий ......................................... 244

Обработка исключений ............................................................ 245

Файлы и потоки ................................................................... 247

Окончательные замечания .........................................................251

4.4
Стандартные монады языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Подробное описание монадических типов в стандартной библиотеке языка
Haskell. Назначение и применимость монадических типов. Примеры использо-
вания стандартных монадических типов (кроме списков и монады IO). Модуль
Monad. Монады Glasgow Haskell Compiler.

Содержание

Модуль Monad ...................................................................... 253

Стандартные монады ............................................................. 257

4.5
Разработка собственных монад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

Критерии возможности и необходимости разработки собственного монадиче-
ского типа. Комбинирование монадических вычислений. Преобразователи монад.
Примеры преобразования.

Комбинирование монадических вычислений ........................................263

Преобразователи монад ............................................................ 264

Пример с преобразователем StateT ................................................ 267

Окончательные замечания .........................................................268

Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .270

5
Комбинаторная логика и λ-исчисление . . . . . . . . . . . . . . . . . . . . . . . . 273

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

5.1
Основы комбинаторной логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

Введение в комбинаторную логику. Поверхностное описание принципов комбина-
торной логики. Комбинаторы и вычисления при помощи комбинаторов. Базисы
в комбинаторной логике. Использование базисных комбинаторов для выраже-
ния любых вычислительных процессов. Числа и иные математические объекты
в виде комбинаторов.

Базовые комбинаторы ............................................................. 274

Комбинатор неподвижной точки ................................................. 281

Нумералы и арифметические операции ............................................ 283

Заключительные слова .............................................................286

5.2
Абстракция функций как вычислительных процессов . . . . . . . . . . . . . . . . . 288

Функция — объект математического исследования. Вычислительный процесс —
функция. Описание функций как λ-выражений. Свободные и связанные иденти-

Содержание
13

фикаторы. Применение (аппликация) значений к λ-выражениям. Непрерывная
точка функций и теорема о непрерывной точке.

«Наивное» определение λ-исчисления .............................................. 289

Связь с комбинаторной логикой ................................................... 292

Редукция ........................................................................... 293

Тезис Черча-Тьюринга ............................................................. 294

5.3
λ-исчисление
как
теоретическая
основа
функционального
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298

Предположение о том, что любая функция представима в виде λ-выражения.
Интенсионал и экстенсионал функций. Формальная система. Построение фор-
мальной системы для обоснования теории функционального программирования.
Правила вывода. Соответствия между вычислениями функциональных про-
грамм и редукцией λ-выражений.

Построение формальной системы ................................................. 299

Функциональное программирование как формальная система ..................... 303

Теорема Черча-Россера .............................................................305

5.4
Кодирование данных в λ-исчислении . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .307

Механизм кодирования данных в λ-исчислении. λ-исчисление — достаточный
формализм для представления значений истинности, упорядоченных пар, на-
туральных чисел, списков, а также базовых операций над этими объектами.

Булевские значения ................................................................ 308

Упорядоченные пары ............................................................... 309

Натуральные числа ................................................................ 311

Списки ............................................................................. 314

5.5
Редукция и вычисления в функциональных языках . . . . . . . . . . . . . . . . . . . .315

Понятие
редукции.
Частичные
вычисления
с
точки
зрения
редукции
λ-выражений. Различные редукционные стратегии и их свойства.

Стратегия редукции и стратегия вычислений .................................... 315

Ленивая редукция ..................................................................321

Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .327
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .329

6
Трансляторы программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331

Содержание

В главе 6 представлено краткое описание теории построения трансляторов
для интерпретации и компиляции языков программирования. Теория рассмат-
ривается на примерах, написанных на языке Haskell. Кроме того, рассматрива-
ются способы построения парсеров, а также готовые библиотеки для синтак-
сического анализа. Суперкомпиляция.

6.1
Математическая лингвистика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331

Краткое введение в математическую лингвистику. Обзор методов и принци-
пов математической лингвистики. Классификация языков и грамматик. Ко-
нечные автоматы и контекстно-свободные языки. Грамматики типа LL(k).
Контекстно-зависимые грамматики.

Базовые понятия .................................................................. 332

Расширенная нотация Бэкуса — Наура ............................................ 335

Классификация грамматик ........................................................ 337

Конечные лингвистические автоматы ............................................ 338

Синтаксический анализ контекстно-свободных языков ........................... 343

6.2
Краткое введение в теорию построения трансляторов . . . . . . . . . . . . . . . . . 346

Трансляторы: определения, типы и классификация, применимость для тех или
иных типов языков и грамматик. Интерпретаторы и компиляторы. Компиля-
торы компиляторов. Методы построения трансляторов. Автоматическое построение 
транслятора по грамматике языка (для ограниченного множества
языков). Понятие трансформационной грамматики.

Классификация трансляторов и их типовые структуры ......................... 347

Трансформационные грамматики .................................................. 354

Автоматическое построение анализатора для отдельных типов языков ......... 358

6.3
Реализация трансляторов на языке Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .360

Функциональные языки, как естественный инструмент реализации трансляторов. 
Синтаксические анализаторы. Методы написания трансляторов на языке
Haskell. Примеры синтаксических анализаторов для различных форматов данных. 
Пример вычисления арифметических выражений, записанных в различной
нотации.

Простейшие парсеры ...............................................................361

Комбинаторы синтаксического анализа ........................................... 363

Дополнительные комбинаторы синтаксического анализа ......................... 366

Анализ нотации Бэкуса — Наура .................................................. 368

Содержание
15

6.4
Библиотеки для создания трансляторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372

Описание имеющихся библиотек для языка Haskell, предназначенных для создания 
трансляторов. Монадическая библиотека Parsec для самостоятельного создания 
трансляторов. Компилятор компиляторов Happy.

Монадическая библиотека парсеров Parsec ........................................ 372

Компилятор компиляторов Happy ................................................. 377

6.5
Частичные
вычисления,
трансформация
программ
и суперкомпиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Задача трансформации программ. Частичные вычисления, как инструмент
для трансформации программ. Частичный вычислитель — инструмент для получения 
остаточного кода заданной функциональной программы. Интерпретатор, 
компилятор и компилятор компиляторов, их связь. Проекции Футамуры-
Турчина. Суперкомпиляция.

Частичные вычисления и трансляция программ .................................. 382

Проекции Футамуры — Турчина ...................................................385

Трансформация программ .......................................................... 387

Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .392
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .394

7
ФП и искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

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

7.1
Основные задачи искусственного интеллекта . . . . . . . . . . . . . . . . . . . . . . . . . . .396

Историческая справка о развитии искусственного интеллекта, как области научного 
исследования. Введение в базовые понятия искусственного интеллекта.
Место функционального программирования в искусственном интеллекте. Функциональное 
и логическое программирования. Задачи искусственного интеллекта, 
которые могут быть решены при помощи методов и средств функционального 
программирования.

История развития искусственного интеллекта ...................................398

Различные подходы к построению систем искусственного интеллекта ........... 402

Место функционального программирования в искусственном интеллекте ........405

Содержание

7.2
Нечеткая математика и функциональное программирование . . . . . . . . . . 407

Небольшой экскурс в нечеткую математику. Функции принадлежности и лингвистические 
переменные. Базовые операции над функциями принадлежности.
Кусочно-линейные
функции
принадлежности.
Операции
сравнения,
арифметические

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

Базовые концепты нечеткой логики ............................................... 407

От нечеткой логики к нечеткой математике .................................... 409

Функции принадлежности как способ описания нечетких значений .............. 411

Нечеткие и лингвистические переменные ......................................... 417

Операции над функциями принадлежности ....................................... 418

Пример модуля для обработки кусочно-линейных функций принадлежности ..... 423

7.3
Логический вывод на знаниях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

Знания и данные. Модели представления знаний. Понятие логического вывода
на знаниях. Стратегии вывода на знаниях. Машины вывода. Эволюция машин-
ного вывода на знаниях. Интерпретаторы функциональных языков как есте-
ственные машины вывода. Язык Haskell и его возможности в логическом выводе
на знаниях. Универсальный вывод на продукционной модели знания.

Знания и данные ................................................................... 430

Вывод на знаниях .................................................................. 434

Прямой нечеткий вывод ........................................................... 437

Обратный нечеткий вывод ........................................................ 439

Некоторые окончательные замечания о машинном выводе ........................ 442

7.4
Общение с компьютером на естественном языке . . . . . . . . . . . . . . . . . . . . . . . 443

Принципы общения с компьютерными системами на естественном языке. Огра-
ниченный естественный язык, деловая проза. Трансляция фраз на естественном
языке во внутренний язык представления смысла. Понимание текстов на есте-
ственном языке. Использование методов функционального программирования.

Обобщенная схема интеллектуальных диалоговых систем ........................444

Схема анализа входного текста ................................................... 447

Некоторые окончательные замечания ............................................. 453

7.5
Перспективы функционального программирования . . . . . . . . . . . . . . . . . . . . 454

Содержание
17

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

Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .460
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .461

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

Ответы на задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 465
Решения задач из главы 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
Решения задач из главы 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Решения задач из главы 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
Решения задач из главы 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Решения задач из главы 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
Решения задач из главы 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

A
Функциональные языки программирования и Интернет-ресурсы
по функциональному программированию . . . . . . . . . . . . . . . . . . . . . . . . . 496

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

Функциональные языки программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496
Русские Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
Иностранные Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .503

B
Опции различных сред разработки на языке Haskell . . . . . . . . . 506

Описание типичных настроек интегрированных сред разработки и компилято-
ров на примере продуктов HUGS 98 и GHC для полноценной работы и выполне-
ния различных задач на языке Haskell. Список команд, ключей командной строки
и внутренних директив интерпретатора HUGS 98. Список параметров команд-
ной строки для компилятора GHC. Другие функциональные средства разработ-
ки.

Интегрированная среда разработки HUGS 98 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
Компилятор GHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .510
Компилятор NHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .523
Компилятор компиляторов Happy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

Введение

C
Описание стандартного модуля Prelude . . . . . . . . . . . . . . . . . . . . . . . 531

Список функций из стандартного модуля языка Haskell Prelude с более или менее
подробным описанием.

Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
Описание некоторых операторов языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586

D
Краткий
словарь
терминов
из
области
функционального
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

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

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
Общая литература по функциональному программированию . . . . . . . . . . . . . . . .599
Книги, руководства и статьи по языку Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
Комбинаторная логика и λ-исчисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .602
Математическая лингвистика и теория построения трансляторов . . . . . . . . . . . 603
Искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604

Введение

Данная книга является первым в России изданием, рассматривающим функциональное 
программирование в полном объеме, достаточном и для понимания
новичку, и для использования книги в качестве справочного пособия теми, кто
уже использует парадигму1 функционального программирования в своей практике. 
Эту книгу можно использовать и в качестве учебника по функциональному
программированию, и в качестве вспомогательного учебного пособия по смежным 
дисциплинам, в первую очередь по комбинаторной логике и λ-исчислению2.
Также книга будет интересна тем, кто всерьез занимается изучением новых компьютерных 
технологий, искусственного интеллекта и синергетическим слиянием
научных направлений человеческой деятельности.

Необходимость написания подобной книги в первую очередь вызвана тем,
что на русском языке нет полноценного справочного и учебного пособия по языку 
Haskell, в то время как этот функциональный язык все больше и больше
завоевывает сердца программистов по всему миру. Более того, этот язык уже
используют и для написания полноценных программных систем, в том числе
для коммерческого использования. Однако в России изучение языка Haskell про-
поведуется лишь энтузиастами, а в строгой академической школе довольству-
ются традиционным рассмотрением языка Lisp в качестве иллюстрации основ
функционального программирования.

1 Под парадигмой (от греч. pardeigma — пример, модель, образец) здесь и далее понимается
общая концептуальная схема постановки проблем и методов их решения. В более узком смысле
под парадигмой программирования будет пониматься не просто стиль написания программ,
а способ мышления, который позволяет использовать тот или иной стиль при создании таких
программ.
2 Основы комбинаторной логики и λ-исчисление кратко рассматриваются в главе 5 этой
книги.

Введение

Однако если рассматривать англоязычные источники, руководства и учебни-
ки по языку Haskell, то налицо сложности, с которыми сталкиваются те, кто
начинает самостоятельно изучать этот функциональный язык. Во-первых, это
скупой и формальный подход при описании синтаксиса языка — на этом принци-
пе основаны все руководства по языку Haskell. Во-вторых, это отсутствие какой-
либо системности, или даже присутствие антисистемности в изложении как основ
функционального программирования, так и способов программирования на язы-
ке Haskell. Например, в учебнике «Haskell: The Craft of Functional Programming»
автор перескакивает с одной темы на другую безо всяких переходов между ними.
Начинает с описания списков, а продолжает принципами создания программно-
го обеспечения вообще. Описывает систему классов, перескакивает на описание
системы ввода/вывода практически без затрагивания темы монад. А это — один
из основных учебников по языку Haskell на английском языке.

Книга рассчитана на всех, кто интересуется современными тенденциями раз-
вития компьютерной науки и технологии, а также искусственным интеллектом.
Она может служить основным или дополнительным учебным пособием для сту-
дентов и аспирантов, обучающихся по специальности «прикладная математика»
и специализации «искусственный интеллект». Также книга будет полезна в каче-
стве справочного материала по языку Haskell всем тем, кто использует функцио-
нальную парадигму в целом и этот функциональный язык в частности в научных
исследованиях или повседневной работе.

Для чтения книги необходимо обладать базовыми познаниями в дискретной
математике, а также иметь представление о методах разработки алгоритмах и ал-
горитмическом решении задач (теория алгоритмов). В процессе написания книги
полагалось, что читатель знаком с базовыми концептами дискретной математи-
ки, поэтому лишние математические определения в книге не приводятся. Слож-
ные разделы математики, представленные в заключительных главах, требуют
более серьезных знаний, поэтому их описание сопровождается небольшими экс-
курсами в теорию. Это касается таких разделов дискретной математики, как
комбинаторная логика, λ-исчисление, математическая лингвистика и теория по-
строения трансляторов, а также базовые принципы искусственного интеллекта.

Рассмотрение парадигмы функционального программирования производится
на примере языка Haskell, на котором написаны все исходные коды, представлен-
ные в книге. Все представленные примеры, функции, модули и исходные тексты
программ проверены в интегрированной среде разработки HUGS 98 (за исклю-

Введение
21

чением тех, которые предназначены для компиляции в среде GHC — Glasgow
Haskell Compiler). Для удобства читателя, желающего проверить и закрепить
свои знания на практике, все приведенные в книге программы и функции раз-

Книгу нельзя рассматривать в качестве скрупулезного введения в язык

Haskell и программирования на нем, так как цель автора — не преподать неко-
торую догму относительно использования языка Haskell, но направить читателя
на путь, следуя которому он сам сможет понять, что и как необходимо делать
для получения правильных программ. В связи с этим в книге не рассматрива-
ются вопросы о том, какие инструкции на языке необходимо написать, чтобы
получить определенный эффект (или рассматриваются в самом минимальном
виде), но предлагаются пути решения разных задач, встающих перед програм-
мистом. Именно поэтому главы, непосредственно посвященные языку Haskell,
написаны сухим языком. Цель этих глав — преподнести читателю как можно
больше информации о синтаксисе языка без лишнего упоминания о том, как
использовать предлагаемые синтаксические конструкции. Для этого необходимо
обратиться к последним главам книги, где, однако, упоминание о языке Haskell
сведено к минимуму. Такой формат представления информации позволит (и даже
принудит) читателю самостоятельно следовать по пути использования парадиг-
мы функционального программирования.

Также на прилагаемом CD-диске можно найти текст данной книги в формате

Adobe PDF (Portable Document Format) для использования его в личных нуждах.

Краткая биография автора

Душкин Роман Викторович.
С 2001 г. читает лекции по функциональному

программированию для студентов четвертого курса кафедры кибернетики (№ 22)
факультета «К» Московского инженерно-физического института (МИФИ). Ба-
зисом для авторского курса по функциональному программированию послужил
текст лекций Г. М. Сергиевского, читавшихся до 2001 г. Данные лекции были
кардинально переработаны с учетом современных веяний в науке и технике, ос-
нова была переведена с языка Lisp на Haskell (вместе с полной переработкой
курса лабораторных работ), а сами лекции были дополнены строгим научным
обоснованием как самой парадигмы функционального программирования, так
и ее прикладных аспектов.

мещены на сайте издательства www.dmkpress.com

Введение

Р. В. Душкин является автором множества научных публикаций по те-
мам нечеткой математики, искусственного интеллекта и функционального
программирования в российских и зарубежных научных изданиях. Участвовал
во множестве национальных и международных научных конференций, прово-
димых под эгидой Российской Ассоциации Искусственного Интеллекта. Издал
ряд методических пособий, в том числе и для выполнения лабораторных работ
по функциональному программированию.

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

О пользовании книгой

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

Для написания имен функций, элементов формул и математических выраже-
ний, которые приводятся непосредственно в тексте книги, используется курсив-
ное начертание. Например: x ∈ C, f0, List(A).

Примеры фрагментов программ на языке Haskell и изредка на абстрактном
функциональном языке, который используется для объяснения теоретических
аспектов применения парадигмы функционального программирования, в тексте
книги приводятся при помощи моноширинной гарнитуры (машинописного шриф-
та):

length [] = 0
length (x:xs) = 1 + length xs

Упоминания об именах функций непосредственно в тексте также выделяют-
ся моноширинным начертанием символов: length, append. Кроме того, таким же
образом выделяются наименования модулей, стандартных библиотек и дополни-
тельных программных средств: Prelude, Parsec, Happy.

Введение
23

Иногда в тексте встречаются обозначения операций, наименования которых
состоят из одного или более нелитеральных символов. Для того чтобы как-то
отделять подобные обозначения от текста книги, такие операции заключают-
ся в круглые скобки, а сами обозначения приводятся моноширинным шрифтом.
Например: (+), (<@), (>>=). Сами скобки различного вида в круглые скобки не за-
ключаются: {}, [] и т. д. в случае, если необходимо показать отдельную скобку,
она заключается в кавычки: «(», «}» и т. д.

Листинги больших и законченных модулей на языке Haskell приводятся в виде
выделенных блоков:

Листинг 0.1. Пример текста программы из внешнего файла

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--
--
-- Модуль INTROEXAMPLE - пример правильно описанного модуля на языке Haskell. --
--
--
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
module IntroExample
(someFunction)
where

--------------------------------------------------------------------------------
-- Некоторая функция, выполняющая определённые действия.
--
-- Входные параметры:
--
n
- число, которое необходимо прибавить к каждому элементу списка.
--
(x:xs) - список, к каждому элементу которого необходимо прибавить число n.
--
-- Возвращаемое значение:
--
Список, составленный из сумм заданного числа n с элементами исходного
--
списка.

someFunction :: Int -> [Int] -> [Int]
someFunction n [] = []
someFunction n (x:xs) = (x + n) : someFunction n xs

--[ КОНЕЦ МОДУЛЯ ]--------------------------------------------------------------

Введение

Еще раз необходимо заметить, что все приведенные в книге листинги читатель
сможет найти на прилагаемом к книге CD-диске или на официальном сайте книги
в Интернете.

Состав и структура представления информации

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

Первая глава является своеобразным введением в проблематику — в ней при-
водится базовый методический материал, необходимый для понимания основ
функционального программирования и дальнейшего чтения книги. По существу,
первая глава — это пролог, который открывает путь в функциональный мир.

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

Третья
глава
посвящена
слиянию
функциональной
и
объектно-
ориентированной
парадигм
программирования,
что
должно
представить
язык Haskell в качестве современного средства разработки компьютерных при-
ложений. Рассматривается такое базовое понятие объектно-ориентированного
программирования, как «класс», и его применение в составе средств языка
Haskell. Кроме того, приводится более или менее полное описание стандартных
классов и их экземпляров, поставляемых в составе базового модуля Prelude.

Четвертая глава рассматривает такую незаурядную вещь, как «монада» —
расширение парадигмы функционального программирования для включения
в нее императивного подмножества структур языка Haskell для выполнения опе-
раций, связанных с использованием побочных эффектов (в первую очередь опе-
раций ввода/вывода). Так же как и в третьей главе, приводится подробное опи-
сание стандартных монад, которое поможет понять этот непростой объект и пол-
ноценно использовать язык Haskell для разработки сложных приложений.

По существу, для изучения самого языка Haskell достаточно прочитать пер-
вые четыре главы. С пятой главы начинается рассмотрение теории и услож-