Справочник по языку Haskell

Справочник

по языку Haskell

Душкин Р. В.

Москва

УДК
004.4

ББК
32.973.26018.2
Д86

Душкин Р. В.

Д86
Справочник по языку Haskell. М.: ДМК Пресс, 544 с., ил.

ISBN 5940744109

Данная книга является первой книгой на русском языке, описывающей

набор стандартных библиотек функционального языка программирования
Haskell. В первой xасти книги кратко рассматривается синтаксис языка и
способы его применения для решения задач. Во второй части описываются
стандартные библиотеки языка, входящие в поставки всех современных
трансляторов Haskell (GHC, HUGS и др.).

Книга станет прекрасным подспорьем для программистов, занимающихся прикладным программированием на языке Haskell, а также для студентов, изучающих функциональное программирование.

УДК 004.4
ББК 32.973.26018.2

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то

ни было форме и какими бы то ни было средствами без письменного разрешения владельцев
авторских прав.

Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность

технических ошибок все равно существует, издательство не может гарантировать абсолютную
точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

© Душкин Р. В.

ISBN 594074© Оформление ДМК Пресс
410 9

Оглавление

Введение
9

I.
Синтаксис и идиомы языка
11

1. Функции
12

1.1. Общий вид определения функций . . . . . . . . . . . . . . . . . . . .
12

1.1.1.
Детальный разбор нескольких примеров
определения функций
. . . . . . . . . . . . . . . . . . . . . .
13

1.1.2.
Ветвление
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16

1.1.3.
Замыкания . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17

1.1.4.
Бинарные операции . . . . . . . . . . . . . . . . . . . . . . . .
20

1.2. Технология сопоставления с образцами
. . . . . . . . . . . . . . . .
23

1.2.1.
Образцы вида (n + k) . . . . . . . . . . . . . . . . . . . . . . .
25

1.2.2.
Именованные образцы
. . . . . . . . . . . . . . . . . . . . . .
26

1.2.3.
Ленивые образцы . . . . . . . . . . . . . . . . . . . . . . . . .
27

1.3. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28

1.3.1.
Действия ввода/вывода
. . . . . . . . . . . . . . . . . . . . .
28

1.3.2.
Обработка исключений . . . . . . . . . . . . . . . . . . . . . .
32

1.4. Приёмы программирования . . . . . . . . . . . . . . . . . . . . . . .
34

1.4.1.
Двумерный синтаксис
. . . . . . . . . . . . . . . . . . . . . .
34

1.4.2.
Рекурсия и корекурсия . . . . . . . . . . . . . . . . . . . . . .
35

1.4.3.
Накапливающий параметр и хвостовая рекурсия . . . . . . .
39

1.4.4.
Бесточечная нотация . . . . . . . . . . . . . . . . . . . . . . .
41

1.4.5.
Анонимные функции . . . . . . . . . . . . . . . . . . . . . . .
42

Оглавление

1.4.6.
Охрана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

1.4.7.
Определители списков . . . . . . . . . . . . . . . . . . . . . .
46

2. Типы данных
48

2.1. Базовые типы
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48

2.1.1.
Кортежи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49

2.1.2.
Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51

2.2. Кратко об алгебраических типах данных
. . . . . . . . . . . . . . .
53

2.2.1.
Перечисления
. . . . . . . . . . . . . . . . . . . . . . . . . . .
54

2.2.2.
Простые структуры . . . . . . . . . . . . . . . . . . . . . . . .
56

2.2.3.
Именованные поля
. . . . . . . . . . . . . . . . . . . . . . . .
59

2.3. Синонимы типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61

2.4. Параметрический полиморфизм . . . . . . . . . . . . . . . . . . . . .
63

2.5. Типы функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64

2.5.1.
Функции как программные сущности с типом
. . . . . . . .
64

2.5.2.
Каррирование и частичное применение
. . . . . . . . . . . .
66

2.5.3.
Функции высшего порядка . . . . . . . . . . . . . . . . . . . .
68

3. Классы типов и экземпляры классов
71

3.1. Класс как интерфейс . . . . . . . . . . . . . . . . . . . . . . . . . . .
71

3.2. Контекст и прикладные функции . . . . . . . . . . . . . . . . . . . .
76

3.3. Экземпляр — связь между типом и классом . . . . . . . . . . . . . .
78

3.3.1.
Экземпляры класса Logic . . . . . . . . . . . . . . . . . . . .
80

3.4. Изоморфные типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83

3.4.1.
Определение нескольких экземпляров
для уникальной пары (класс, тип) . . . . . . . . . . . . . . .
85

3.5. Автоматическое построение экземпляров
. . . . . . . . . . . . . . .
86

3.6. Окончательные замечания о системе типов в языке Haskell . . . . .
88

4. Модули
91

4.1. Система модулей
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91

4.1.1.
Экспорт программных сущностей . . . . . . . . . . . . . . . .
92

4.1.2.
Импорт сторонних модулей
. . . . . . . . . . . . . . . . . . .
93

4.2. Абстракция данных при помощи модулей . . . . . . . . . . . . . . .
97

4.3. Кое-что ещё о модулях . . . . . . . . . . . . . . . . . . . . . . . . . .
98

Оглавление
5

5. Сводная информация
100

II.
Стандартные библиотеки
105

6. Стандартный модуль Prelude
108

6.1. Prelude: Алгебраические типы данных
. . . . . . . . . . . . . . . . 108

6.2. Prelude: Классы и их экземпляры
. . . . . . . . . . . . . . . . . . . 115

6.3. Prelude: Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.4. Prelude: Операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

7. Пакет модулей Control
172

7.1. Модуль Applicative
. . . . . . . . . . . . . . . . . . . . . . . . . . . 172

7.2. Модуль Arrow
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

7.3. Модуль Concurrent . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

7.3.1.
Модуль Chan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

7.3.2.
Модуль MVar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

7.3.3.
Модуль QSem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

7.3.4.
Модуль QSemN
. . . . . . . . . . . . . . . . . . . . . . . . . . . 193

7.3.5.
Модуль SampleVar . . . . . . . . . . . . . . . . . . . . . . . . . 194

7.4. Модуль Exception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.5. Модуль Monad
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

7.5.1.
Модуль Fix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

7.5.2.
Модуль Instances . . . . . . . . . . . . . . . . . . . . . . . . . 222

7.5.3.
Модуль ST
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

7.6. Модуль Parallel
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

8. Пакет модулей Data
226

8.1. Модуль Array
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

8.1.1.
Модуль Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

8.1.2.
Модуль Diff . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

8.1.3.
Модуль IArray . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

8.1.4.
Модуль IO
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

8.1.5.
Модуль MArray . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

8.1.6.
Модуль ST
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

8.1.7.
Модуль Storable
. . . . . . . . . . . . . . . . . . . . . . . . . 243

Оглавление

8.1.8.
Модуль Unboxed . . . . . . . . . . . . . . . . . . . . . . . . . . 245

8.2. Модуль Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.3. Модуль Bool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.4. Модуль ByteString . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

8.4.1.
Модуль Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

8.4.2.
Модуль Char8
. . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.4.3.
Модуль Lazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

8.5. Модуль Char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
8.6. Модуль Complex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
8.7. Модуль Dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8.8. Модуль Either . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
8.9. Модуль Eq
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

8.10. Модуль Fixed
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

8.11. Модуль Foldable
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

8.12. Модуль Graph
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

8.13. Модуль HashTable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
8.14. Модуль Int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
8.15. Модуль IntMap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
8.16. Модуль IntSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
8.17. Модуль IORef
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

8.18. Модуль Ix
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

8.19. Модуль List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
8.20. Модуль Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
8.21. Модуль Maybe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

8.22. Модуль Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
8.23. Модуль Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
8.24. Модуль Ratio
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

8.25. Модуль Sequence
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

8.26. Модуль Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
8.27. Модуль STRef
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

8.27.1. Модуль Lazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
8.27.2. Модуль Strict . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

8.28. Модуль Traversable
. . . . . . . . . . . . . . . . . . . . . . . . . . . 402

8.29. Модуль Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
8.30. Модуль Tuple
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Оглавление
7

8.31. Модуль Typeable
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

8.32. Модуль Unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
8.33. Модуль Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
8.34. Модуль Word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

9. Пакет модулей Debug
419

9.1. Модуль Trace
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

10.Пакет модулей Foreign
421

10.1. Модуль C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

10.1.1. Модуль Error
. . . . . . . . . . . . . . . . . . . . . . . . . . . 423

10.1.2. Модуль String . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
10.1.3. Модуль Types
. . . . . . . . . . . . . . . . . . . . . . . . . . . 436

10.2. Модуль ForeignPtr . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
10.3. Модуль Marshal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

10.3.1. Модуль Alloc
. . . . . . . . . . . . . . . . . . . . . . . . . . . 445

10.3.2. Модуль Array
. . . . . . . . . . . . . . . . . . . . . . . . . . . 447

10.3.3. Модуль Error
. . . . . . . . . . . . . . . . . . . . . . . . . . . 453

10.3.4. Модуль Pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
10.3.5. Модуль Utils
. . . . . . . . . . . . . . . . . . . . . . . . . . . 459

10.4. Модуль Ptr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
10.5. Модуль StablePtr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
10.6. Модуль Storable
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468

11.Пакет модулей System
471

11.1. Модуль Cmd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
11.2. Модуль CPUTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
11.3. Модуль Directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473

11.3.1. Модуль Internals . . . . . . . . . . . . . . . . . . . . . . . . . 482

11.4. Модуль Environment
. . . . . . . . . . . . . . . . . . . . . . . . . . . 482

11.5. Модуль Exit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
11.6. Модуль Info . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
11.7. Модуль IO
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

11.7.1. Модуль Error
. . . . . . . . . . . . . . . . . . . . . . . . . . . 497

11.7.2. Модуль Unsafe . . . . . . . . . . . . . . . . . . . . . . . . . . . 507

11.8. Модуль Locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507

Оглавление

11.9. Модуль Mem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

11.9.1. Модуль StableName . . . . . . . . . . . . . . . . . . . . . . . . 510
11.9.2. Модуль Weak . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512

11.10.Модуль Random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
11.11.Модуль Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519

12.Пакет модулей Text
528

12.1. Модуль Printf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
12.2. Модуль Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

12.2.1. Модуль Lex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533

12.3. Модуль Show . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

12.3.1. Модуль Functions . . . . . . . . . . . . . . . . . . . . . . . . . 536

Заключение
537

Литература
538

Введение

Язык Haskell является динамично развивающимся функциональным языком

программирования, который получает всё больше и больше сторонников во всём
мире, в том числе и в России. Этот язык вырвался из рамок научных лабораторий и стал языком программирования общего назначения. Вместе с тем хорошей
литературы об этом прекрасном языке программирования категорически мало,
тем более на русском языке.

В конце 2006 года из печати вышла первая и на текущий момент (2007 год)

единственная книга на русском языке, рассматривающая функциональное программирование на языке Haskell [1]. Несмотря на то что в этой книге тема языка
Haskell раскрыта практически полностью, его описание в ней страдает неполнотой и некоторой «поверхностностью». С другой стороны, достаточно серьёзная
математика в книге немного отпугивает неподготовленного читателя. Поэтому
книга явилась своеобразным «первым блином», который необходим для первоначального ввода в проблематику. Однако в связи с ростом популярности как
языка Haskell, так и парадигмы функционального программирования, необходимо больше всевозможных материалов, охватывающих различные аспекты и предназначенных для разной целевой аудитории.

Данная книга является кратким справочником по функциональному языку

программирования Haskell стандарта Haskell-98 (без описания многочисленных
расширений языка). В книге собрано описание знаний по успешному применению
языка Haskell на практике. Она предназначена для тех, кто уже знает принципы
функциональной парадигмы и сам язык Haskell. Это связано с тем, что, несмотря
на то что практически всю информацию можно почерпнуть из интернета, очень
часто необходимо иметь под рукой полноценный справочник, в котором мож

Введение

но быстро найти ответы на специализированные вопросы. И эта книга как раз
и предназначена для подобных целей.

Поскольку книга названа «кратким справочником», одним из принципов, ко
торым руководствовался автор при её написании, является минимизация информации и предоставление компактно выраженных знаний, с достаточной степенью
полноты раскрывающих смысл конструкций языка Haskell, идиом, существующих функций и других программных объектов, определённых в стандартных
библиотеках. Поэтому стиль этого справочника является более или менее сухим
и выдержанным, а описание программных сущностей наиболее формализованным.

Справочник разбит на две части. В первой части представлено краткое опи
сание синтаксиса языка Haskell, а также наиболее часто и успешно используемые
техники программирования на нём (ведь не секрет, что в каждом языке имеются
свои особые методы «правильного» программирования). Во второй части описываются наиболее часто использующиеся стандартные модули, входящие в поставку двух наиболее известных трансляторов языка — HUGS 98 и GHC. Первая
часть разбита на главы, каждая из которых описывает одну из пяти существующих в языке программных сущностей (и дополнительная шестая глава со сводной информацией). Главы второй части соответствуют стандартным библиотекам
языка Haskell.

В целях единообразия представления информации в книге используется спе
циальное форматирование текста, выделяющее определённые структурные элементы. Так, наименования программных сущностей выделяются моноширинным
шрифтом обычного начертания: head, True, Enum и т. д. В отличие от идентификаторов ключевые слова записываются моноширинным шрифтом с подчёркиванием: if, do, instance и т. д. Знаки операций и специальные символы при записи
ограничиваются круглыми скобками, чтобы выделить и отделить знаки от основного текста: (+), (>=), (‘) и т. д., в то время как сами скобки в случае необходимости записываются в кавычках: «(», «]». Кроме того, наименования модулей,
библиотек и специальных утилит также записываются моноширинным шрифтом:
Prelude, Data.List и пр.

Краткость — сестра таланта, как говаривал русский классик А. П. Чехов.

Поэтому осталось только упомянуть, что автор чрезвычайно благодарен Роганову В. А. за помощь в создании книги, и то, что автор будет рад получить
комментарии и замечания по адресу электронной почты darkus.14@gmail.com.