Учебник по Haskell - [24]

сохранить связи. А в 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, они символизируют аргументы конструктора.

Потренируйтесь изображать константы в виде деревьев, вспомните константы из предыдущей главы, или

придумайте какие-нибудь новые.

Строчная запись деревьев

Итак все константы в 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)

Смотрите в этой функции слева от знака равно мы проводим декомпозицию второго аргумента, а в правой

части мы составляем новое дерево из тех значений, что были нами получены слева от знака равно. Или

посмотрим на другой пример:

show (Time h m s) = show h ++ ”:” ++ show m ++ ”:” ++ show s

Слева от знака равно мы также выделили из составного дерева (Time h m s) три его дочерних для корня

узла и связали их с переменными h, m и s. А справа от знака равно мы составили из этих переменных новое

выражение.

Итак операцию объявления синонима можно представить в таком виде:

name

декомпозиция

=

композиция

В каждом уравнении у нас три части: новое имя, декомпозиция, поступающих на вход аргументов, и

композиция нового значения. Теперь давайте остановимся поподробнее на каждой из этих операций.

Структура функций | 45

Композиция и частичное применение

Композиция строится по очень простому правилу, если у нас есть значение f типа a -> b и значение x

типа a, мы можем получить новое значение (f x) типа b. Это основное правило построения новых значений,

поэтому давайте запишем его отдельно:

f :: a -> b,

x :: a

--------------------------

(f x) :: b

Сверху от черты, то что у нас есть, а снизу от черты то, что мы можем получить. Это операция называется

применением или аппликацией.

Выражения, полученные таким образом, напоминают строчную запись дерева, но есть одна тонкость, ко-

торую мы обошли стороной. В случае деревьев мы строили только константы, и конструктор получал столько