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

Содержание ......Page 8
Введение ......Page 22
Краткая биография автора ......Page 24
О пользовании книгой ......Page 25
Состав и структура представления информации ......Page 27
Контактная информация ......Page 29
1 Основы функционального программирования ......Page 30
1.1 История функционального программирования ......Page 31
Предпосылки создания функционального программирования ......Page 37
История языка Haskell ......Page 41
Заключительные слова ......Page 45
Краткость и простота ......Page 47
Строгая типизация ......Page 51
Модульность ......Page 53
Функции — это значения и объекты вычисления ......Page 54
Чистота (отсутствие побочных эффектов и детерминированность) ......Page 56
Отложенные (ленивые) вычисления ......Page 58
1.3 Типовые задачи, решаемые методами ФП ......Page 61
Получение остаточной процедуры ......Page 63
Построение математического описания функций ......Page 65
Описание динамических структур данных ......Page 67
Автоматическое построение «значительной» части программы по описанию структур данных ......Page 69
Доказательство наличия некоторого свойства программы ......Page 70
Эквивалентная трансформация программ ......Page 71
1.4 Конструирование функций ......Page 72
Декартово произведение ......Page 73
Размеченное объединение ......Page 74
Примеры определения типов данных ......Page 75
1.5 Доказательство свойств функций ......Page 89
Область определения D — линейно-упорядоченное множество ......Page 91
Множество D определяется как индуктивный класс ......Page 92
Рассмотрение некоторых примеров доказательства свойств функций ......Page 94
Вопросы для самоконтроля ......Page 98
Задачи для самостоятельного решения ......Page 100
2 Базовые принципы языка Haskell ......Page 102
2.1 Списки — основа функциональных языков ......Page 103
Проекция списков в язык Haskell ......Page 104
Несколько слов о программной реализации ......Page 107
Примеры ......Page 109
Определители списков и математические последовательности ......Page 113
Кортежи ......Page 120
Соглашения по именованию ......Page 121
Образцы и клозы ......Page 122
Вызовы функций ......Page 128
Использование A-исчисления ......Page 129
Инфиксный способ записи функций ......Page 124
2.3 Списки — основа функциональных языков ......Page 134
Структуры данных и их типы ......Page 135
Синонимы типов ......Page 139
Типы функций в функциональных языках ......Page 140
Полиморфные типы ......Page 143
2.4 Списки — основа функциональных языков ......Page 145
Охрана ......Page 146
Ветвление алгоритма ......Page 148
Локальные переменные ......Page 149
Двумерный синтаксис ......Page 152
Накапливающий параметр — аккумулятор ......Page 153
Принципы построения определений с накапливающим параметром ......Page 155
2.5 Списки — основа функциональных языков ......Page 156
Абстрактные типы данных ......Page 159
Другие аспекты использования модулей ......Page 160
Литературный код ......Page 161
Вопросы для самоконтроля ......Page 163
Задачи для самостоятельного решения ......Page 164
3 Классы и их экземпляры ......Page 167
3.1 Параметрический полиморфизм данных ......Page 168
3.2 Классы в языке Haskell как способ абстракции действительности ......Page 173
Модель типизации Хиндли-Милнера ......Page 174
Определение классов ......Page 179
Наследование ......Page 183
Реализация ......Page 185
Реализация для существующих типов ......Page 189
Сорта типов ......Page 190
Дополнительные возможности при определении типов данных ......Page 192
Класс Bounded ......Page 195
Класс Епит ......Page 196
Класс Floating ......Page 198
Класс Fractional ......Page 199
Класс Functor ......Page 200
Класс Integral ......Page 201
Класс Monad ......Page 202
Класс Num ......Page 203
Класс Ord ......Page 204
Класс Read ......Page 205
Класс RealFloat ......Page 206
Класс RealFrac ......Page 207
Класс Show ......Page 208
3.5 Сравнение с другими языками программирования ......Page 210
Окончательные замечания ......Page 212
Вопросы для самоконтроля ......Page 213
Задачи для самостоятельного решения ......Page 214
4 Монады — императивный мир в функциональной парадигме .......Page 216
4.1 Монада как тип-контейнер ......Page 217
Определение понятия «монада» ......Page 218
Нотация do ......Page 221
Правила построения монад ......Page 223
4.2 Последовательное выполнение действий ......Page 225
Класс Computations ......Page 227
Монада State ......Page 230
4.3 Операции ввода/вывода в языке Haskell ......Page 242
Действия ввода/вывода ......Page 243
Программирование при помощи действий ......Page 247
Обработка исключений ......Page 248
Файлы и потоки ......Page 250
Окончательные замечания ......Page 254
4.4 Стандартные монады языка Haskell ......Page 255
Модуль Monad ......Page 256
Стандартные монады ......Page 260
4.5 Разработка собственных монад ......Page 265
Комбинирование монадических вычислений ......Page 266
Преобразователи монад ......Page 267
Пример с преобразователем StateT ......Page 270
Окончательные замечания ......Page 271
Вопросы для самоконтроля ......Page 272
Задачи для самостоятельного решения ......Page 273
5 Комбинаторная логика и A-исчисление ......Page 276
Базовые комбинаторы ......Page 277
Комбинатор неподвижной точки ......Page 284
Нумералы и арифметические операции ......Page 286
Заключительные слова ......Page 289
5.2 Абстракция функций как вычислительных процессов ......Page 291
«Наивное» определение A-исчисления ......Page 292
Связь с комбинаторной логикой ......Page 295
Редукция ......Page 296
Тезис Черна- Тьюринга ......Page 297
5.3 A-исчисление как теоретическая основа функционального программирования ......Page 301
Построение формальной системы ......Page 302
Функциональное программирование как формальная система ......Page 306
Теорема Черча-Россера ......Page 308
5.4 Кодирование данных в Л-исчислении ......Page 310
Булевские значения ......Page 311
Упорядоченные пары ......Page 312
Натуральные числа ......Page 314
Списки ......Page 317
Стратегия редукции и стратегия вычислений ......Page 318
Ленивая редукция ......Page 324
Вопросы для самоконтроля ......Page 330
Задачи для самостоятельного решения ......Page 332
6.1 Математическая лингвистика ......Page 334
Базовые понятия ......Page 335
Расширенная нотация Бэкуса — Наура ......Page 338
Классификация грамматик ......Page 340
Конечные лингвистические автоматы ......Page 341
Синтаксический анализ контекстно-свободных языков ......Page 346
6.2 Краткое введение в теорию построения трансляторов ......Page 349
Классификация трансляторов и их типовые структуры ......Page 350
Трансформационные грамматики ......Page 357
Автоматическое построение анализатора для отдельных типов языков ......Page 361
6.3 Реализация трансляторов на языке Haskell ......Page 363
Простейшие парсеры ......Page 364
Комбинаторы синтаксического анализа ......Page 366
Дополнительные комбинаторы синтаксического анализа ......Page 369
Анализ нотации Бэкуса — Наура ......Page 371
Монадическая библиотека парсеров Parsec ......Page 375
Компилятор компиляторов Happy ......Page 380
6.5 Частичные вычисления, трансформация программ и суперкомпиляция ......Page 384
Частичные вычисления и трансляция программ ......Page 385
Проекции Футамуры — Турчина ......Page 388
Трансформация программ ......Page 390
Вопросы для самоконтроля ......Page 395
Задачи для самостоятельного решения ......Page 397
7 ФП и искусственный интеллект ......Page 398
7.1 Основные задачи искусственного интеллекта ......Page 399
История развития искусственного интеллекта ......Page 401
Различные подходы к построению систем искусственного интеллекта ......Page 405
Место функционального программирования в искусственном интеллекте ......Page 408
Базовые концепты нечеткой логики ......Page 410
От нечеткой логики к нечеткой математике ......Page 412
Функции принадлежности как способ описания нечетких значений ......Page 414
Нечеткие и лингвистические переменные ......Page 419
Операции над функциями принадлежности ......Page 421
Пример модуля на языке Haskell для обработки кусочно-линейных функций принадлежности ......Page 426
7.3 Логический вывод на знаниях ......Page 432
Знания и данные ......Page 433
Вывод на знаниях ......Page 437
Прямой нечеткий вывод ......Page 440
Обратный нечеткий вывод ......Page 442
Некоторые окончательные замечания о машинном выводе ......Page 445
7.4 Общение с компьютером на естественном языке ......Page 446
Обобщенная схема интеллектуальных диалоговых систем ......Page 447
Схема анализа входного текста : ......Page 450
Некоторые окончательные замечания ......Page 456
7.5 Перспективы функционального программирования ......Page 457
Вопросы для самоконтроля ......Page 463
Задачи для самостоятельного решения ......Page 464
Заключение ......Page 466
Решения задач из главы 1 ......Page 468
Решения задач из главы 2 ......Page 470
Решения задач из главы 3 ......Page 477
Решения задач из главы 4 ......Page 480
Решения задач из главы 5 ......Page 486
Решения задач из главы 6 ......Page 491
Функциональные языки программирования ......Page 499
Русские Интернет-ресурсы по функциональному программированию ......Page 505
Иностранные Интернет-ресурсы по функциональному программированию ......Page 506
Интегрированная среда разработки HUGS 98 ......Page 509
Компилятор GHC ......Page 513
Компилятор NHC ......Page 526
Компилятор компиляторов Happy ......Page 531
Функции ......Page 533
abs ......Page 538
and ......Page 539
approxRational ......Page 540
break ......Page 541
concat ......Page 542
curry ......Page 543
div ......Page 544
doubleToRational ......Page 545
either ......Page 546
flip ......Page 547
foldl ......Page 548
foldrl ......Page 549
fst ......Page 550
getLine ......Page 551
interact ......Page 552
isAlpha ......Page 553
isDigit ......Page 554
isPrint ......Page 555
last ......Page 556
lexmatch ......Page 559
lex ......Page 557
lexLitChar ......Page 558
lookup ......Page 560
mapM- ......Page 561
min ......Page 562
null ......Page 563
numericEnumPromThen ......Page 564
or ......Page 565
putChar ......Page 566
protectEsc ......Page 567
rationalToRealFloat ......Page 568
readHex ......Page 569
readFloat ......Page 570
readLitChar ......Page 571
readLn ......Page 572
readSigned ......Page 573
reduce ......Page 574
round ......Page 575
scanrl ......Page 576
show ......Page 577
showLitChar ......Page 578
shows ......Page 579
signumReal ......Page 580
span ......Page 581
sum ......Page 582
tan ......Page 583
truncate ......Page 584
until ......Page 585
userError ......Page 586
zip3 ......Page 587
Описание некоторых операторов языка Haskell ......Page 588
Приложение D. Краткий словарь терминов из области функционального программирования ......Page 591
Общая литература по функциональному программированию ......Page 601
Книги, руководства и статьи по языку Haskell ......Page 603
Комбинаторная логика и А-исчисление ......Page 604
Математическая лингвистика и теория построения трансляторов ......Page 605
Искусственный интеллект ......Page 606