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