придумайте какие-нибудь новые.
Строчная запись деревьев
Итак все константы в 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 и пять примитивных конструкторов. Точно так же мы строим и все другие константы в
Haskell:
Succ (Succ (Succ Zero))
Time (Hour 13) (Minute 10) (Second 0)
Mul (Add One Ten) (Neg (Mul Six Zero))
За одним исключением, если конструктор бинарный, символьный (начинается с двоеточия), мы помеща-
ем его между аргументов:
(One :+ Ten) :* (Neg (Six :* Zero))
3.3 Структура функций
Функции описывают одни значения в терминах других. При этом важно понимать, что функция это лишь
новое имя, пусть и составное. Мы можем написать 5, или 2+3, это лишь два разных имени для одной кон-
станты. Теперь мы разобрались с тем, что константы это деревья. Значит функции строят одни деревья из
других. Как они это делают? Для этого этого в Haskell есть две операции: это композиция и декомпозиция де-
ревьев. С помощью композиции мы строим из простых деревьев сложные, а с помощью декомпозиции разбиваем
составные деревья на простейшие.
Композиция и декомпозиция объединены в одной операции, с которой мы уже встречались, это операция
определения синонима. Давайте вспомним какое-нибудь объявление функции:
(+) a
Zero
= a
(+) a
(Succ b)
= Succ (a + b)
Смотрите в этой функции слева от знака равно мы проводим декомпозицию второго аргумента, а в правой
