Учебник по Haskell

Сделаем первое наблюдение: каждое произведение типов определяет новый конструктор. Число кон-

структоров в типе равно числу альтернатив. Так в первом случае у нас была одна альтернатива и следова-

тельно у нас был лишь один конструктор Name.

Имена конструкторов должны быть уникальными в пределах модуля. У нас нет таких двух типов, у ко-

торых совпадают конструкторы. Это говорит о том, что по имени конструктора компилятор знает значение

какого типа он может построить.

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

не случайна, она копирует структуру функции. В качестве имени функции выступает конструктор, а в ка-

честве аргументов – значения заданных в произведении подтипов. Функция-конструктор после применения

“оборачивает” значения аргументов и создаёт новое значение. За счёт этого мы могли бы определить типы

по-другому. Мы могли бы определить их в стиле классов типов:

data Bool where

True

:: Bool

False :: Bool

Мы видим “класс” Bool, у которого два метода. Или определим в таком стиле Nat:

data Nat where

Zero

:: Nat

Succ

:: Nat -> Nat

Мы переписываем подтипы по порядку в аргументы метода. Или определим в таком стиле списки:

data [a] where

[]

:: [a]

(:)

:: a -> [a] -> [a]

Конструктор пустого списка [] является константой, а конструктор объединения элемента со списком

(:), является функцией. Когда я говорил, что типы определяют примитивы и методы составления из прими-

тивов, я имел ввиду, что некоторые конструкторы по сути являются константами, а другие функциями.

Эти “методы” определяют базовые значения типа, все другие значения будут комбинациями базовых.

При этом сумма типов, определяет число методов “классе” типа, то есть число базовых значений, а произ-

ведение типов в каждой альтернативе определяет имя метода (именем конструктора) и состав аргументов

(перечислением подтипов).

3.2 Структура констант

Мы уже знаем, что значения могут быть функциями и константами. Объявляя константу, мы даём имя-

синоним некоторой комбинации базовых конструкторов. В функции мы говорим как по одним значениям

получить другие. В этом и следующем разделе мы посмотрим на то, как типы определяют структуру констант

и функций.

Давайте присмотримся к константам:

Succ (Succ Zero)

Neg (Add One (Mul Six Ten))

Not (Follows A (And A B))

Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))

Заменим все функциональные конструкторы на букву f (от слова function), а все примитивные конструк-

торы на букву c (от слова constant).

f (f c)

f (f c (f c c))

f (f c (f c c))

f c (f c (f c (f c c)))

Те кто знаком с теорией графов, возможно уже узнали в этой записи строчную запись дерева. Все зна-

чения в Haskell являются деревьями. Узел дерева содержит составной конструктор, а лист дерева содержит

примитивный конструктор. Далее будет небольшой подраздел посвящённый терминологии теории графов,

которая нам понадобится, будет много картинок, если вам это известно, то вы можете спокойно его пропу-

стить.

Структура констант | 41

Несколько слов о теории графов

Если вы не знакомы с теорией графов, то сейчас как раз самое время с ней познакомится, хотя бы на

уровне основных терминов. Теория графов изучает дискретные объекты в терминах зависимостей между

объектами или связей. При этом объекты и связи можно изобразить графически.

Граф состоит из узлов и рёбер, которые соединяют узлы. Приведём пример графа:

8

7

c

f

6

a

b

d

e

5

1

2

g

h

3

4

Рис. 3.1: Граф

В этом графе восемь узлов, они пронумерованы, и восемь рёбер, они обозначены буквами. Теорию графов

придумал Леонард Эйлер, когда решал задачу о кёнингсбергских мостах. Он решал задачу о том, можно ли

обойти все семь кёнингсбергских мостов так, чтобы пройти по каждому лишь один раз. Эйлер представил

мосты в виде рёбер а участки суши в виде узлов графа и показал, что это сделать нельзя. Но мы отвлеклись.

А что такое дерево? Дерево это такой связанный граф, у которого нет циклов. Несвязанный граф образует

несколько островков, или множеств узлов, которые не соединены рёбрами. Циклы – это замкнутые последо-

вательности рёбер. Например граф на рисунке выше не является деревом, но если мы сотрём ребро e, то у

нас получится дерево.

Ориентированный граф – это такой граф, у которого все рёбра являются стрелками, они ориентированы,

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

ентированных деревьях обычно выделяют один узел, который называют корнем. Его особенность заключается

в том, что все стрелки в ориентированном дереве как бы “разбегаются” от корня или сбегаются к корню. Ко-

рень определяет все стрелки в дереве. Ориентированное дерево похоже на иерархию. У нас есть корневой

элемент и набор его дочерних поддеревьев, каждое из поддеревьев в свою очередь является ориентирован-

ным деревом и так далее. Проиллюстрируем на картинке, давайте сотрём ребро e и назначим первый узел