Учебник по 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
Случайные значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Исключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Потоки текстовых данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.5 Форточка в мир побочных эффектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Отладка программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.6 Композиция монад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.7 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.8 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9 Редукция выражений
136
9.1 Стратегии вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Преимущества и недостатки стратегий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.2 Вычисление по необходимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.3 Аннотации строгости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Принуждение к СЗНФ с помощью seq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Функции с хвостовой рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Тонкости применения seq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Энергичные образцы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Энергичные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.4 Пример ленивых вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.5 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.6 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6
10 Реализация Haskell в GHC
149
10.1 Этапы компиляции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.2 Язык STG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
10.3 Вычисление STG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Куча . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Стек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Правила общие для обеих стратегий вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Правила для стратегии вставка-вход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Правила для стратегии вычисление-применение . . . . . . . . . . . . . . . . . . . . . . . . . . 156
10.4 Представление значений в памяти. Оценка занимаемой памяти . . . . . . . . . . . . . . . . . 156
10.5 Управление памятью. Сборщик мусора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
10.6 Статистика выполнения программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Статистика вычислителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Профилирование функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Поиск источников внезапной остановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.7 Оптимизация программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Флаги оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
Прагма INLINE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
Прагма RULES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Прагма UNPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
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
Связь с лямбда-исчислением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Немного истории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
14.3 Лямбда-исчисление с типами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
14.4 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
14.5 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
15 Теория категорий
221
15.1 Категория . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
15.2 Функтор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
15.3 Естественное преобразование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
15.4 Монады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Категория Клейсли . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
15.5 Дуальность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
15.6 Начальный и конечный объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Начальный объект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Конечный объект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
15.7 Сумма и произведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
15.8 Экспонента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
15.9 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
15.10Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
16 Категориальные типы
234
16.1 Программирование в стиле оригами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
16.2 Индуктивные и коиндуктивные типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Существование начальных и конечных объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 239
16.3 Гиломорфизм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
16.4 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
16.5 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
17 Дополнительные возможности
245
17.1 Пуд сахара . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Сахар для списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Сахар для монад, do-нотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
17.2 Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Обобщённые алгебраические типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
Семейства типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
Классы с несколькими типами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Экземпляры классов для синонимов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Функциональные зависимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Ограничение мономорфизма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
Полиморфизм высших порядков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
Лексически связанные типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
И другие удобства и украшения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
17.3 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
17.4 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
8
18 Средства разработки
259
18.1 Пакеты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
Создание пакетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
Создаём библиотеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Создаём исполняемые программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Установка пакета . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Удаление библиотеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Репозиторий пакетов Hackage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Дополнительные атрибуты пакета . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Установка библиотек для профилирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
18.2 Создание документации с помощью Haddock . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Комментарии к определениям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Комментарии к модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
Структура страницы документации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
Разметка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
18.3 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
18.4 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
19 Ориентируемся по карте
269
19.1 Алгоритм эвристического поиска А* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Поиск маршрутов в метро . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
19.2 Тестирование с помощью QuickCheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Формирование тестовой выборки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Классификация тестовых случаев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
19.3 Оценка быстродействия с помощью criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Основные типы criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
19.4 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
19.5 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
20 Императивное программирование
282
20.1 Основные библиотеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Изменяемые значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Chipmunk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
20.2 Боремся с IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
20.3 Определяемся с типами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
20.4 Структура проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
20.5 Детализируем функции обновления состояния игры . . . . . . . . . . . . . . . . . . . . . . . . 297
20.6 Детализируем дальше . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
20.7 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
20.8 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
21 Музыкальный пример
299
21.1 Музыкальная нотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Нотная запись в европейской традиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Протокол midi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
21.2 Музыкальная запись в виде событий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Преобразование событий во времени . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Композиция треков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Экземпляры стандартных классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
21.3 Ноты в midi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Синонимы для нот . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
21.4 Перевод в midi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
21.5 Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
21.6 Эффективное представление музыкальной нотации . . . . . . . . . . . . . . . . . . . . . . . . 310
21.7 Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
21.8 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
9
Приложения
312
Начало работы с Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Тематический сборник . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
И все-все-все . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Обзор Hackage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Стандартные библиотеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Эффективные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Разработка программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
И все-все-все . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Места . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Университеты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Компании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
10
Предисловие
История языка Haskell начинается в 1987 году. В 1980е годы наблюдался всплеск интереса к ленивой
стратегии вычислений. Один за другим появлялись новые функциональные языки программирования. Про-
граммисты задумались и решили, объединив усилия, найти общий язык. Так появился Haskell. Он был назван
в честь одного из основателей комбинаторной логики Хаскеля Кэрри (Haskell Curry).
Новый язык должен был стать свободным языком, пригодным для исследовательской деятельности и
решения практических задач. Свободные языки основаны на стандарте, который формулируется комите-
том разработчиков. Дальше любой желающий может заняться реализацией стандарта, написать компилятор
языка. Первая версия стандарта была опубликована 1 апреля 1990 года. Haskell продолжает развиваться
и сегодня, было зафиксировано два стандарта: 1998 и 2010 года. Это стабильные версии. Но кроме них в
Haskell включается множество расширений, проходит обкат интересных идей. Сегодня Haskell переживает
бурный рост, к сожалению, эпицентры далеки от России, это Англия, Нидерланды, Америка и Австралия. Ин-
терес к Haskell вызван популярностью многопроцессорных технологий. Модель вычислений Haskell хорошо
подходит для распараллеливания. И сейчас проводятся исследования в этой области.
Haskell очень красивый и лаконичный язык. Он придётся по душе математикам, программистам, склон-
ным к поиску элегантных решений. В арсенале программиста: строгая типизация с выводом типов, функции
высшего порядка, алгебраические типы данных, алгебраические структуры. Если пока всё это звучит как
набор слов, ничего страшного, вы узнаете что это по ходу чтения книги.
Структура книги
Haskell славится высоким порогом вхождения. Он считается трудным языком для начинающих. Во многом
это связано с тем, что начинающие уже имеют приличный опыт программирования на императивных языках.
И при первом знакомстве оказывается, что этот опыт ничем не может им помочь. Они не могут найти в Haskell
аналогов привычных синтаксических конструкций и приёмов программирования. Haskell сильно отличается
от распространённых языков программирования. Но если вы совсем-совсем начинающий, скорее всего в этом
плане вам будет гораздо проще. Если вы всё же не начинающий, попробуйте подойти к материалу этой книги
с открытым сердцем. Не ищите в Haskell элементы вашего любимого языка и, возможно, таким языком станет
Haskell.
Ещё одна трудность связана с тем, что многие понятия тесно переплетены, Haskell не так просто разбить
на маленькие части и изучать их от простого к сложному, уже в самых простейших элементах кроются черты
новых и непривычных идей. Но, я надеюсь, что мы сможем преодолеть и этот барьер, мы не будем изучать
Haskell по кусочкам, а окунёмся в него с головой, уже в первой главе мы пробежимся по всему языку и далее
будем углубляться в отдельные моменты.
В книге много примеров. Haskell оснащён интерпретатором. Интерпретатор (также называемый REPL, от
англ. read-eval-print loop) позволяет писать программы в диалоговом режиме. Мы набираем выражение языка
и сразу видим ответ – вычисленное значение. Интерпретатор поможет нам разобраться во многих тонкостях
языка. Мы будем обращаться к нему очень часто.
Книгу можно разбить на несколько частей:
• Основы языка (1-13). Из первых тринадцати глав вы узнаете, что такое Haskell и чем он хорош.
• Теоретическая часть (14-16). Haskell питается соками математики, многие красивые научные идеи не
только находят в нём воплощение, но и являются фундаментом языка. Из этих глав вы узнаете немного
теории, которая служила источником вдохновения разработчиков Haskell.
• Разработка на Haskell (10,17-20). В этих главах мы познакомимся с расширениями языка (17), мы узна-
ем как писать библиотеки и документацию (18), проводить тестирование и оценивать быстродействие
программ (19), также мы потренируемся в написании императивного кода на Haskell (20). Из главы 10
мы узнаем как работает GHC, основной компилятор для Haskell.
Предисловие | 11
• Примеры (13, 21). В этих главах мы посмотрим на несколько примеров применения Haskell. В глваве
13 мы напишем программу для игры в пятнашки, а в главе 21 – midi-секвенсор и немного музыки.
Рекомендую сначала изучить основы языка, а затем обращаться к остальным частям в любом порядке.
Основные понятия
Haskell – чисто функциональный, типизированный язык программирования. Я буду очень часто говорить
слова функция, типы, значения, типы, функция, функция, типы~– буквально постоянно. Перед тем как мы
окунёмся с головой в программный код, я бы хотел словами пояснить, что всё это значит.
Мы собираемся изучить новый язык, хоть и искусственный, но всё же язык. Языки служат описанию яв-
лений, словами мы можем зафиксировать мысли и чувства и передать их другому. Предложение языка опи-
сывает что-то. У нас будут два разных вида описаний. Одни говорят о чём-то конкретном, их мы будем
называть значениями, а другие говорят о самих описаниях. Например это слова “числа”, “цвета” или “люди”.
Есть конкретное число: один два или три, а есть все числа. Такие описания мы будем называть типами. Типы
описывают множество значений. Функции описывают одни значения через другие. Это такие шаблоны описа-
ний. Типичный пример функции, это “вычисление площади треугольника”. Функция как бы говорит: если ты
мне покажешь треугольник, то я тебе скажу его площадь (число). Функция “вычисление площади треуголь-
ника” связывает два типа между собой: тип всех треугольников и тип чисел (значение площади). Могут быть
и не математические функции. Например функция “цвет глаз” говорит нам: если ты покажешь мне челове-
ка, то я скажу какого цвета у него глаза. Эта функция связывает тип “люди” и тип “цвет”. При этом связь
имеет направление. Функция сначала спрашивает у нас, чего ей не хватает, а потом говорит ответ. Ответ
называют значением функции (или выходом функции), а то чего ей не хватает аргументами функции (или
входами). Математики говорят, что эта функция отображает значения типа “люди” в значения типа “цвет”.
В Haskell функции тоже являются значениями. Функция может принимать в качестве аргумента функцию и
возвращать функцию.
Функции бывают чистыми и с побочными эффектами. Чистые функции – это правдивые функции. Их основ-
ная особенность в том, что для одинаковых ответов на их вопросы, они скажут одинаковые ответы. Функции
с побочными эффектами так не делают, например если мы спросим у такой функции какого цвета глаза у
Коли? В один день она может сказать голубые, а в другой зелёные. В Haskell таким функциям не доверяют и
огораживают их от чистых функций, но я увлёкся, обо всём об этом вы узнаете из этой книги.
Благодарности
Я бы хотел поблагодарить родителей за терпение и поддержку, сообщество Haskell, всех тех людей, у
которых я мог свободно учится языку Haskell. Когда я только начинал мне очень помогли книга Мирана
Липовача (Miran Lipovaca) Learn You A Haskell for a Great Good и книга Хал Дама (Hal Daume III) Yet another
Haskell Tutorial. Спасибо Дмитрию Астапову, Дугласу Мак Илрою (Douglas McIlroy) и Джону Хьюзу (John
Huges) за великодушное согласие на использование примеров из их статей. Большое спасибо Кате Столяро-
вой за идею написания книги. Спасибо Александру Мозгунову за расширение моего кругозора в Haskell и не
только. Спасибо Оксане Станевич за редактирование и правки первой главы.
Хочется поблагодарить тех, кто присылал правки, после появления первой версии книги. Огромное спа-
сибо Андрею Мельникову. Его поддержка и замечания значительно углубили материал книги, вывели её
на новый уровень. Книга сильно изменилась после комментариев Владимира Шабанова (появились части о
сборщике мусора). Многие правки внесли Сергей Дмитриев и Кирилл Заборский. Также хотелось бы отме-
тить тех, кто вносил правки через github и ru_declarative: lionet, d_ao, odrdo, ul.
Технические благодарности: команде GHC, за компилятор Haskell, Джону Мак Фарлану (John MacFarlane)
за систему вёрстки pandoc, команде TexLive, авторам XeLatex, автору пакета hscolour Малькольму Уолласу
(Malcolm Wallace) за подсветку синтаксиса, авторам пакетов c Hackage: diagrams (Брент Йорги (Brent Yorgey),
Райан Йэйтс (Ryan Yates)) QuickCheck (Коэн Клаессен (Koen Claessen), Бьорн Брингерт (Bjorn Bringert), Ник
Смолбоун (Nick Smallbone)), criterion (Брайан О’Салливан (Bryan O’Sullivan)), HCodecs (Джордж Гиоргадзе
(George Giorgidze)), fingertree (Росс Патерсон (Ross Paterson), Ральф Хинце (Ralf Hinze)), Hipmunk (Фелипе
Лесса (Felipe A. Lessa)), OpenGL (Джэйсон Даджит (Jason Dagit), Свен Пэнн (Sven Panne) и GLFW (Пол Лю
(Paul H. Liu), Марк Санет (Marc Sunet)).
12 | Предисловие
Глава 1
Основы
Есть мнение, что Haskell очень большой язык. Это и правда так. В Haskell много разных конструкций,
синтаксического сахара, которые делают код более наглядным. Также в Haskell много библиотек на раз-
ные случаи жизни. Однако, обману ли я ваши ожидания, сказав, что всё это имеет достаточно компактную
основу? Это и правда так, вам осталось лишь убедиться в наглядности и простоте Haskell. В этой главе мы
пробежимся по нему, охватив одним взглядом целиком весь язык. Несколько наглядных конструкций, немно-
го моих пояснений, и вы поймёте, что к чему. Если что-то сразу не станет ясно, или где-то я опущу какие-то
пояснения, будьте уверены – в следующих главах мы обязательно обратимся к этим моментам и обсудим их
подробнее.
1.1 Общая картина
Программы на Haskell бывают двух видов: это приложения (executable) и библиотеки (library). Приложе-
ния представляют собой исполняемые файлы, которые решают некоторую задачу, к примеру – это может
быть компилятор языка, сортировщик данных в директориях, календарь, или цитатник на каждый день, лю-
бая полезная утилита. Библиотеки тоже решают задачи, но решают их внутри самого языка. Они содержат
отдельные значения, функции, которые можно подключать к другой программе Haskell, и которыми можно
пользоваться.
Программа состоит из модулей (module). И здесь работает правило: один модуль – один файл. Имя модуля
совпадает с именем файла. Имя модуля начинается с большой буквы, тогда как файлы имеют расширение
. hs. Например FirstModule. hs. Посмотрим на типичный модуль в Haskell:
--------------------------------------
-- шапка
module Имя(определение1, определение2,..., определениеN) where
import Модуль1(... )
import Модуль2(... )
...
---------------------------------------
-- определения
определение1
определение2
...
Каждый модуль содержит набор определений. Относительно модуля определения делятся на экспорти-
руемые и внутренние. Экспортируемые определения могут быть использованы за пределами модуля, а внут-
ренние – только внутри модуля, и обычно они служат для выражения экспортируемых определений.
Модуль состоит из двух частей – шапки и определений.
Шапка В шапке после слова module объявляется имя модуля, за которым в скобках следует список экспорти-
руемых определений; после скобок стоит слово where. Затем идут импортируемые модули. С помощью
импорта модулей вы имеете возможность в данном модуле пользоваться определениями из другого
модуля.
Как после имени модуля, так и в директиве import скобки с определениями можно не писать,так как
в этом случае считается, что экспортируются/импортируются все определения.
| 13
Определения Эта часть содержит все определения модуля, при этом порядок следования определений не
имеет значения. То есть, не обязательно пользоваться в данной функции лишь теми значениями, что
были определены выше.
Модули взаимодействуют друг с другом с помощью экспортируемых определений. Один модуль может
сказать, что он хочет воспользоваться экспортируемыми определениями другого модуля, для этого он пишет
import Модуль(определения). Модуль – это айсберг, на вершине которого – те функции, ради которых он
создавался (экспортируемые), а под водой – все служебные детали реализации (внутренние).
Итак, программа состоит из модулей, модули состоят из определений. Но что такое определения?
В Haskell определения могут описывать четыре вида сущностей:
• Типы.
• Значения.
• Классы типов.
• Экземпляры классов типов.
Теперь давайте рассмотрим их подробнее.
1.2 Типы
Типы представляют собой каркас программы. Они кратко описывают все возможные значения. Это очень
удобно. Опытный программист на Haskell может понять смысл функции по её названию и типу. Это не очень
сложно. Например, мы видим:
not :: Bool -> Bool
Выражение v :: T означает, что значение v имеет тип T. Стрелка a -> b означает функцию, то есть из a мы
можем получить b. Итак, перед нами функция из Bool в Bool, под названием not. Мы можем предположить,
что это логическая операция “не”. Или, перед нами такое определение типа:
reverse :: [a] -> [a]
Мы видим функцию с именем reverse, которая принимает список [a] и возвращает список [a], и мы
можем догадаться, что эта функция переворачивает список, то есть мы получаем список, у которого элементы
идут в обратном порядке. Маленькая буква a в [a] является параметром типа, на место параметра может быть
поставлен любой тип. Она говорит о том, что список содержит элементы типа a. Например, такая функция
соглашается переворачивать только списки логических значений:
reverseBool :: [Bool] -> [Bool]
Программа представляет собой описание некоторого явления или процесса. Типы определяют основные
слова или термины и способы их комбинирования. А значения представляют собой комбинации базовых
слов. Но значения комбинируются не произвольным образом, а на основе определённых правил, которые
задаются типами.
Например, такое выражение определяет тип, в котором два базовых термина True или False
data Bool = True | False
Слово data ключевое, с него начинается любое определение нового типа. Символ | означает или. Наш
новый тип Bool является либо словом True, либо словом False. В этом типе есть только понятия, но нет
способов комбинирования, посмотрим на тип, в котором есть и то, и другое:
data [a] = [] | a : [a]
Это определение списка. Как мы уже поняли, a – это параметр. Список [a] может быть либо пустым
списком [], либо комбинацией a : [a]. В этой комбинации знак : объединяет элемент типа a и ещё один
список [a]. Это рекурсивное определение, они встречаются в Haskell очень часто. Если это пока кажется
непонятным, не пугайтесь, в следующих главах будет представлено много примеров с пояснениями.
Приведём ещё несколько примеров определений; ниже типы определяют базовые понятия для мира ка-
лендаря: то что стоит за – является комментарием и игнорируется при выполнении программы:
14 | Глава 1: Основы
-- Дата
data Date = Date Year Month Day
-- Год
data Year
= Year Int
-- Int это целые числа
-- Месяц
data Month
= January
| February
| March
| April
| May
| June
| July
| August
| September
| October
| November | December
data Day = Day Int
-- Неделя
data Week
= Monday
| Tuesday
| Wednesday
| Thursday
| Friday
| Saturday
| Sunday
-- Время
data Time = Time Hour Minute Second
data Hour
= Hour
Int
-- Час
data Minute = Minute Int
-- Минута
data Second = Second Int
-- Секунда
Одной из основных целей разработчиков Haskell была ясность. Они стремились создать язык, предложе-
ния которого будут простыми и понятными, близкий к языку спецификаций.
С символом | мы уже познакомились, он указывает на альтернативы, объединение пишется через пробел.
Так, фраза
data Time = Time Hour Minute Second
означает, что тип Time – это значение с меткой Time, которое состоит из значений типов “час”, “время” и
“секунда”, и больше ничего. Метку принято называть конструктором.
Фраза
data Year = Year Int
означает, что тип Year – это значение с конструктором Year, которое состоит из одного значения типа
Int. Конструктор обычно идёт первым, а за ним через пробел следуют другие типы. Конструктор может быть
и самостоятельным значением, как в случае True или January.
Типы делят выполнение программы на две стадии: компиляцию (compile-time) и вычисление (run-time). На
этапе компиляции происходит проверка типов. Программа, которая не прошла проверку типов, считается
бессмысленной и не вычисляется. Приложение, которое выполняет компиляцию, называют компилятором
(compiler), а то приложение, которое проводит вычисление, называют вычислителем (run-time system).
Типами мы определяем основные понятия в том явлении, которое мы хотим описать, а также осмыслен-
ные способы их комбинирования. Мы говорим, как из простейших терминов получаются составные. Если мы
попытаемся построить бессмысленное предложение, компилятор языка автоматически найдёт такое предло-
жение и сообщит нам об этом. Этот процесс заключается в проверке типов, к примеру если у нас есть функция
сложения чисел, и мы попытаемся передать в неё строку или список, компилятор заметит это и скажет нам
об этом перед тем как программа начнёт выполнятся. И важно то, что это произойдёт очень быстро. Если мы
случайно ошиблись в выражении, которое будет вычислено через час, нам не нужно ждать пока вычислитель
дойдёт до ошибки, мы узнаем об этом, не успев моргнуть, после запуска программы.
Итак, если мы попробуем составить время из месяцев и логических значений:
Time January True 23
компилятор предупредит нас об ошибке. Наверное, вы думаете, что приведенный пример надуман, ведь
кому захочется составлять время из логических значений? Но когда вы пишете программу, часто процесс
работы складывается так: вы думаете над одним, пишете другое, а также планируете вернуться к третьему.
И знание того, что есть надежный компилятор, который не пропустит глупых ошибок, освобождает руки, вы
можете не заботиться о таких пустяках, как правильное построение предложения.
Отметим, что такой подход с разделением вычисления на две стадии и проверкой типов называется
статической типизацией. Есть и другие языки, в них типы лишь подразумеваются и программа сразу начинает
Типы | 15
вычисляться, если есть какие-то несоответствия, об ошибке программисту сообщит вычислитель, причём
только тогда, когда вычисление дойдёт до ошибки. Такой подход называют динамической типизацией.
Типы требуют серьёзных размышлений на начальном этапе, этапе определения базовых терминов и спо-
собов их комбинирования. Не упускаем ли мы что-то важное из виду, или, может быть, типы имеют слишком
общий характер и допускают ненужные нам предложения? Приходится задумываться. Но если типы подо-
браны удачно, они сами начинают подсказывать, как строить программу.
1.3 Значения
Итак, мы определили типами базовые понятия и способы комбинирования. Обычно это небольшой набор
слов. Например в логических выражениях всего лишь два слова. Можем ли мы на что либо рассчитывать с
таким словарным запасом? Оказывается, что да. Здесь на помощь приходят синонимы. Сейчас у нас в активе
лишь два слова:
data Bool = True | False
И мы можем определить два синонима:
true :: Bool
true = True
false :: Bool
false = False
В Haskell синонимы пишутся с маленькой буквы. Синоним определяется через знак =. Обратите внимание
на то, что это не процесс вычисления значения. Мы всего лишь объявляем новое имя для комбинации слов.
Теперь мы имеем целых четыре слова! Тем не менее, ушли мы не далеко, и два новых слова, в сущности,
не делают язык выразительнее. Такие синонимы называют константами. Это значит, что одним словом мы
будем обозначать некоторую комбинацию других слов. В данном случае комбинации очень простые.
Но наши синонимы могут определять одни слова через другие. Синонимы могут принимать параметры.
Параметры пишутся через пробел между новым именем и знаком равно:
not :: Bool -> Bool
not True
= False
not False = True
Мы определили новое имя not с типом Bool -> Bool. Оно определяется двумя уравнениями (clause). Слева
от знака равно левая часть уравнения, а справа – правая. В первом уравнении мы говорим, что сочетание (not
True) означает False, а сочетание (not False) означает True. Опять же, мы ничего не вычисляем, мы даём
новые имена нашим константам True и False. Только в этом случае имена составные.
Если вычислителю нужно узнать, что кроется за составным именем not False он последовательно про-
анализирует уравнения сверху вниз, до тех пор, пока левая часть уравнения не совпадёт со значением not
False. Сначала мы сверим с первым:
not True
== not False
-- нет, пошли дальше
not False
== not False
-- эврика, вернём правую часть
=> True
Определим ещё два составных имени
and :: Bool -> Bool -> Bool
and False
_
= False
and True
x
= x
or
:: Bool -> Bool -> Bool
or True
_ = True
or False
x = x
Эти синонимы определяют логические операции “и” и “или”. Здесь несколько новых конструкций, но вы
не пугайтесь, они не так трудны для понимания. Начнём с _:
and False
_
= False
16 | Глава 1: Основы
Здесь cимвол _ означает, что в этом уравнении, если первый параметр равен False, то второй нам уже не
важен, мы знаем ответ. Так, если в логическом “и” один из аргументов равен False, то всё выражение равно
False. Так же и в случае с or.
Теперь другая новая конструкция:
and True
x
= x
В этом случае параметр x служит для того, чтобы перетащить значение из аргумента в результат. Кон-
кретное значение нам также не важно, но в этом случае мы полагаем, что слева и справа от =, x имеет одно
и то же значение.
Итак у нас уже целых семь имён: True, False, true, false, not, and, or. Или не семь? На самом деле, их
уже бесконечное множество. Поскольку три из них составные, мы можем создавать самые разнообразные
комбинации:
not (and true False)
or (and true true) (or False False)
not (not true)
not (or (or True True) (or False (not True)))
...
Обратите внимание на использование скобок, они группируют значения. Так, если бы мы написали not
not true вместо not (not true), мы бы получили ошибку компиляции, потому что not ожидает один пара-
метр, а в выражении not not true их два. Параметры дописываются к имени через пробел.
Посмотрим, как происходят вычисления. В сущности, процесса вычислений нет, есть процесс замены
синонимов на основные понятия согласно уравнениям. Базовые понятия мы определили в типах. Так давайте
“вычислим” выражение not (and true False):
-- выражение
--
уравнение
not (and true False)
--
true
= True
not (and True False)
--
and True
x = x
=> and True False = False
not False
--
not False
= True
True
Слева в столбик написаны шаги “вычисления”, а справа уравнения, по которым синонимы заменяются
на комбинации слов. Процесс замены синонима (левой части уравнения) на комбинацию слов (правую часть
уравнения) называется редукцией (reduction).
Сначала мы заменили синоним true на правую часть его уравнения, тo есть на конструктор True. Затем
мы заменили выражение (and True False) на правую часть из уравнения для синонима and. Обратите вни-
мание на то, что переменная x была заменена на значение False. Последним шагом была замена синонима
not. В конце концов мы пришли к базовому понятию, а именно – к одному из двух конструкторов. В данном
случае True.
Интересно, что новые синонимы могут быть использованы в правых частях уравнений. Так мы можем
определить операцию “исключающее или”:
xor :: Bool -> Bool -> Bool
xor a b = or (and (not a) b) (and a (not b))
Этим выражением мы говорим, что xor a b это или отрицание a и b, или a и отрицание b. Это и есть
определение “исключающего или”.
Может показаться, что с типом Bool мы зациклены на двух конструкторах, и единственное, что нам оста-
ётся – это давать всё новые и новые имена словам True и False. Но на самом деле это не так. С помощью
типов-параметров мы можем выйти за эти рамки. Определим функцию ветвления ifThenElse:
ifThenElse :: Bool -> a -> a -> a
ifThenElse True
t
_ = t
ifThenElse False
_
e = e
Эта функция первым аргументом принимает значение типа Bool, а вторым и третьим – альтернативы
некоторого типа a. Если первый аргумент – True, возвращается второй аргумент, а если – False, то третий.
Интересно, что в Haskell ничего не происходит, мир Haskell-значений стоит на месте. Мы просто даём
имена разным комбинациям слов. Определяем новые термины. Потом на этих терминах определяем новые
термины, и так далее. Кажется, если ничего не меняется, то зачем язык? И что мы собираемся программиро-
вать без вычислений?
Значения | 17
Разгадка кроется в функциях not, and и or. До того как мы их определили, у нас было четыре имени, но
после их определения имён стало бесконечное множество. Три синонима пополнили наш язык бесконечным
набором комбинаций. В этом суть. Мы определяем базовые элементы и способы составления новых, потом
мы просим ”вычислить’ комбинацию из них. Мы не определяли явно, чему равна комбинация not (and true
False), это сделал за нас вычислитель Haskell1.
Вычислить стоит в кавычках, потому что на самом деле вычислений нет, есть замена синонимов на ком-
бинации простейших элементов.
Ещё один пример, положим у нас есть тип:
data Status = Work | Rest
Он определяет, что делать в данный день: работать (Work) или отдыхать (Rest). У разных рабочих разный
график. Например, есть функции:
jonny :: Week -> Status
jonny x = ...
colin :: Week -> Status
colin x = ...
Конкретное определение сейчас не важно, важно, что они определяют зависимость статуса (Status) от
дня недели (Week) для работников Джонни (jonny) и Колина (colin).
Также у нас есть полезная функция:
calendar :: Date -> Week
calendar x = ...
Она определяет по дате день недели. И теперь, зная лишь эти функции, мы можем спросить у вычислителя
будет ли у Джонни выходной 8 августа 3043 года:
jonny (calendar (Date (Year 3043) August (Day 8)))
=> jonny Saturday
=> Rest
Интересно, у нас опять всего лишь два значения, но, дав такое большое имя одному из значений, мы
смогли получить полезную нам информацию, ничего не вычисляя.
1.4 Классы типов
Если типы и значения – привычные понятия, которые можно найти в том или ином виде в любом языке
программирования, то термин класс типов встречается не часто. У него нет аналогов и в обычном языке,
поэтому я сначала постараюсь объяснить его смысл на примере.
В типизированном языке у каждой функции есть тип, но бывают функции, которые могут быть опреде-
лены на аргументах разных типов; по сути, они описывают схожие понятия, но определены для значений
разных типов. Например, функция сравнения на равенство, говорящая о том, что два значения одного типа
a равны, имеет тип a -> a -> Bool, или функция печати выражения имеет тип a -> String, но что такое
a в этих типах? Тип a является любым типом, для которого сравнение на равенство или печать (преобразо-
вание в строку) имеют смысл. Это понятие как раз и кодируется в классах типов. Классы типов (type class)
позволяют определять функции с одинаковым именем для разных типов.
У классов типов есть имена. Также как и имена классов, они начинаются с большой буквы. Например,
класс сравнений на равенство называется Eq (от англ. equals – равняется), а класс печати выражений имеет
имя Show (от англ. show – показывать). Посмотрим на их определения:
Класс Eq:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
Класс Show:
1Было бы точнее называть вычислитель редуктором, поскольку мы проводим редукции, или замену эквивалентных значений, но
закрепилось это название. К тому же, редуктор также обозначает прибор.
18 | Глава 1: Основы
class Show a where
show :: a -> String
За ключевым словом class следует имя класса, тип-параметр и ещё одно ключевое слово where. Далее с
отступами пишутся имена определённых в классе значений. Значения класса называются методами.
Мы определяем лишь типы методов, конкретная реализация будет зависеть от типа a. Методы определя-
ются в экземплярах классов типов, мы скоро к ним перейдём.
Программистская аналогия класса типов это интерфейс. В интерфейсе определён набор значений (как
констант, так и функций), которые могут быть применены ко всем типам, которые поддерживают данный
интерфейс. К примеру, в интерфейсе “сравнение на равенство” для некоторого типа a определены две функ-
ции: равно (==) и не равно (/=) с одинаковым типом a -> a -> Bool, или в интерфейсе “печати” для любого
типа a определена одна функция show типа a -> String.
Математическая аналогия класса типов это алгебраическая система. Алгебра изучает свойства объекта в
терминах операций, определённых на нём, и взаимных ограничениях этих операций. Алгебраическая систе-
ма представляет собой набор операций и свойств этих операций. Этот подход позволяет абстрагироваться
от конкретного представления объектов. Например группа – это все объекты данного типа a, для которых
определены значения: константа – единица типа a, бинарная операция типа a -> a -> a и операция взятия
обратного элемента, типа a -> a. При этом на операции накладываются ограничения, называемые свойства-
ми операций. Например, ассоциативность бинарной операции, или тот факт, что единица с любым другим
элементом, применённые к бинарной операции, дают на выходе исходный элемент.
Давайте определим класс для группы:
class Group a where
e
:: a
(+) :: a -> a -> a
inv :: a -> a
Класс с именем Group имеет для некоторого типа a три метода: константу e :: a, операцию (+) :: a ->
a -> a и операцию взятия обратного элемента inv :: a -> a.
Как и в алгебре, в Haskell классы типов позволяют описывать сущности в терминах определённых на них
операций или значений. В примерах мы указываем лишь наличие операций и их типы, так же и в классах
типов. Класс типов содержит набор имён его значений с информацией о типах значений.
Определив класс Group, мы можем начать строить различные выражения, которые будут потом интер-
претироваться специфическим для типа образом:
twice :: Group a => a -> a
twice a = a + a
isE :: (Group a, Eq a) => a -> Bool
isE x = (x == e)
Обратите внимание на запись Group a => и (Group a, Eq a) => . Это называется контекстом объявления
типа. В контексте мы говорим, что данный тип должен быть из класса Group или из классов Group и Eq. Это
значит, что для этого типа мы можем пользоваться методами из этих классов.
В первой функции twice мы воспользовались методом (+) из класса Group, поэтому функция имеет кон-
текст Group a => . А во второй функции isE мы воспользовались методом e из класса Group и методом (==)
из класса Eq, поэтому функция имеет контекст (Group a, Eq a) => .
Контекст классов типов. Суперклассы
Класс типов также может содержать контекст. Он указывается между словом class и именем класса.
Например
class IsPerson a
class IsPerson a => HasName a where
name :: a -> String
Это определение говорит о том, что мы можем сделать экземпляр класса HasName только для тех типов,
которые содержатся в IsPerson. Мы говорим, что класс HasName содержится в IsPerson. В этом случае класс
из контекста IsPerson называют суперклассом для данного класса HasName.
Это сказывается на контексте объявления типа. Теперь, если мы пишем
Классы типов | 19
fun :: HasName a => a -> a
Это означает, что мы можем пользоваться для значений типа a как методами из класса HasName, так и
методами из класса IsPerson. Поскольку если тип принадлежит классу HasName, то он также принадлежит и
IsPerson.
Запись (IsPerson a => HasName a) немного обманывает, было бы точнее писать IsPerson a <= HasName
a, если тип a в классе HasName, то он точно в классе IsPerson, но в Haskell закрепилась другая запись.
1.5 Экземпляры классов типов
В экземплярах (instance) классов типов мы даём конкретное наполнение для методов класса типов. Опре-
деление экземпляра пишется так же, как и определение класса типа, но вместо class мы пишем instance,
вместо некоторого типа наш конкретный тип, а вместо типов методов – уравнения для них.
Определим экземпляры для Bool
Класс Eq:
instance Eq Bool where
(==) True
True
= True
(==) False False = True
(==) _
_
= False
(/=) a b
= not (a == b)
Класс Show:
instance Show Bool where
show True
= ”True”
show False = ”False”
Класс Group:
instance Group Bool where
e
= True
(+) a b = and a b
inv a
= not a
Отметим важность наличия свойств (ограничений) у значений, определённых в классе типов. Так, на-
пример, в классе типов “сравнение на равенство” для любых двух значений данного типа одна из операций
должна вернуть “истину”, а другая “ложь”, то еесть два элемента данного типа либо равны, либо не рав-
ны. Недостаточно определить равенство для конкретного типа, необходимо убедиться в том, что для всех
элементов данного типа свойства понятия равенства не нарушаются.
На самом деле приведённое выше определение экземпляра для Group не верно, хотя по типам оно под-
ходит. Оно не верно как раз из-за нарушения свойств. Для группы необходимо, чтобы для любого a выпол-
нялось:
inv a + a == e
У нас лишь два значения, и это свойство не выполняется ни для одного из них. Проверим:
inv True
+ True
=> (not True) + True
=> False
+ True
=> and False
True
=> False
inv False
+ False
=> (not False) + False
=> True
+ False
=> and True
False
=> False
Проверять свойства очень важно, потому что другие люди, читая ваш код и используя ваши функции,
будут на них рассчитывать.
20 | Глава 1: Основы
1.6 Ядро Haskell
Фуууухх. Мы закончили наш пробег. Теперь можно остановиться, отдышаться и подвести итоги. Давайте
вспомним синтаксические конструкции, которые нам встретились.
Модули
module New(edef1, edef2, ... , edefN) where
import Old1(idef11, idef12, ... , idef1N)
import Old2(idef21, idef22, ... , idef2M)
...
import OldK(idefK1, idefK2, ... , idefKP)
-- определения :
...
Ключевые слова: module, where, import. Мы определили модуль с именем New, который экспортирует
определения edef1, edef2, … , edefN. И импортирует определения из модулей Old1, Old2, и т.д., определения
написаны в скобках за ключевыми словами import и именами модулей.
Типы
Тип определяется с помощью:
• Перечисления альтернатив через |
data Type = Alt1 | Alt2 | ... | AltN
Эту операцию называют суммой типов.
• Составления сложного типа из подтипов, пишем конструктор первым, затем через пробел подтипы:
data Type = Name
Sub1
Sub2
...
SubN
Эту операцию называют произведением типов.
Есть одно исключение: если тип состоит из двух подтипов, мы можем дать конструктору символьное
(а не буквенное) имя, но оно должно начинаться с двоеточия :, как в случае списка, например, можно
делать такие определения типов:
data Type = Sub1 :+ Sub2
data Type = Sub1 :| Sub2
• Комбинации суммы и произведения типов:
data Type = Name1
Sub11
Sub12
...
Sub1N
| Name2
Sub21
Sub22
...
Sub2M
...
| NameK
SubK1
SubK2
...
SubKP
Такие типы называют алгебраическими типами данных. С помощью типов мы определяем основные поня-
тия и способы их комбинирования.
Значения
Как это ни странно, нам встретилась лишь одна операция создания значений: определение синонима. Она
пишется так
name x1
x2 ... xN = Expr1
name x1
x2 ... xN = Expr2
name x1
x2 ... xN = Expr3
Слева от знака равно стоит составное имя, а справа от знака равно некоторое выражение, построенное
согласно типам. Разные комбинации имени name с параметрами определяют разные уравнения для синонима
name.
Также мы видели символ _, который означает “всё, что угодно” на месте аргумента. А также мы увидели,
как с помощью переменных можно перетаскивать значения из аргументов в результат.
Ядро Haskell | 21
Классы типов
Нам встретилась одна конструкция определения классов типов:
class Name a where
method1 :: a -> ...
method2 :: a -> ...
...
methodN :: a -> ...
Экземпляры классов типов
Нам встретилась одна конструкция определения экземпляров классов типов:
instance Name Type where
method1 x1 ... xN = ...
method2 x1 ... xM = ...
...
methodN x1 ... xP = ...
Типы, значения и классы типов
Каждое значение имеет тип. Значение v имеет тип T на Haskell:
v :: T
Функциональный тип обозначается стрелкой: a -> b
fun :: a -> b
Тип значения может иметь контекст, он говорит о том, что параметр должен принадлежать классу типов:
fun1 :: С a
=> a -> a
fun2 :: (C1 a, C2, ... , CN) => a -> a
Суперклассы
Также контекст может быть и у классов, запись
class A a => B a where
...
Означает, что класс B целиком содержится в A, и перед тем как объявлять экземпляр для класса B, необ-
ходимо определить экземпляр для класса A. При этом класс A называют суперклассом для B.
1.7 Двумерный синтаксис
Наверное вы обратили внимание на то, что в Haskell нет разделителей строк и дополнительных скобок,
которые бы указывали границы определения классов или функций. Компилятор Haskell ориентируется по
переносам строки и отступам.
Так если мы пишем в классе:
class Eq a where
(==) :: a -> a -> a
(/=) :: a -> a -> a
По отступам за первой строкой определения компилятор понимает, что класс содержит два метода. Если
бы мы написали:
class Eq a where
(==) :: a -> a -> a
(/=) :: a -> a -> a
22 | Глава 1: Основы
То смысл был бы совсем другим. Теперь мы определяем класс Eq с одним методом == и указываем тип
некоторого значения (/=). Основное правило такое: конструкции, расположенные на одном уровне, вырав-
ниваются с помощью отступов. Чем правее находится определение, тем глубже оно вложено в какую-нибудь
специальную конструкцию. Пока нам встретилось лишь несколько специальных конструкций, но дальше
появятся и другие. Часто отступы набираются с помощью табуляции. Это удобно. Но лучше пользоваться
пробелами или настроить ваш любимый текстовый редактор так, чтобы он автоматически заменял табуля-
цию на пробелы. Зачем это нужно? Дело в том, что в разных редакторах на табуляцию может быть назначено
разное количество пробелов, так код набранный с двухзначной табуляцией будет очень трудно прочитать
если открыть его в редакторе с четырьмя пробелами вместо табуляции. Поскольку очень часто табуляция
перемежается с пробелами и выравнивание может “поехать”. Поэтому признаком хорошего стиля в Haskell
считается полный отказ от табуляции.
1.8 Краткое содержание
Итак подведём итоги: у нас есть две операции для определения типов (сумма и произведение) и по одной
для значений (синонимы), классов типов и экземпляров. А также бесконечное множество их комбинаций, из
которых и состоит увлекательный мир Haskell. Конечно не только из них, есть нюансы, синтаксический сахар,
расширения языка. Об этом и многом другом мы узнаем из этой книги.
Интересно, что в Haskell, несмотря на обилие конструкций и библиотек, ты чувствуешь, что за ними стоит
нечто из мира науки, мира чистого знания. Ты не просто учишься пользоваться определёнными функциями
или классами, а узнаёшь что-то новое и красивое.
1.9 Упражнения
Потренируйтесь в описаниях в рамках системы типов. Вы определяете базовые понятия и способы их
комбинирования. У вас есть три операции:
• Сумма типов data T = A1 | A2. Перечисление альтернатив
• Произведение типов data T = S S1 S2. Этим мы говорим, что понятие состоит из нескольких.
• Взятие в список [T]. Обозначает множественное число, элементов типа T их может быть несколько.
Опишите что-либо: комнату, дорогу, город, человека, главу из книги, математическую теорию, всё что
угодно.
Ниже приведён пример для понятий из этой главы:
data Program = Programm ProgramType [Module]
data ProgramType = Executable | Library
data Module = Module [Definition]
data Definition = Definition DefinitionType Element
data DefinitionType = Export | Inner
data Element = ET Type | EV Value | EC Class | EI Instance
data Type
= Type String
data Value
= Value String
data Class
= Class String
data Instance = Instance String
После того как вы закончите с описанием, подумайте, какие производные связи могли бы вас заинтере-
совать. Какие функции вам бы хотелось определить в этом описании. Выпишите их типы без определений,
например так:
-- Все объявления типов в модуле
getTypes :: Module -> [Type]
-- Провести редукцию значения:
reduce :: Value -> Program -> Value
-- Проверить типы:
Краткое содержание | 23
checkTypes :: Program -> Bool
-- Заменить все определения в модуле на новые
setDefinitions
:: Module -> [Definition] -> Module
-- Упорядочить определения по какому-лбо принципу
orderDefinitions :: [Definition] -> [Definition]
Подумайте: если у вас есть все эти функции, какие производные значения могли бы вам сказать что-
нибудь интересное.
24 | Глава 1: Основы
Глава 2
Первая программа
Я вот говорю-говорю, а вдруг я вас обманываю, и ничего этого нет. В этой главе мы перейдём к програм-
мированию и запустим нашу первую программу в Haskell. Будет много примеров, на которых мы закрепим
наши знания.
2.1 Интерпретатор
Для запуска кода мы будем пользоваться приложением GHC (Glorious Glasgow Haskell Compiler) наиболее
развитой системой интерпретации Haskell программ. В GHC есть компилятор ghc и интерпретатор ghci. Пока
мы будем пользоваться лишь интерпретатором. Если вы не знаете как установить ghc загляните в приложе-
ние. Также нам понадобится текстовый редактор с подсветкой синтаксиса. Подсветка синтаксиса для Haskell
по умолчанию есть в редакторах Vim, Emacs, gedit, geany, yi. Есть IDE для Haskell Leksah. Мы будем писать
модули в файлах и загружать их в интерпретатор. Если вы не знаете продвинутых текстовых редакторов
вроде Vim или Emacs, лучше всего будет начать с gedit.
Интерпретатор позволяет загружать модуль с определениями и набирать значения в командной строке.
Мы набираем значение, а интерпретатор редуцирует его и показывает нам ответ. Интерпретатор запускается
командой ghci в терминале. Определения из модуля могут быть загружены в интерпретатор двумя способа-
ми, либо при запуске интерпретатора командой ghci ИмяМодуля. hs либо в самом интерпретаторе командой
:l ИмяМодуля. hs.
Рассмотрим некоторые полезные команды интерпретатора:
:? Выводит на экран список доступных команд
:t Expression Возвращает тип выражения.
:set +t После выполнения команды интерпретатор будет выводить на экран не только результат вычисле-
ния выражения, но и его тип.
:set +s После выполнения команды интерпретатор будет выводить на экран не только результат вычисле-
ния выражения, но и статистику вычислений.
:l ИмяМодуля Загружает модуль в интерпретатор.
:cd Директория Перейти в данную директорию.
:r Перезагружает, последний загруженный модуль. Этой командой можно пользоваться после внесения в
модуль изменений.
:q Выход из интерпретатора.
2.2 У-вей
Согласно даосам основной принцип жизни заключается в недеянии (у-вей). Всё происходит естественно и
словно само собой. Давайте создадим модуль который ничего не делает. Создадим пустой модуль и загрузим
его в интерпретатор.
module Empty where
import Prelude()
| 25
Зачем мы написали import Prelude()? Этой фразой мы говорим, что не хотим ничего импортировать
из модуля Prelude. По умолчанию в любой модуль загружается модуль Prelude, который содержит много
полезных определений. К примеру там определяется тип Bool, списки и функции для них, символы, классы
типов для сравнения на равенство и печати значений и много, много других определений. В первых главах
я хочу сделать акцент на самом языке Haskell, а не на производных выражениях, поэтому пока мы будем в
явном виде загружать из модуля Prelude лишь самые необходимые определения.
Сохраним модуль в файле Empty. hs, сделаем директорию модуля текущей и запустим интерпретатор
командой ghci Empty (имя расширения можно не писать). Также можно просто запустить интерпретатор
командой ghci, переключиться на директорию командой :cd и загрузить модуль командой :l Empty.
$ ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/
:? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :cd ~/haskell-notes/code/ch-2/
Prelude> :l Empty.hs
[1 of 1] Compiling Empty
( Empty.hs, interpreted )
Ok, modules loaded: Empty.
*Empty>
Слева от знака приглашения к вводу > отображаются загруженные в интерпретатор модули. По умол-
чанию загружается модуль Prelude. После выполнения команды :l мы видим, что Prelude сменилось на
Empty.
Теперь давайте потренируемся перезагружать модули. Давайте изменим наш модуль, сделаем его не та-
ким пустым, убрав последние две скобки от модуля Prelude в директиве import. Теперь сохраним изменения
и выполним команду :r.
*Empty> :r
[1 of 1] Compiling Empty
( Empty. hs, interpreted )
Ok, modules loaded: Empty.
*Empty>
Завершим сессию интерпретатора командой :q.
*Empty> :q
Leaving GHCi.
Внешние модули должны находится в текущей директории. Давайте потренируемся с подключением
определений из внешних модулей. Создадим модуль близнец модуля Empty. hs:
module EmptyEmpty where
import Prelude()
И сохраним его в той же директории, что и модуль Empty, теперь мы можем включить все определения
из модуля EmptyEmpty:
module Empty where
import EmptyEmpty
Когда у нас будет много модулей мы можем разместить их по директориям. Создадим в одной дирек-
тории с модулем Empty директорию Sub, а в неё поместим копию модуля Empty. Существует одна тонкость:
поскольку модуль находится в поддиректории, для того чтобы он стал виден из текущей директории, необ-
ходимо дописать через точку имя директории в которой он находится:
module Sub.Empty where
Теперь мы можем загрузить этот модуль из исходного:
module Empty where
import EmptyEmpty
import Sub.Empty
Обратите внимание на то, что мы приписываем к модулю в поддиректории Sub имя поддиректории. Если
бы он был заложен в ещё одной директории, то мы написали бы через точку имя и этой поддиректории:
module Empty where
import Sub1.Sub2.Sub3.Sub4.Empty
26 | Глава 2: Первая программа
2.3 Логические значения
Пустой модуль это хорошо, но слишком скучно. Давайте перепишем объявленные в этой главе опреде-
ления в модуль, загрузим его в интерпретатор и понабираем значения.
Начнём с логических операций. Давайте не будем переопределять Bool, Show и Eq, а просто возьмём их
из Prelude:
module Logic where
import Prelude(Bool(.. ), Show(.. ), Eq(.. ))
Две точки в скобках означают “все конструкторы” (в случае типа) и “все методы” (в случае класса типа).
Строчку
import Prelude(Bool(.. ), Show(.. ), Eq(.. ))
Следует читать так: Импортируй из модуля Prelude тип Bool и все его конструкторы и классы Show и
Eq со всеми их методами. Если бы мы захотели импортировать только конструктор True, мы бы написали
Bool(True), а если бы мы захотели импортировать лишь имя типа, мы бы написали просто Bool без скобок.
Сначала выпишем в модуль наши синонимы:
module Logic where
import Prelude(Bool(.. ), Show(.. ), Eq(.. ))
true :: Bool
true = True
false :: Bool
false = False
not :: Bool -> Bool
not True
= False
not False = True
and :: Bool -> Bool -> Bool
and False
_
= False
and True
x
= x
or
:: Bool -> Bool -> Bool
or True
_ = True
or False
x = x
xor :: Bool -> Bool -> Bool
xor a b = or (and (not a) b) (and a (not b))
ifThenElse :: Bool -> a -> a -> a
ifThenElse True
t
_ = t
ifThenElse False
_
e = e
Теперь сохраним модуль и загрузим его в интерпретатор. Для наглядности мы установим флаг +t, при
этом будет возвращено не только значение, но и его тип. Понабираем разные комбинации значений:
*Logic> :l Logic
[1 of 1] Compiling Logic
( Logic. hs, interpreted )
Ok, modules loaded: Logic.
*Logic> :set +t
*Logic> not (and true False)
True
it :: Bool
*Logic> or (and true true) (or False False)
True
it :: Bool
*Logic> xor (not True) (False)
False
it :: Bool
*Logic> ifThenElse (or true false) True False
True
it :: Bool
Логические значения | 27
Разумеется в Haskell уже определены логические операции, здесь мы просто тренировались. Они называ-
ются not, (&& ), ||. Операция xor это то же самое, что и (/=). Для Bool определён экземпляр класса Eq. Также
в Haskell есть конструкция ветвления она пишется так:
x = if cond then t else e
Слова if, then и else – ключевые. cond имеет тип Bool, а t и e одинаковый тип.
В коде программы обычно пишут так:
x = if a > 3
then ”Hello”
else (if a < 0
then ”Hello”
else ”Bye”)
Отступы обязательны.
Давайте загрузим в интерпретатор модуль Prelude и наберём те же выражения стандартными функция-
ми:
*Logic> :m Prelude
Prelude> not (True && False)
True
it :: Bool
Prelude> (True && True) || (False || False)
True
it :: Bool
Prelude> not True /= False
False
it :: Bool
Prelude> if (True || False) then True else False
True
it :: Bool
Бинарные операции с символьными именами пишутся в инфиксной форме, то есть между аргументами
как в a && b или a + b. Значение с буквенным именем также можно писать в инфиксной форме, для этого
оно заключается в апострофы, например a ‘and‘ b или a ‘plus‘ b. Апострофы обычно находятся на одной
кнопке с буквой “ё”. Также символьные функции можно применять в префиксной форме, заключив их в
скобки, например (&& ) a b и (+) a b. Попробуем в интерпретаторе:
Prelude> True && False
False
it :: Integer
Prelude> (&& ) True False
False
it :: Bool
Prelude> let and a b = a && b
and :: Bool -> Bool -> Bool
Prelude> and True False
False
it :: Bool
Prelude> True ‘and‘ False
False
it :: Bool
Обратите внимание на строчку let and a b = a && b. В ней мы определили синоним в интерпретаторе.
Сначала мы пишем ключевое слово let затем обычное определение синонима, как в программе. Это простое
однострочное определение, но мы можем набирать в интерпретаторе и более сложные. Мы можем написать
несколько строчек в одной, разделив их точкой с запятой:
Prelude> let not2 True = False; not2 False = True
Мы можем записать это определение более наглядно, совсем как в редакторе, если воспользуемся много-
строчным вводом. Для этого просто наберите команду :{. Для выхода воспользуйтесь командой :}. Отметим,
что точкой с запятой можно пользоваться и в обычном коде. Например в том случае если у нас много кратких
определений и мы хотим записать их покомпактней, мы можем сделать это так:
a1 = 1;
a2 = 2;
a3 = 3
a4 = 4;
a5 = 5;
a6 = 6
28 | Глава 2: Первая программа
2.4 Класс Show. Строки и символы
Мы набираем в интерпретаторе какое-нибудь сложное выражение, или составной синоним, интерпрета-
тор проводит редукцию и выводит ответ на экран. Откуда интерпретатор знает как отображать значения
типа Bool? Внутри интерпретатора вызывается метод класса Show, который переводит значение в строку. И
затем мы видим на экране ответ.
Для типа Bool экземпляр класса Show уже определён, поэтому интерпретатор знает как его отображать.
Обратите внимание на эту особенность языка, вид значения определяется пользователем, в экземпляре
класса Show. Из соображений наглядности вид значения может сильно отличаться от его внутреннего пред-
ставления.
В этом разделе мы рассмотрим несколько примеров с классом Show, но перед этим мы поговорим о стро-
ках и символах в языке Haskell.
Строки и символы
Посмотрим в интерпретаторе на определение строк (тип String), для этого мы воспользуемся командой
:i (сокращение от :info):
Prelude> :i String
type String = [Char]
-- Defined in ‘GHC.Base’
Интерпретатор показал определение типа и в комментариях указал в каком модуле тип определён. В
этом определении мы видим новое ключевое слово type. До этого для определения типов нам встречалось
лишь слово data. Ключевое слово type определяет синоним типа. При этом мы не вводим новый тип, мы
лишь определяем для него псевдоним. String является синонимом для списка значений типа Char. Тип
Char представляет символы. Итак строка – это список символов. В Haskell символы пишутся в ординарных
кавычках, а строки в двойных:
Prelude> [’H’,’e’,’l’,’l’,’o’]
”Hello”
it :: [Char]
Prelude> ”Hello”
”Hello”
it :: [Char]
Prelude> ’+’
’+’
it :: Char
Для обозначения перехода на новую строку используется специальный символ \n. Если строка слишком
длинная и не помещается на одной строке, то её можно перенести так:
str = ”My long long long long \
\long long string”
Перенос осуществляется с помощью комбинации следующих друг за другом обратных слэшей.
Нам понадобится функция конкатенации списков (++), она определена в Prelude, с её помощью мы будем
объединять строки:
Prelude> :t (++)
(++) :: [a] -> [a] -> [a]
Prelude> ”Hello” ++ [’ ’] ++ ”World”
”Hello World”
it :: [Char]
Пример: Отображение дат и времени
Приведём, пример в котором отображаемое значение не совпадает с видом значения в коде. Мы отобра-
зим значения из мира календаря. Для начала давайте сохраним определения в отдельном модуле:
module Calendar where
import Prelude (Int, Char, String, Show(.. ), (++))
-- Дата
Класс Show. Строки и символы | 29
data Date = Date Year Month Day
-- Год
data Year
= Year Int
-- Int это целые числа
-- Месяц
data Month
= January
| February
| March
| April
| May
| June
| July
| August
| September
| October
| November | December
data Day = Day Int
-- Неделя
data Week
= Monday
| Tuesday
| Wednesday
| Thursday
| Friday
| Saturday
| Sunday
-- Время
data Time = Time Hour Minute Second
data Hour
= Hour
Int
-- Час
data Minute = Minute Int
-- Минута
data Second = Second Int
-- Секунда
Теперь сохраним наш модуль под именем Calendar. hs и загрузим в интерпретатор:
Prelude> :l Calendar
[1 of 1] Compiling Calendar
( Calendar. hs, interpreted )
Ok, modules loaded: Calendar.
*Calendar> Monday
< interactive>:3:1:
No instance for (Show Week)
arising from a use of ‘System.IO. print’
Possible fix: add an instance declaration for (Show Week)
In a stmt of an interactive GHCi command: System.IO. print it
Смотрите мы попытались распечатать значение Monday, но в ответ получили ошибку. В ней интерпре-
татор сообщает нам о том, что для типа Week не определён экземпляр класса Show, и он не знает как его
распечатывать. Давайте подскажем ему. Обычно дни недели в календарях печатают не полностью, в имя
попадают лишь три первых буквы:
instance Show Week where
show Monday
= ”Mon”
show Tuesday
= ”Tue”
show Wednesday
= ”Wed”
show Thursday
= ”Thu”
show Friday
= ”Fri”
show Saturday
= ”Sat”
show Sunday
= ”Sun”
Отступы перед show обязательны, но выравнивание по знаку равно не обязательно, мне просто нравится
так писать. По отступам компилятор понимает, что все определения относятся к определению instance.
Теперь запишем экземпляр в модуль, сохраним, и перезагрузим в интерпретатор:
*Calendar> :r
[1 of 1] Compiling Calendar
( Calendar. hs, interpreted )
Ok, modules loaded: Calendar.
*Calendar> Monday
Mon
it :: Week
*Calendar> Sunday
Sun
it :: Week
Теперь наши дни отображаются. Я выпишу ещё один пример экземпляра для Time, а остальные достанутся
вам в качестве упражнения.
30 | Глава 2: Первая программа
instance Show Time where
show (Time h m s) = show h ++ ”:” ++ show m ++ ”:” ++ show s
instance Show Hour where
show (Hour h) = addZero (show h)
instance Show Minute where
show (Minute m) = addZero (show m)
instance Show Second where
show (Second s) = addZero (show s)
addZero :: String -> String
addZero (a:[]) = ’0’ : a : []
addZero as
= as
Функцией addZero мы добавляем ноль в начало строки, в том случае, если число однозначное, также в
этом определении мы воспользовались тем, что для типа целых чисел Int экземпляр Show уже определён.
Проверим в интерпретаторе:
*Calendar> Time (Hour 13) (Minute 25) (Second 2)
13:25:02
it :: Time
2.5 Автоматический вывод экземпляров классов типов
Для некоторых стандартных классов экземпляры классов типов могут быть выведены автоматически.
Это делается с помощью директивы deriving. Она пишется сразу после объявления типа. Например так мы
можем определить тип и экземпляры для классов Show и Eq:
data T = A | B | C
deriving (Show, Eq)
Отступ за deriving обязателен, после ключевого слова в скобках указываются классы, которые мы хотим
вывести.
2.6 Арифметика
В этом разделе мы обсудим основные арифметические операции. В Haskell много стандартных классов,
которые группируют различные типы операций, есть класс для сравнения на равенство, отдельный класс для
сравнения на больше/меньше, класс для умножения, класс для деления, класс для упорядоченных чисел, и
много других. Зачем такое изобилие классов?
Каждый из классов отвечает независимой группе операций. Есть много объектов, которые можно только
складывать, но нельзя умножать или делить. Есть объекты, для которых сравнение на равенство имеет смысл,
а сравнение на больше/меньше – нет.
Для иллюстрации мы воспользуемся числами Пеано, у них компактное определение, всего два конструк-
тора, которых тем не менее достаточно для описания множества натуральных чисел:
module Nat where
data Nat = Zero | Succ Nat
deriving (Show, Eq, Ord)
Конструктор Zero указывает на число ноль, а (Succ n) на число следующее за данным числом n. В
последней строчке мы видим новый класс Ord, этот класс содержит операции сравнения на больше/меньше:
Prelude> :i Ord
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
(< ) :: a -> a -> Bool
(>=) :: a -> a -> Bool
(> ) :: a -> a -> Bool
(<=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
Автоматический вывод экземпляров классов типов | 31
Тип Ordering кодирует результаты сравнения:
Prelude> :i Ordering
data Ordering = LT | EQ | GT
-- Defined in GHC.Ordering
Он содержит конструкторы, соответствующие таким понятиям как меньше, равно и больше.
Класс Eq. Сравнение на равенство
Вспомним определение класса Eq:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
a == b = not (a /= b)
a /= b = not (a == b)
Появились две детали, о которых я умолчал в предыдущей главе. Это две последние строчки. В них
мы видим определение == через /= и наоборот. Это определения методов по умолчанию. Такие определения
дают нам возможность определять не все методы класса, а лишь часть основных, а все остальные мы получим
автоматически из определений по умолчанию.
Казалось бы почему не оставить в классе Eq один метод а другой метод определить в виде отдельной
функции:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: Eq a => a -> a -> Bool
a /= b = not (a == b)
Так не делают по соображениям эффективности. Есть типы для которых проще вычислить /= чем ==.
Тогда мы определим тот метод, который нам проще вычислять и второй получим автоматически.
Набор основных методов, через которые определены все остальные называют минимальным полным опре-
делением (minimal complete definition) класса. В случае класса Eq это метод == или метод /=.
Мы уже вывели экземпляр для Eq, поэтому мы можем пользоваться методами == и /= для значений типа
Nat:
*Calendar> :l Nat
[1 of 1] Compiling Nat
( Nat. hs, interpreted )
Ok, modules loaded: Nat.
*Nat> Zero == Succ (Succ Zero)
False
it :: Bool
*Nat> Zero /= Succ (Succ Zero)
True
it :: Bool
Класс Num. Сложение и умножение
Сложение и умножение определены в классе Num. Посмотрим на его определение:
*Nat> :i Num
class (Eq a, Show a) => Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
-- Defined in GHC.Num
Методы (+), (*), (-) в представлении не нуждаются, метод negate является унарным минусом, его можно
определить через (-) так:
32 | Глава 2: Первая программа
negate x = 0 - x
Метод abs является модулем числа, а метод signum возвращает знак числа, метод fromInteger позволяет
создавать значения данного типа из стандартных целых чисел Integer.
Этот класс устарел, было бы лучше сделать отельный класс для сложения и вычитания и отдельный
класс для умножения. Также контекст класса, часто становится помехой. Есть объекты, которые нет смысла
печатать но, есть смысл определить на них сложение и умножение. Но пока в целях совместимости с уже
написанным кодом, класс Num остаётся прежним.
Определим экземпляр для чисел Пеано, но давайте сначала разберём функции по частям.
Сложение
Начнём со сложения:
instance Num Nat where
(+) a Zero
= a
(+) a (Succ b) = Succ (a + b)
Первое уравнение говорит о том, что, если второй аргумент равен нулю, то мы вернём первый аргумент
в качестве результата. Во втором уравнении мы “перекидываем” конструктор Succ из второго аргумента за
пределы суммы. Схематически вычисление суммы можно представить так:
3+2 → 1 + (3+1) → 1 + (1 + (3+0))
1 + (1 + 3) → 1 + (1 + (1 + (1 + (1 + 0)))) → 5
Все наши числа имеют вид 0 или 1+ n, мы принимаем на вход два числа в таком виде и хотим в результате
составить число в этом же виде, для этого мы последовательно перекидываем $(1+) в начало выражения из
второго аргумента.
Вычитание
Операция отрицания не имеет смысла, поэтому мы воспользуемся специальной функцией error ::
String -> a, она принимает строку с сообщением об ошибке, при её вычислении программа остановит-
ся с ошибкой и сообщение будет выведено на экран.
negate _ = error ”negate is undefined for Nat”
Умножение
Теперь посмотрим на умножение:
(*) a Zero
= Zero
(*) a (Succ b) = a + (a * b)
В первом уравнении мы вернём ноль, если второй аргумент окажется нулём, а во втором мы за каждый
конструктор Succ во втором аргументе прибавляем к результату первый аргумент. В итоге, после вычисле-
ния a * b мы получим аргумент a сложенный b раз. Это и есть умножение. При этом мы воспользовались
операцией сложения, которую только что определили. Посмотрим на схему вычисления:
3*2 → 3 + (3*1) → 3 + (3 + (3*0)) → 3 + (3+0) → 3+3 →
1 + (3+2) → 1 + (1 + (3+1)) → 1 + (1 + (1 + (3+0))) →
1 + (1 + 1 + 3) → 1 + (1 + (1 + (1 + (1 + (1 + 0))))) → 6
Операции abs и signum
Поскольку числа у нас положительные, то методы abs и signum почти ничего не делают:
abs
x
= x
signum Zero = Zero
signum _
= Succ Zero
Арифметика | 33
Перегрузка чисел
Остался последний метод fromInteger. Он конструирует значение нашего типа из стандартного:
fromInteger 0 = Zero
fromInteger n = Succ (fromInteger (n-1))
Зачем он нужен? Попробуйте узнать тип числа 1 в интерпретаторе:
*Nat> :t 1
1 :: (Num t) => t
Интерпретатор говорит о том, тип значения 1 является некоторым типом из класса Num. В Haskell обозна-
чения для чисел перегружены. Когда мы пишем 1 на самом деле мы пишем (fromInteger (1::Integer)).
Поэтому теперь мы можем не писать цепочку Succ-ов, а воспользоваться методом fromInteger, для этого
сохраним определение экземпляра для Num и загрузим обновлённый модуль в интерпретатор:
[1 of 1] Compiling Nat
( Nat. hs, interpreted )
Ok, modules loaded: Nat.
*Nat> 7 :: Nat
Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))
*Nat> (2 + 2) :: Nat
Succ (Succ (Succ (Succ Zero)))
*Nat> 2 * 3 :: Nat
Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
Вы можете убедиться насколько гибкими являются числа в Haskell:
*Nat> (1 + 1) :: Nat
Succ (Succ Zero)
*Nat> (1 + 1) :: Double
2.0
*Nat> 1 + 1
2
Мы выписали три одинаковых выражения и получили три разных результата, меняя объявление типов. В
последнем выражении тип был приведён к Integer. Это поведение интерпретатора по умолчанию. Если мы
напишем:
*Nat> let q = 1 + 1
*Nat> :t q
q :: Integer
Мы видим, что значение q было переведено в Integer, это происходит лишь в интерпретаторе, если такая
переменная встретится в программе и компилятор не сможет определить её тип из контекста, произойдёт
ошибка проверки типов, компилятор скажет, что он не смог определить тип. Помочь компилятору можно,
добавив объявление типа с помощью конструкции (v :: T).
Посмотрим ещё раз на определение экземпляра Num для Nat целиком:
instance Num Nat where
(+) a Zero
= a
(+) a (Succ b) = Succ (a + b)
(*) a Zero
= Zero
(*) a (Succ b) = a + (a * b)
fromInteger 0 = Zero
fromInteger n = Succ (fromInteger (n-1))
abs
x
= x
signum Zero = Zero
signum _
= Succ Zero
negate _ = error ”negate is undefined for Nat”
34 | Глава 2: Первая программа
Класс Fractional. Деление
Деление определено в классе Fractional:
*Nat>:m Prelude
Prelude> :i Fractional
class Num a => Fractional a where
(/) :: a -> a -> a
recip :: a -> a
fromRational :: Rational -> a
-- Defined in ‘GHC.Real’
instance Fractional Float -- Defined in ‘GHC.Float’
instance Fractional Double -- Defined in ‘GHC.Float’
Функция recip, это аналог negate для Num. Она делит единицу на данное число. Функция fromRational
строит число данного типа из дробного числа. Если мы пишем 2, то к нему подспудно будет применена
функция fromInteger, а если 2.0, то будет применена функция fromRational.
Стандартные числа
В этом подразделе мы рассмотрим несколько стандартных типов для чисел в Haskell. Все эти числа явля-
ются экземплярами основных численных классов. Тех, которые мы рассмотрели, и многих-многих других.
Целые числа
В Haskell предусмотрено два типа для целых чисел. Это Integer и Int. Чем они отличаются? Значения
типа Integer не ограничены, мы можем проводить вычисления с очень-очень-очень большими числами, если
памяти на нашем компьютере хватит. Числа из типа Int ограничены. Каждое число занимает определённый
размер в памяти компьютера. Диапазон значений для Int составляет от − 229 до 229 − 1. Вычисления с Int
более эффективны.
Действительные числа
Действительные числа бывают дробными (тип Rational), с ординарной точностью Float и с двойной
точностью Double. Числа из типа Float занимают меньше места, но они не такие точные как Double. Если вы
сомневаетесь, чем пользоваться, выбирайте Double, обычно Float используется только там, где необходимо
хранить огромные массивы чисел. В этом случае мы экономим много памяти.
Преобразование численных типов
Во многих языках программирования при сложении или умножении чисел разных типов проводится ав-
томатическое приведение типов. Обычно целые числа становятся действительными, Float превращается в
Double и так далее. Это противоречит строгой типизации, поэтому в Haskell этого нет:
Prelude> (1::Int) + (1::Double)
< interactive>:2:13:
Couldn’t match expected type ‘Int’ with actual type ‘Double’
In the second argument of ‘(+)’, namely ‘(1 :: Double)’
In the expression: (1 :: Int) + (1 :: Double)
In an equation for ‘it’: it = (1 :: Int) + (1 :: Double)
Любое преобразование типов контролируется пользователем. Мы должны вызвать специальную функ-
цию.
От целых к действительным: Часто возникает необходимость приведения целых чисел к действитель-
ным при делении. Для этого можно воспользоваться функцией: fromIntegral
Prelude> :i fromIntegral
fromIntegral :: (Integral a, Num b) => a -> b
-- Defined in ‘GHC.Real’
Определим функцию поиска среднего между двумя целыми числами:
meanInt :: Int -> Int -> Double
meanInt a b = fromIntegral (a + b) / 2
Арифметика | 35
В этой функции двойка имеет тип Double. Обратите внимание на скобки: составной синоним всегда при-
тягивает аргументы сильнее чем бинарная операция.
От действительных к целым: В этом нам поможет класс RealFrac. Методы говорят сами за себя:
Prelude GHC.Float> :i RealFrac
class (Real a, Fractional a) => RealFrac a where
properFraction :: Integral b => a -> (b, a)
truncate :: Integral b => a -> b
round :: Integral b => a -> b
ceiling :: Integral b => a -> b
floor :: Integral b => a -> b
-- Defined in ‘GHC.Real’
instance RealFrac Float -- Defined in ‘GHC.Float’
instance RealFrac Double -- Defined in ‘GHC.Float’
Метод properFraction отделяет целую часть числа от дробной:
properFraction :: Integral b => a -> (b, a)
Для того, чтобы вернуть сразу два значения используется кортеж (кортежи пишутся в обычных скобках,
значения следуют через запятую):
Prelude> properFraction 2.5
(2,0.5)
Для пар (кортеж, состоящий из двух элементов) определены две удобные функции извлечения элементов,
их смысл можно понять по одним лишь типам:
fst :: (a, b) -> a
snd :: (a, b) -> b
Проверим:
Prelude> let x = properFraction 2.5
Prelude> (fst x, snd x)
(2, 0.5)
Мы бы и сами могли определить такие функции:
fst :: (a, b) -> a
fst (a, _) = a
snd :: (a, b) -> b
snd (_, b) = b
Между действительными числами: Кто-то написал очень хорошую функцию, но она определена на
Double, а вам приходится использовать Float. Как быть? Нам поможет функция realToFrac:
Prelude> :i realToFrac
realToFrac :: (Real a, Fractional b) => a -> b
-- Defined in ‘GHC.Real’
Она принимает значение из класса Real и приводит его к значению, которое можно делить. Что это за
класс Real? Математики наверное смекнут, что это противоположность комплексным числам (где-то должен
быть определён тип или класс Complex, и он правда есть, но об этом в следующем разделе). При переходе
к комплексным числам мы теряем способность сравнения на больше/меньше, но сохраняем возможность
вычисления арифметических операций, поэтому класс Real это пересечение классов Num и Ord:
Prelude> :i Real
class (Num a, Ord a) => Real a where
toRational :: a -> Rational
Здесь “пересечение” означает “и тот и другой”. Пересечение классов кодируется с помощью контекста.
Вернёмся к нашему первому примеру:
36 | Глава 2: Первая программа
Prelude> realToFrac (1::Float) + (1::Double)
2.0
Отметим, что этой функцией можно пользоваться не только для типов Float и Double, в Haskell возможны
самые экзотические числа.
Если преобразования между Float и Double происходят очень-очень часто, возможно имеет смысл вос-
пользоваться специальными для GHC функциями: Они определены в модуле GHC.Float:
Prelude> :m +GHC.Float
Prelude GHC.Float> :t float2Double
float2Double :: Float -> Double
Prelude GHC.Float> :t double2float
double2Float :: Double -> Float
2.7 Документация
К этой главе мы уже рассмотрели основные конструкции языка и базовые типы. Если у вас есть какая-то
задача, вы уже можете начать её решать. Для этого сначала нужно будет описать в типах проблему, затем
выразить с помощью функций её решение.
Но не стоит писать все функции самостоятельно, если функция достаточно общая её наверняка кто-
нибудь уже написал. Самые полезные функции и классы определены в модуле Prelude и основных стан-
дартных библиотечных модулях. Было бы излишним описывать каждую функцию, книга превратилась бы
в справочник. Вместо этого давайте научимся искать функции в документации. Нам понадобится умение
составлять типы функций и небольшое знание английского языка.
Для начала о том, где находится документация к стандартным модулям. Если вы установили ghc вме-
сте с Haskell Platform под Windows скорее всего во вкладке Пуск, там где иконка ghc там же находится
и документация. В Linux необходимо найти директорию с документацией, скорее всего она в директории
/usr/local/share/doc/ghc/libraries. Также документацию можно найти в интернете, наберите в поиско-
вике Haskell Hierarchical Libraries. На главной странице документации вы найдёте огромное количество мо-
дулей. Нас пока интересуют разделы Data и Prelude. Разделы расположены по алфавиту. То что вы видите
это стандартный вид документации в Haskell. Документация делается с помощью специального приложе-
ния Haddock, мы тоже научимся такие делать, но позже, пока мы попробуем разобраться с тем как искать в
документации функции.
Предположим нам нужно вычислить длину списка. Нам нужна функция, которая принимает список и
возвращает целое число, скорее всего её тип [a] -> Int, обычно во всех библиотечных функциях для це-
лых чисел используется тип Int, также на месте параметра используются буквы a, b, c. Мы можем открыть
документацию к Prelude набрать в строке поиска тип [a] -> Int. Или поискать такую функцию в разде-
ле функций для списков List Operations. Тогда мы увидим единственную функцию с таким типом, под
говорящим именем length. Так мы нашли то, что искали.
Или мы ищем функцию, которая переворачивает список, нам нужна функция с типом [a] -> [a]. Таких
функций в Prelude несколько, но имя reverse одной из них может намекнуть на её смысл.
Но одной Prelude мир стандартных функций Haskell не ограничивается, если вы не нашли необходимую
вам функцию в Prelude её стоит поискать в других библиотечных модулях. Обычно функции разделяются
по тому на каких типах они определены. Так например функция sort :: Ord a => [a] -> [a] определена
не в Prelude, а в отдельном библиотечном модуле для списков он называется Data.List. Так же есть много
других модулей для разных типов, таких как Data.Bool, Data.Char, Data.Function, Data.Maybe и многие
другие. Не пугайтесь изобилия модулей постепенно они станут вашей опорой.
Для поиска в стандартных библиотеках есть замечательный интернет-сервис Hoogle (http://www.
haskell.org/hoogle/). Hoogle может искать значения не только по имени, но и по типам. Например мы
хотим узнать целочисленный код символа. Поиск по типу Char -> Int выдаёт искомую функцию digitToInt.
2.8 Краткое содержание
В этой главе мы познакомились с интерпретатором ghci и основными типами. Рассмотрели много при-
меров.
Документация | 37
Типы
Bool
– Основные операции: &&, ||, not, if c then t else e
Char
– Значения пишутся в ординарных кавычках, как в ’H’, ’+’
String
– Значения пишутся в двойных кавычках, как в ”Hello World”
Int
– Эффективные целые числа, но ограниченные
Integer
– Не ограниченные целые числа, но не эффективные
Double
– Числа с двойной точностью
Float
– Числа с ординарной точностью
Rational
– Дробные числа
Нам впервые встретились кортежи (на функции properFraction). Кортежи используются для возвраще-
ния из функции нескольких значений. Элементы кортежа могут иметь разные типы. Для извлечения элемен-
тов из кортежей-пар используются функции fst и snd. Кортежи пишутся в скобках, и элементы разделены
запятыми:
(a, b)
(a, b, c)
(a, b, c, d)
...
Классы
Show
Печать
Eq
Сравнение на равенство
Num
Сложение и умножение
Fractional
Деление
Особенности синтаксиса
Запись применения функции:
Префиксная
Инфиксная
add a b
a ‘add‘ b
(+) a b
a + b
Также мы научились приводить одни численные типы к другим и пользоваться документацией.
2.9 Упражнения
• Напишите функцию beside :: Nat -> Nat -> Bool, которая будет возвращать True только в том случае,
если два аргумента находятся рядом, то есть один из них можно получить через другой операцией Succ.
• Напишите функцию beside2 :: Nat -> Nat -> Bool, которая будет возвращать True только если
аргументы являются соседями через некоторое другое число.
• Мы написали очень неэффективную функцию сложения натуральных чисел. Проблема в том, что число
рекурсивных вызовов функции зависит от величины второго аргумента. Если мы захотим прибавить
единицу к сотне, то порядок следования аргументов существенно повлияет на скорость вычисления.
Напишите функцию, которая лишена этого недостатка.
• Напишите функцию возведения в степень pow :: Nat -> Nat -> Nat.
• Напишите тип, описывающий бинарные деревья BinTree a. Бинарное дерево может быть либо листом
со значением типа a, либо хранить два поддерева.
• Напишите функцию reverse :: BinTree a -> BinTree a, которая переворачивает дерево. Она меняет
местами два элемента в узле дерева.
• Напишите функцию depth :: BinTree a -> Nat, которая вычисляет глубину дерева, то есть самый
длинный путь от корня дерева к листу.
38 | Глава 2: Первая программа
• Напишите функцию leaves :: BinTree a -> [a], которая переводит бинарное дерево в список, воз-
вращая все элементы в листьях дерева.
• Обратите внимание на раздел List Operations в Prelude. Посмотрите на функции и их типы. Попро-
буйте догадаться по типу функции и названию что она делает.
• Попробуйте разобраться по документации с классами Ord (сравнение на больше/меньше), Enum (пере-
числения) и Integral (целые числа). Также стоит отметить класс Floating. Если у вас не получится,
не беда, они обязательно встретятся нам вновь. Там и разберёмся.
• Найдите функцию, которая переставляет элементы пары местами (элементы могут быть разных типов).
Потренируйтесь с кортежами. Определите аналоги функций fst и snd для не пар. Обратите внимание
на то, что сочетание символов (,) это функция-конструктор пары:
Prelude> (,) ”Hi” 101
(”Hi”,101)
Prelude> :t (,)
(,) :: a -> b -> (a, b)
Также определены („), („,) и другие.
Упражнения | 39
Глава 3
Типы
С помощью типов мы определяем все возможные значения в нашей программе. Мы определяем основные
примитивы и способы их комбинирования. Например в типе Nat:
data Nat = Zero | Succ Nat
Один конструктор-примитив Zero, и один конструктор Succ, с помощью которого мы можем делать со-
ставные значения. Определив тип Nat таким образом, мы говорим, что значения типа Nat могут быть только
такими:
Zero,
Succ Zero,
Succ (Succ Zero), Succ (Succ (Succ Zero)), ...
Все значения являются цепочками Succ с Zero на конце. Если где-нибудь мы попытаемся построить значе-
ние, которое не соответствует нашему типу, мы получим ошибку компиляции, то есть программа не пройдёт
проверку типов. Так типы описывают множество допустимых значений.
Значения, которые проходят проверку типов мы будем называть допустимыми, а те, которые не проходят
соответственно недопустимыми. Так например следующие значения недопустимы для Nat
Succ Zero Zero,
Succ Succ, True, Zero (Zero Succ), ...
Недопустимых значений конечно гораздо больше. Такое проявляется и в естественном языке, бессмыс-
ленных комбинаций слов гораздо больше, чем осмысленных предложений. Обратите внимание на то, что мы
говорим о значениях (не)допустимых для некоторого типа, например значение True допустимо для Bool, но
недопустимо для Nat.
Сами типы строятся не произвольным образом. Мы узнали, что при их построении используются две ос-
новные операции, это сумма и произведение типов. Это говорит о том, что в типах должны быть какие-то
закономерности, которые распространяются на все значения. В этой главе мы посмотрим на эти закономер-
ности.
3.1 Структура алгебраических типов данных
Итак у нас лишь две операции: сумма и произведение. Давайте для начала рассмотрим два крайних
случая.
• Только произведение типов
data T = Name T1 T2 ... TN
Мы говорим, что значение нашего нового типа T состоит из значений типов T1, T2, … , TN и у нас есть
лишь один способ составить значение этого типа. Единственное, что мы можем сделать это применить
к значениям типов Ti конструктор Name.
Пример:
data Time = Time Hour Second Minute
• Только сумма типов
data T = Name1 | Name2 | ... | NameN
40 | Глава 3: Типы
Мы говорим, что у нашего нового типа T может быть лишь несколько значений, и перечисляем их в
альтернативах через знак |.
Пример:
data Bool = True | False
Сделаем первое наблюдение: каждое произведение типов определяет новый конструктор. Число кон-
структоров в типе равно числу альтернатив. Так в первом случае у нас была одна альтернатива и следова-
тельно у нас был лишь один конструктор Name.
Имена конструкторов должны быть уникальными в пределах модуля. У нас нет таких двух типов, у ко-
торых совпадают конструкторы. Это говорит о том, что по имени конструктора компилятор знает значение
какого типа он может построить.
Произведение типов состоит из конструктора, за которым через пробел идут подтипы. Такая структура
не случайна, она копирует структуру функции. В качестве имени функции выступает конструктор, а в ка-
честве аргументов – значения заданных в произведении подтипов. Функция-конструктор после применения
“оборачивает” значения аргументов и создаёт новое значение. За счёт этого мы могли бы определить типы
по-другому. Мы могли бы определить их в стиле классов типов:
data Bool where
True
:: Bool
False :: Bool
Мы видим “класс” Bool, у которого два метода. Или определим в таком стиле Nat:
data Nat where
Zero
:: Nat
Succ
:: Nat -> Nat
Мы переписываем подтипы по порядку в аргументы метода. Или определим в таком стиле списки:
data [a] where
[]
:: [a]
(:)
:: a -> [a] -> [a]
Конструктор пустого списка [] является константой, а конструктор объединения элемента со списком
(:), является функцией. Когда я говорил, что типы определяют примитивы и методы составления из прими-
тивов, я имел ввиду, что некоторые конструкторы по сути являются константами, а другие функциями.
Эти “методы” определяют базовые значения типа, все другие значения будут комбинациями базовых.
При этом сумма типов, определяет число методов “классе” типа, то есть число базовых значений, а произ-
ведение типов в каждой альтернативе определяет имя метода (именем конструктора) и состав аргументов
(перечислением подтипов).
3.2 Структура констант
Мы уже знаем, что значения могут быть функциями и константами. Объявляя константу, мы даём имя-
синоним некоторой комбинации базовых конструкторов. В функции мы говорим как по одним значениям
получить другие. В этом и следующем разделе мы посмотрим на то, как типы определяют структуру констант
и функций.
Давайте присмотримся к константам:
Succ (Succ Zero)
Neg (Add One (Mul Six Ten))
Not (Follows A (And A B))
Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))
Заменим все функциональные конструкторы на букву f (от слова function), а все примитивные конструк-
торы на букву c (от слова constant).
f (f c)
f (f c (f c c))
f (f c (f c c))
f c (f c (f c (f c c)))
Те кто знаком с теорией графов, возможно уже узнали в этой записи строчную запись дерева. Все зна-
чения в Haskell являются деревьями. Узел дерева содержит составной конструктор, а лист дерева содержит
примитивный конструктор. Далее будет небольшой подраздел посвящённый терминологии теории графов,
которая нам понадобится, будет много картинок, если вам это известно, то вы можете спокойно его пропу-
стить.
Структура констант | 41
Несколько слов о теории графов
Если вы не знакомы с теорией графов, то сейчас как раз самое время с ней познакомится, хотя бы на
уровне основных терминов. Теория графов изучает дискретные объекты в терминах зависимостей между
ТЕЛЕГРАМКанал с обзорами, анонсами новинок и книжными подборками
Книжный Вестник
Бот для удобного поиска книг (если не нашлось на сайте)
Поиск книг
Свежие любовные романы в удобных форматах
Любовные романы
О психологии, саморазвитии и личностном росте
Саморазвитие
Детективы и триллеры, все новинки
Детективы
Фантастика и фэнтези, все новинки
Фантастика
Отборные классические книги
Классика
ВКОНТАКТЕБиблиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории
Любовные романы
Библиотека с фантастикой и фэнтези, а также смежных жанров
Фантастика
Самые популярные книги в формате фб2
Топ фб2
книги