Unknown - haskell-notes

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

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

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

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

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

Mul( Add One Ten) ( Neg( Mul Six Zero))

За одним исключением, если конструктор бинарный, символьный (начинается с двоеточия), мы помеща-

ем его между аргументов:

( One :+ Ten) :*( Neg( Six :* Zero))

3.3 Структура функций

Функции описывают одни значения в терминах других. При этом важно понимать, что функция это лишь

новое имя, пусть и составное. Мы можем написать 5, или 2 +3, это лишь два разных имени для одной кон-

станты. Теперь мы разобрались с тем, что константы это деревья. Значит функции строят одни деревья из

других. Как они это делают? Для этого этого в Haskell есть две операции: это композиция и декомпозиция де-

ревьев. С помощью композиции мы строим из простых деревьев сложные, а с помощью декомпозиции разбиваем

составные деревья на простейшие.

Композиция и декомпозиция объединены в одной операции, с которой мы уже встречались, это операция

определения синонима. Давайте вспомним какое-нибудь объявление функции: