Проверка типов с контекстом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Ограничение мономорфизма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Рекурсивные типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4
4 Декларативный и композиционный стиль
53
4.1 Локальные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
where-выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
let-выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Сопоставление с образцом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
case-выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Условные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Охранные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
if-выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4 Определение функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Уравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Безымянные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 Какой стиль лучше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.7 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5 Функции высшего порядка
66
5.1 Обобщённые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Функция тождества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Константная функция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Функция композиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Аналогия с числами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Функция перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Функция on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Функция применения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 Приоритет инфиксных операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Приоритет функции композиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Приоритет функции применения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Функциональный калькулятор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 Функции, возвращающие несколько значений . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.5 Комбинатор неподвижной точки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.6 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Основные функции высшего порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Приоритет инфиксных операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.7 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6 Функторы и монады: теория
80
6.1 Композиция функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Класс Category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Специальные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Взаимодействие с внешним миром . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Три композиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Обобщённая формулировка категории Клейсли . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 Примеры специальных функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Частично определённые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Многозначные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3 Применение функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Применение функций многих переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Несколько полезных функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4 Функторы и монады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Функторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Аппликативные функторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Монады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Свойства классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Полное определение классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Исторические замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.5 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.6 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5
7 Функторы и монады: примеры
99
7.1 Случайные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2 Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102