если два аргумента находятся рядом, то есть один из них можно получить через другой операцией Succ.
• Напишите функцию beside2 :: Nat -> Nat -> Bool, которая будет возвращать True только если
аргументы являются соседями через некоторое другое число.
• Мы написали очень неэффективную функцию сложения натуральных чисел. Проблема в том, что число
рекурсивных вызовов функции зависит от величины второго аргумента. Если мы захотим прибавить
единицу к сотне, то порядок следования аргументов существенно повлияет на скорость вычисления.
Напишите функцию, которая лишена этого недостатка.
• Напишите функцию возведения в степень pow :: Nat -> Nat -> Nat.
• Напишите тип, описывающий бинарные деревья BinTree a. Бинарное дерево может быть либо листом
со значением типа a, либо хранить два поддерева.
• Напишите функцию reverse :: BinTree a -> BinTree a, которая переворачивает дерево. Она меняет
местами два элемента в узле дерева.
• Напишите функцию depth :: BinTree a -> Nat, которая вычисляет глубину дерева, то есть самый
длинный путь от корня дерева к листу.
38 | Глава 2: Первая программа
• Напишите функцию leaves :: BinTree a -> [a], которая переводит бинарное дерево в список, воз-
вращая все элементы в листьях дерева.
• Обратите внимание на раздел List Operations в Prelude. Посмотрите на функции и их типы. Попро-
буйте догадаться по типу функции и названию что она делает.
• Попробуйте разобраться по документации с классами Ord (сравнение на больше/меньше), Enum (пере-
числения) и Integral (целые числа). Также стоит отметить класс Floating. Если у вас не получится,
не беда, они обязательно встретятся нам вновь. Там и разберёмся.
• Найдите функцию, которая переставляет элементы пары местами (элементы могут быть разных типов).
Потренируйтесь с кортежами. Определите аналоги функций fst и snd для не пар. Обратите внимание
на то, что сочетание символов (,) это функция-конструктор пары:
Prelude> (,) ”Hi” 101
(”Hi”,101)
Prelude> :t (,)
(,) :: a -> b -> (a, b)
Также определены („), („,) и другие.
Упражнения | 39
Глава 3
Типы
С помощью типов мы определяем все возможные значения в нашей программе. Мы определяем основные
примитивы и способы их комбинирования. Например в типе Nat:
data Nat = Zero | Succ Nat
Один конструктор-примитив Zero, и один конструктор Succ, с помощью которого мы можем делать со-
ставные значения. Определив тип Nat таким образом, мы говорим, что значения типа Nat могут быть только
такими:
Zero,
Succ Zero,
Succ (Succ Zero), Succ (Succ (Succ Zero)), …
Все значения являются цепочками Succ с Zero на конце. Если где-нибудь мы попытаемся построить значе-
ние, которое не соответствует нашему типу, мы получим ошибку компиляции, то есть программа не пройдёт
проверку типов. Так типы описывают множество допустимых значений.
Значения, которые проходят проверку типов мы будем называть допустимыми, а те, которые не проходят
соответственно недопустимыми. Так например следующие значения недопустимы для Nat
Succ Zero Zero,
Succ Succ, True, Zero (Zero Succ), …
Недопустимых значений конечно гораздо больше. Такое проявляется и в естественном языке, бессмыс-
ленных комбинаций слов гораздо больше, чем осмысленных предложений. Обратите внимание на то, что мы
говорим о значениях (не)допустимых для некоторого типа, например значение True допустимо для Bool, но
недопустимо для Nat.
Сами типы строятся не произвольным образом. Мы узнали, что при их построении используются две ос-
новные операции, это сумма и произведение типов. Это говорит о том, что в типах должны быть какие-то
закономерности, которые распространяются на все значения. В этой главе мы посмотрим на эти закономер-
ности.
3.1 Структура алгебраических типов данных
Итак у нас лишь две операции: сумма и произведение. Давайте для начала рассмотрим два крайних
случая.
• Только произведение типов
data T = Name T1 T2 … TN
Мы говорим, что значение нашего нового типа T состоит из значений типов T1, T2, … , TN и у нас есть
лишь один способ составить значение этого типа. Единственное, что мы можем сделать это применить
к значениям типов Ti конструктор Name.
Пример:
data Time = Time Hour Second Minute
• Только сумма типов
data T = Name1 | Name2 | … | NameN
40 | Глава 3: Типы
Мы говорим, что у нашего нового типа T может быть лишь несколько значений, и перечисляем их в
альтернативах через знак |.
Пример:
data Bool = True | False
Сделаем первое наблюдение: каждое произведение типов определяет новый конструктор. Число кон-
структоров в типе равно числу альтернатив. Так в первом случае у нас была одна альтернатива и следова-
тельно у нас был лишь один конструктор 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 являются деревьями. Узел дерева содержит составной конструктор, а лист дерева содержит
примитивный конструктор. Далее будет небольшой подраздел посвящённый терминологии теории графов,
