вательности рёбер. Например граф на рисунке выше не является деревом, но если мы сотрём ребро e, то у
нас получится дерево.
Ориентированный граф – это такой граф, у которого все рёбра являются стрелками, они ориентированы,
отсюда и название. При этом теперь каждое ребро не просто связывает узлы, но имеет начало и конец. В ори-
ентированных деревьях обычно выделяют один узел, который называют корнем. Его особенность заключается
в том, что все стрелки в ориентированном дереве как бы “разбегаются” от корня или сбегаются к корню. Ко-
рень определяет все стрелки в дереве. Ориентированное дерево похоже на иерархию. У нас есть корневой
элемент и набор его дочерних поддеревьев, каждое из поддеревьев в свою очередь является ориентирован-
ным деревом и так далее. Проиллюстрируем на картинке, давайте сотрём ребро e и назначим первый узел
корнем. Все наши стрелки будут идти от корня. Сначала мы проведём стрелки к узлам связанным с корнем:
Затем представим, что каждый из этих узлов сам является корнем в своём дереве и повторим эту процеду-
ру. На этом шаге мы дорисовываем стрелки в поддеревьях, которые находятся в узлах 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 и пять примитивных конструкторов. Точно так же мы строим и все другие константы в