Unknown - haskell-notes

и функций.

Давайте присмотримся к константам:

Succ( Succ Zero)

Neg( Add One( Mul Six Ten))

Not( Follows A( And A B))

Cons1 ( Cons2 ( Cons3 ( Cons4 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

Несколько слов о теории графов

Если вы не знакомы с теорией графов, то сейчас как раз самое время с ней познакомится, хотя бы на

уровне основных терминов. Теория графов изучает дискретные объекты в терминах зависимостей между

объектами или связей. При этом объекты и связи можно изобразить графически.

Граф состоит из узлов и рёбер , которые соединяют узлы. Приведём пример графа:

8

7

c

f

6

a

b

d

e

5

1

2

g

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: Превращаем в дерево