10.8 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.9 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
11 Ленивые чудеса
175
11.1 Численные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Дифференцирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Интегрирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
11.2 Степенные ряды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Арифметика рядов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Производная и интеграл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Элементарные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
11.3 Водосборы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
11.4 Ленивее некуда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
11.5 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.6 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
12 Структурная рекурсия
186
12.1 Свёртка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Логические значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Натуральные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Maybe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
12.2 Развёртка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
Натуральные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
12.3 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
12.4 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
13 Поиграем
195
13.1 Стратегия написания программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Описание задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Набросок решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Каркас. Типы и классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Ленивое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
13.2 Пятнашки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Цикл игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Приведём код в порядок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Формат запросов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Последние штрихи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Правила игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
13.3 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7
14 Лямбда-исчисление
210
14.1 Лямбда исчисление без типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Составление термов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Редукция. Вычисление термов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Рекурсия. Комбинатор неподвижной точки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Кодирование структур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Конструктивная математика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Расширение лямбда исчисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
14.2 Комбинаторная логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216