Оглавление.....................................................................................................5
Предисловие .................................................................................................15
Благодарности ............................................................................................19
О книге .........................................................................................................20
Об авторе ....................................................................................................28
Об иллюстрации на обложке.......................................................................29
1 Создание безопасных программ ..............................................31
1.1 Программные ловушки................................................................33
1.1.1 Безопасная обработка эффектов..........................................35
1.1.2 Увеличение безопасности программ за счет ссылочной
прозрачности.........................................................................36
1.2 Выгоды безопасного программирования................................37
1.2.1 Использование подстановочной модели в рассуждениях
о программе............................................................................39
1.2.2 Применение принципов соблюдения безопасности
на простом примере ..............................................................40
1.2.3 Максимальное использование абстракций............................44
Итоги..........................................................................................................45
2 Функциональное программирование на Kotlin:
обзор.........................................................................................................46
2.1 Поля и переменные в Kotlin........................................................47
2.1.1 Тип можно опустить для простоты.....................................47
2.1.2 Изменяемые поля ...................................................................47
2.1.3 Отложенная инициализация .................................................48
2.2 Классы и интерфейсы в Kotlin....................................................49
2.2.1 Еще большее сокращение кода ...............................................51
2.2.2 Реализация интерфейса или расширение класса ..................51
Содержание 7
2.2.3 Создание экземпляра класса ..................................................52
2.2.4 Перегрузка конструкторов....................................................52
2.2.5 Создание методов equals и hashCode.....................................53
2.2.6 Деструктуризация объектов данных....................................55
2.2.7 Реализация статических членов в Kotlin...............................55
2.2.8 Синглтоны .............................................................................56
2.2.9 Предотвращение создания экземпляров служебных
классов....................................................................................56
2.3 В Kotlin нет элементарных типов ..............................................57
2.4 Два типа коллекций в Kotlin .......................................................57
2.5 Пакеты в Kotlin...............................................................................59
2.6 Видимость в Kotlin .......................................................................60
2.7 Функции в Kotlin............................................................................61
2.7.1 Объявление функций...............................................................61
2.7.2 Локальные функции ................................................................62
2.7.3 Переопределение функций......................................................63
2.7.4 Функции-расширения.............................................................63
2.7.5 Лямбда-выражения ................................................................64
2.8 Пустое значение null в Kotlin......................................................66
2.8.1 Приемы работы с типами, поддерживающими null .............66
2.8.2 Оператор Элвис и значение по умолчанию............................67
2.9 Поток выполнения программы и управляющие
структуры........................................................................................67
2.9.1 Условная конструкция ...........................................................68
2.9.2 Использование конструкций с несколькими условиями.........69
2.9.3 Циклы .....................................................................................70
2.9.4 Какие проблемы может вызывать поддержка
вариантности?......................................................................76
2.9.5 Когда использовать объявления ковариантности
и контрвариантности ..........................................................77
2.9.6 Объявление вариантности в точке определения
и точке использования...........................................................78
Итоги..........................................................................................................79
3 Программирование с функциями...........................................81
3.1 Что такое функция? ......................................................................82
3.1.1 Отношения между двумя областями функций .....................83
3.1.2 Обратные функции в Kotlin ...................................................84
3.1.3 Частичные функции ...............................................................85
3.1.4 Композиция функций..............................................................86
3.1.5 Функции нескольких аргументов ...........................................86
3.1.6 Каррирование функций ..........................................................87
3.1.7 Частично-примененные функции ..........................................87
3.1.8 Функции не имеют эффектов................................................88
3.2 Функции в Kotlin............................................................................89
8 Содержание
3.2.1 Функции как данные...............................................................89
3.2.2 Данные как функции...............................................................89
3.2.3 Конструкторы объектов как функции ..................................89
3.2.4 Использование функций fun в Kotlin.......................................90
3.2.5 Объектная и функциональная нотация ................................93
3.2.6 Использование функций как значений ...................................94
3.2.7 Ссылки на функции.................................................................96
3.2.8 Композиция функций fun........................................................97
3.2.9 Повторное использование функций .......................................98
3.3 Дополнительные особенности функций..................................99
3.3.1 Функции с несколькими аргументами? .................................99
3.3.2 Применение каррированных функций..................................100
3.3.3 Реализация функций высшего порядка.................................100
3.3.4 Полиморфные функции высшего порядка ............................102
3.3.5 Анонимные функции.............................................................104
3.3.6 Локальные функции ..............................................................106
3.3.7 Замыкания............................................................................106
3.3.8 Частичное применение функций и автоматическое
каррирование .......................................................................107
3.3.9 Перестановка аргументов частично примененных
функций ................................................................................112
Итоги........................................................................................................119
4 Рекурсия, сорекурсия и мемоизация ...................................120
4.1 Рекурсия и сорекурсия...............................................................121
4.1.1 Реализация сорекурсии.........................................................121
4.1.2 Реализация рекурсии ............................................................123
4.1.3 Различия между рекурсивными и сорекурсивными
функциями............................................................................124
4.1.4 Выбор между рекурсией и сорекурсией.................................125
4.2 Удаление хвостового вызова ....................................................127
4.2.1 Использование механизма удаления хвостового вызова .....128
4.2.2 Преобразование циклов в хвостовую рекурсию...................128
4.2.3 Рекурсивные функции-значения...........................................132
4.3 Рекурсивные функции и списки..............................................135
4.3.1 Дважды рекурсивные функции .............................................137
4.3.2 Абстракция рекурсии в списках...........................................140
4.3.3 Обращение списка ................................................................143
4.3.4 Сорекурсивные списки ..........................................................145
4.3.5 Опасность строгости..........................................................149
4.4 Мемоизация .................................................................................149
4.4.1 Мемоизация в программировании на основе циклов...........149
4.4.2 Мемоизация рекурсивных функций ......................................150
4.4.3 Неявная мемоизация ............................................................152
4.4.4 Автоматическая мемоизация .............................................154
4.4.5 Мемоизация функций нескольких аргументов ....................157
Содержание 9
4.5 Являются ли мемоизованные функции чистыми?..............159
Итоги........................................................................................................159
5 Обработка данных с использованием списков .............161
5.1 Классификация коллекций данных ........................................162
5.2 Разные типы списков .................................................................162
5.3 Производительность списков...................................................164
5.3.1 Время в обмен на объем памяти и сложность ....................165
5.3.2 Отказ от изменения на месте............................................165
5.4 Какие виды списков доступны в Kotlin? ................................167
5.4.1 Использование постоянных структур данных....................168
5.4.2 Реализация неизменяемого, постоянного,
односвязного списка ........................................................................168
5.5 Совместное использование данных в операциях
со списками ..................................................................................172
5.6 Дополнительные операции со списками...............................174
5.6.1 Преимущества объектной нотации....................................175
5.6.2 Объединение списков ............................................................178
5.6.3 Удаление элементов с конца списка ....................................180
5.6.4 Использование рекурсии для свертки списков
с помощью функций высшего порядка..................................181
5.6.5 Вариантность .....................................................................182
5.6.6 Безопасная рекурсивная версия foldRight.............................191
5.6.7 Отображение и фильтрация списков..................................193
Итоги........................................................................................................196
6 Необязательные данные ............................................................197
6.1 Проблемы с пустым указателем ..............................................198
6.2 Как пустые ссылки обрабатываются в Kotlin ........................201
6.3 Альтернативы пустым ссылкам...............................................202
6.4 Тип Option.....................................................................................205
6.4.1 Извлечение значения из Option ............................................207
6.4.2 Применение функций к необязательным значениям...........209
6.4.3 Композиция функций с типом Option..................................210
6.4.4 Примеры использования Option ...........................................212
6.4.5 Другие способы комбинирования типа Options...................215
6.4.6 Комбинирование List и Option..............................................218
6.4.7 Когда и как использовать тип Option .................................220
Итоги........................................................................................................221
7 Обработка ошибок и исключений........................................222
7.1 Проблемы с отсутствующими данными................................223
7.2 Тип Either......................................................................................224
7.3 Тип Result......................................................................................227
10 Содержание
7.4 Приемы использования типа Result .......................................230
7.5 Дополнительные способы использования Result................236
7.5.1 Применение предикатов......................................................236
7.6 Преобразование ошибок ...........................................................238
7.7 Дополнительные фабричные функции..................................239
7.8 Применение эффектов...............................................................240
7.9 Дополнительные способы комбинирования с типом
Result..............................................................................................243
Итоги........................................................................................................247
8 Дополнительные операции со списками..........................248
8.1 Проблемы функции length........................................................249
8.2 Проблема производительности ...............................................249
8.3 Преимущества мемоизации .....................................................250
8.3.1 Недостатки мемоизации.....................................................250
8.3.2 Оценка увеличения производительности............................252
8.4 Комбинирование List и Result..................................................253
8.4.1 Списки, возвращающие Result..............................................253
8.4.2 Преобразование List в Result..........................255
8.5 Абстракции операций со списками ........................................257
8.5.1 Упаковка и распаковка списков............................................258
8.5.2 Доступ к элементам по индексам.......................................261
8.5.3 Разбиение списков ................................................................266
8.5.4 Поиск подсписков .................................................................270
8.5.5 Разные функции для работы со списками............................271
8.6 Автоматическое распараллеливание операций
со списками ..................................................................................276
8.6.1 Не все вычисления могут выполняться параллельно ..........276
8.6.2 Деление списка на подсписки ...............................................276
8.6.3 Параллельная обработка подсписков..................................278
Итоги........................................................................................................280
9 Ленивые вычисления.....................................................................282
9.1 Строгий и ленивый подходы ....................................................283
9.2 Строгие вычисления в Kotlin ....................................................284
9.3 Ленивые вычисления в Kotlin...................................................286
9.4 Реализация ленивых вычислений...........................................288
9.4.1 Комбинирование ленивых значений .....................................290
9.4.2 Преобразование обычных функций в ленивые......................294
9.4.3 Отображение ленивых значений .........................................296
9.4.4 Комбинирование типов Lazy и List ......................................298
9.4.5 Обработка исключений........................................................299
9.5 Другие способы комбинирования ленивых
вычислений ..................................................................................302
Содержание 11
9.5.1 Ленивое применение эффектов ...........................................302
9.5.2 Вычисления, невозможные без ленивых значений................304
9.5.3 Создание ленивого списка ....................................................305
9.6 Работа с потоками.......................................................................308
9.6.1 Свертка потоков .................................................................314
9.6.2 Трассировка вычислений и применение функций.................317
9.6.3 Использование потоков для решения конкретных задач....319
Итоги........................................................................................................322
10 Обработка данных с использованием деревьев ...........323
10.1 Бинарное дерево..........................................................................324
10.2 Сбалансированные и несбалансированные деревья ..........325
10.3 Размер, высота и глубина дерева.............................................325
10.4 Пустые деревья и рекурсивное определение........................326
10.5 Лиственные деревья ...................................................................327
10.6 Упорядоченные бинарные деревья, или бинарные
деревья поиска.............................................................................327
10.7 Порядок вставки и структура дерева......................................329
10.8 Рекурсивный и нерекурсивный обход дерева ......................330
10.8.1 Рекурсивный обход дерева ....................................................330
10.8.2 Нерекурсивный обход дерева................................................332
10.9 Реализация бинарного дерева поиска....................................333
10.9.1 Деревья и вариантность .....................................................334
10.9.2 Об абстрактных функциях в классе Tree ............................336
10.9.3 Перегрузка операторов........................................................336
10.9.4 Рекурсия в деревьях ..............................................................336
10.9.5 Удаление элементов из дерева.............................................340
10.9.6 Слияние произвольных деревьев...........................................341
10.10 О свертке деревьев......................................................................347
10.10.1 Свертка с двумя функциями ................................................348
10.10.2 Свертка с одной функцией ...................................................350
10.10.3 Выбор реализации свертки..................................................350
10.11 О преобразовании элементов деревьев.................................353
10.12 О балансировке деревьев ..........................................................354
10.12.1 Вращение деревьев ...............................................................354
10.12.2 Алгоритм Дея/Стоута/Уоррен ...........................................357
10.12.3 Самобалансирующиеся деревья............................................361
Итоги........................................................................................................362
11 Решение задач с использованием
усовершенствованных деревьев.............................................363
11.1 Улучшение производительности и безопасности
деревьев добавлением самобалансировки......................................364
11.1.1 Структура красно-черных деревьев....................................365
12 Содержание
11.1.2 Добавление элемента в красно-черное дерево ....................367
11.1.3 Удаление элементов из красно-черного дерева...................373
11.2 Практические примеры использования красно-черных
деревьев: ассоциативные массивы.........................................373
11.2.1 Реализация Map....................................................................373
11.2.2 Расширение ассоциативных массивов.................................376
11.2.3 Использование ключей, не поддерживающих сравнение......377
11.3 Реализация функциональной приоритетной очереди.......380
11.3.1 Протоколы доступа к приоритетной очереди ...................380
11.3.2 Варианты использования приоритетных очередей............380
11.3.3 Требования к реализации .....................................................381
11.3.4 Левосторонняя куча.............................................................381
11.3.5 Реализация левосторонней кучи..........................................382
11.3.6 Реализация интерфейса, характерного для очередей .........385
11.4 Элементы и сортированные списки .......................................386
11.5 Приоритетная очередь для несопоставимых элементов ...388
Итоги........................................................................................................391
12 Функциональный ввод/вывод ..................................................392
12.1. Что означает «эффект внутри контекста»? ............................393
12.1.1 Обработка эффектов..........................................................394
12.1.2 Реализация эффектов..........................................................394
12.2 Чтение данных.............................................................................397
12.2.1 Чтение данных с клавиатуры..............................................398
12.2.2 Чтение из файла ..................................................................402
12.3 Тестирование программ с вводом...........................................404
12.4 Полностью функциональный ввод/вывод.............................405
12.4.1 Как сделать ввод/вывод полностью функциональным........405
12.4.2 Реализация чисто функционального ввода/вывода .............406
12.4.3 Комбинирование ввода/вывода ............................................407
12.4.4 Обработка ввода с IO ..........................................................409
12.4.5 Расширение типа IO ............................................................411
12.4.6 Добавление в IO защиты от переполнения стека ..............414
Итоги........................................................................................................419
13 Общее изменяемое состояние и акторы.........................420
13.1 Модель акторов............................................................................422
13.1.1 Асинхронный обмен сообщениями .......................................422
13.1.2 Параллельное выполнение....................................................422
13.1.3 Управление изменением состояния актора........................423
13.2 Реализация инфраструктуры акторов....................................424
13.2.1 Обзор ограничений ...............................................................425
13.2.2 Интерфейсы инфраструктуры акторов ............................425
13.3 Реализация AbstractActor ..........................................................427
Содержание 13
13.4 Включение акторов в работу ....................................................428
13.4.1 Реализация примера игры в пинг-понг.................................429
13.4.2 Параллельное выполнение вычислений ................................431
13.4.3 Переупорядочение результатов ..........................................437
13.4.4 Оптимизация производительности ...................................440
Итоги........................................................................................................447
14 Решение типичных проблем функциональным
способом...............................................................................................448
14.1 Утверждения и проверка данных............................................449
14.2 Повторный вызов функций и эффектов................................453
14.3 Чтение свойств из файла...........................................................456
14.3.1 Загрузка файла со свойствами ............................................457
14.3.2 Чтение свойств как строк ..................................................458
14.3.3 Вывод более информативных сообщений об ошибках .........459
14.3.4 Чтение свойств как списков ................................................462
14.3.5 Чтение значений перечислений ...........................................463
14.3.6 Чтение свойств произвольных типов .................................464
14.4 Преобразование императивной программы:
чтение файлов XML ....................................................................467
14.4.1 Шаг 1: императивное решение ............................................468
14.4.2 Шаг 2: превращаем императивную программу
в функциональную ................................................................470
14.4.3 Шаг 3: делаем программу еще более функциональной ........473
14.4.4 Шаг 4: исправление проблемы с аргументами одного
типа .....................................................................................477
14.4.5 Шаг 5: передача функции обработки элемента
в параметре .........................................................................478
14.4.6 Шаг 6: обработка ошибок в именах элементов ..................479
14.4.7 Шаг 7: дополнительные улучшения в прежде
императивном коде .............................................................481
Итоги........................................................................................................483
Приложение A. Cмешивание кода на Kotlin и Java................484
Создание и управление смешанными проектами.........................485
Создание простого проекта в GRADLE ..........................................485
Импортирование Gradle-проекта в IntelliJ....................................487
Добавление зависимостей в проект...............................................488
Создание проектов с несколькими модулями .................................488
Добавление зависимостей в проект с несколькими модулями.......489
Вызов Java-методов из Kotlin..............................................................490
Использование примитивов Java ....................................................490
Использование числовых типов-объектов Java .............................491
Быстрый отказ со значениями null ................................................492
Использование строковых типов Kotlin и Java ...............................492
14 Содержание
Преобразование других типов.........................................................493
Вызов Java-методов с переменным числом параметров ...............494
Управление поддержкой null в Java .................................................494
Доступ к свойствам в JAVA с зарезервированными именами........497
Вызов контролируемых исключений ...............................................497
SAM-интерфейсы ..................................................................................498
Вызов Kotlin-функций из Java ............................................................498
Преобразование свойств Kotlin.......................................................498
Использование общедоступных полей Kotlin...................................499
Статические поля...........................................................................499
Вызов функций Kotlin из методов Java............................................500
Преобразование типов Kotlin в типы Java .....................................503
Типы функций ..................................................................................504
Характерные проблемы смешанных проектов на Kotlin/Java.....504
Итоги........................................................................................................505
Приложение В. Тестирование на основе свойств.................507
Зачем нужно тестирование на основе свойств?.............................508
Интерфейс ......................................................................................509
Тест.................................................................................................509
Что такое тестирование на основе свойств? ...................................510
Абстракция и тестирование на основе свойств..............................511
Зависимости для модульного тестирования на основе
свойств.....................................................................................................513
Разработка тестов на основе свойств ...............................................514
Создание своих генераторов ..............................................................517
Использование своих генераторов ..................................................518
Упрощение кода дальнейшим абстрагированием...........................522
Итоги........................................................................................................524
Предметный указатель ............................................................................526