.
А невырожденные поддеревья мы будем называть узлами. Корневой узел в данном поддереве называют ро-
дительским. А его соседние узлы, в которые направлены исходящие из него стрелки называют дочерними
узлами. На предыдущем шаге у нас появился один родительский узел 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, они символизируют аргументы конструктора.
Потренируйтесь изображать константы в виде деревьев, вспомните константы из предыдущей главы, или
