Читаем Учебник по Haskell онлайн бесплатно
Учебник по Haskell
Антон Холомьёв
Книга зарегистрирована под лицензией Creative Commons Attribution-NonCommercial-NoDerivs
3.0 Generic license (CC BY-NC-ND 3.0), 2012 год. Вы можете свободно распространять и копировать
эту книгу при условии указания автора. Вы не можете использовать эту книгу в коммерческих
целях, вы не можете изменять содержание книги при копировании или создавать производные
работы на основе содержания этой книги, конечно если это не программный код :) Любое из
указанных ограничений может быть смягчено по договорённости с правообладателем.
Обратная связь: anton.kholomiov@gmail.com
Оглавление
Предисловие
5
1 Основы
7
2 Первая программа
19
3 Типы
34
4 Декларативный и композиционный стиль
53
5 Функции высшего порядка
66
6 Функторы и монады: теория
80
7 Функторы и монады: примеры
99
8 IO
120
9 Редукция выражений
136
10 Реализация Haskell в GHC
149
11 Ленивые чудеса
175
12 Структурная рекурсия
186
13 Поиграем
195
14 Лямбда-исчисление
210
15 Теория категорий
221
16 Категориальные типы
234
17 Дополнительные возможности
245
18 Средства разработки
259
19 Ориентируемся по карте
269
20 Императивное программирование
282
21 Музыкальный пример
299
Приложения
312
3
Содержание
Предисловие
5
Структура книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1 Основы
7
1.1 Общая картина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2 Типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3 Значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Классы типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Контекст классов типов. Суперклассы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Экземпляры классов типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Ядро Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Двумерный синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.8 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.9 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Первая программа
19
2.1 Интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 У-вей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Логические значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Класс Show. Строки и символы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Строки и символы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Пример: Отображение дат и времени . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Автоматический вывод экземпляров классов типов . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Арифметика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Класс Eq. Сравнение на равенство . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Класс Num. Сложение и умножение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Класс Fractional. Деление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Стандартные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Документация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.8 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.9 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Типы
34
3.1 Структура алгебраических типов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Структура констант . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Несколько слов о теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Строчная запись деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Структура функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Композиция и частичное применение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Декомпозиция и сопоставление с образцом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Проверка типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Проверка типов с контекстом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
7.3 Отложенное вычисление выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Тип Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.4 Накопление результата . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Тип-обёртка newtype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Накопление чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Накопление логических значений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Накопление списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.5 Монада изменяемых значений ST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Тип ST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Императивные циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.6 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.7 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8 IO
120
8.1 Чистота и побочные эффекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.2 Монада IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.3 Как пишутся программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.4 Типичные задачи IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Вывод на экран . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Ввод пользователя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Чтение и запись файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Ленивое и энергичное чтение файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Аргументы программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Вызов других программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
