Учебник по Haskell

корнем. Все наши стрелки будут идти от корня. Сначала мы проведём стрелки к узлам связанным с корнем:

Затем представим, что каждый из этих узлов сам является корнем в своём дереве и повторим эту процеду-

ру. На этом шаге мы дорисовываем стрелки в поддеревьях, которые находятся в узлах 3 и 6. Узел 5 является

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

А невырожденные поддеревья мы будем называть узлами. Корневой узел в данном поддереве называют ро-

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

узлами. На предыдущем шаге у нас появился один родительский узел 1, у которого три дочерних узла: 3, 6,

и 5. А на этом шаге у нас появились ещё два родительских узла 3 и 6. У узла 3 один дочерний узел (4), а у

узла 6 – три дочерних узла (2, 8, 7).

Отметим, что положение узлов и рёбер на картинке не важно, главное это то, какие рёбра какие узлы

соединяют. Мы можем перерисовать это дерево в более привычном виде (рис. 3.4).

Теперь если вы посмотрите на константы в Haskell вы заметите, что очень похожи на деревья. Листья со-

держат примитивные конструкторы, а узлы – составные. Это происходит из-за того, что каждый конструктор

содержит метку и набор подтипов. В этой аналогии метки становятся узлами, а подтипы-аргументы стано-

вятся поддеревьями.

42 | Глава 3: Типы

8

7

c

f

6

a

b

d

5

1

2

g

h

3

4

Рис. 3.2: Превращаем в дерево

8

7

c

f

6

a

b

d

5

1

2

g

h

3

4

Рис. 3.3: Превращаем в дерево...

Но есть одна тонкость, в которой заключается отличие констант Haskell от деревьев из теории графов. В

теории графов порядок поддеревьев не важен, мы могли бы нарисовать поддеревья в любом порядке, главное

сохранить связи. А в Haskell порядок следования аргументов в конструкторе важен.

На следующем рисунке (рис. 3.5) изображены две константы:

Succ (Succ Zero) :: Nat и Neg (Add One (Mul Six Ten)) :: Expr. Но они изображены немного по-другому.

Я перевернул стрелки и добавил корнем ещё один узел, это тип константы.

Стрелки перевёрнуты так, чтобы стрелки на картинке соответствовали стрелкам в типе конструктора.

Например по виду узла Succ :: Nat -> Nat, можно понять, что это функция от одного аргумента, в неё

впадает одна стрелка-аргумент и вытекает одна стрелка-значение. В конструктор Mul впадает две стрелки,

значит это конструктор-функция от двух аргументов.

Константы похожи на деревья за счёт структуры операции произведения типов. В произведении типов

мы пишем:

data Tnew = Name T1 T2 ... Tn

Структура констант | 43

1

g

d

a

3

5

6

h

b

f

c

4

2

7

8

Рис. 3.4: Ориентированное дерево

Expr

Nat

Neg

Succ

Add

Succ

One

Mul

Zero

Six

Ten

Рис. 3.5: Константы

Так и получается, что у нашего узла New одна вытекающая стрелка, которая символизирует значение типа

Tnew и несколько впадающих стрелок T1, T2, …, Tn, они символизируют аргументы конструктора.

Потренируйтесь изображать константы в виде деревьев, вспомните константы из предыдущей главы, или

придумайте какие-нибудь новые.

Строчная запись деревьев

Итак все константы в Haskell за счёт особой структуры построения типов являются деревьями, но мы

программируем в текстовом редакторе, а не в редакторе векторной графики, поэтому нам нужен удобный

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

Мы сидим на корне дерева и спускаемся по его вершинам. Нам могут встретиться вершины двух типов

узлы и листья. Сначала мы пишем имя в текущем узле, затем через пробел имена в дочерних узлах, если нам

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

записи дерево из первого примера:

Начнём с корня и будем последовательно дописывать поддеревья, точками обозначаются дочерние узлы,

которые нам ещё предстоит дописать:

(1

.

.

.

)

(1

(3 . )

5

(6 . . . ))

(1

(3 4)

5

(6 2 7 8))

44 | Глава 3: Типы

1

3

5

6

4

2

7

8

Рис. 3.6: Ориентированное дерево

Мы можем ставить любое число пробелов между дочерними узлами, здесь для наглядности точки вы-

ровнены. Так мы можем закодировать исходное дерево строкой. Часто самые внешние скобки опускаются. В

итоге получилась такая запись:

tree = 1 (3 4) 5 (6 2 7 8)

По этой записи мы можем понять, что у нас есть два конструктора трёх аргументов 1 и 6, один конструктор

одного аргумента 3 и пять примитивных конструкторов. Точно так же мы строим и все другие константы в

Haskell:

Succ (Succ (Succ Zero))

Time (Hour 13) (Minute 10) (Second 0)

Mul (Add One Ten) (Neg (Mul Six Zero))

За одним исключением, если конструктор бинарный, символьный (начинается с двоеточия), мы помеща-

ем его между аргументов:

(One :+ Ten) :* (Neg (Six :* Zero))

3.3 Структура функций

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

новое имя, пусть и составное. Мы можем написать 5, или 2+3, это лишь два разных имени для одной кон-