h
3
4
Рис. 3.1: Граф
В этом графе восемь узлов, они пронумерованы, и восемь рёбер, они обозначены буквами. Теорию графов
придумал Леонард Эйлер, когда решал задачу о кёнингсбергских мостах. Он решал задачу о том, можно ли
обойти все семь кёнингсбергских мостов так, чтобы пройти по каждому лишь один раз. Эйлер представил
мосты в виде рёбер а участки суши в виде узлов графа и показал, что это сделать нельзя. Но мы отвлеклись.
А что такое дерево? Дерево это такой связанный граф, у которого нет циклов. Несвязанный граф образует
несколько островков, или множеств узлов, которые не соединены рёбрами. Циклы – это замкнутые последо-
вательности рёбер. Например граф на рисунке выше не является деревом, но если мы сотрём ребро 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 одна вытекающая стрелка, которая символизирует значение типа