Миран Липовача - Изучай Haskell во имя добра!

Итак, напишем две функции. Первая будет вспомогательной функцией для создания дерева, состоящего из одного элемента; вторая будет вставлять элемент в дерево.

singleton :: a –> Tree a

singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a –> Tree a –> Tree a

treeInsert x EmptyTree = singleton x

treeInsert x (Node a left right)

| x == a = Node x left right

| x < a = Node a (treeInsert x left) right

| x > a = Node a left (treeInsert x right)

Функция singletonслужит для создания узла, который хранит некоторое значение и два пустых поддерева. В функции для добавления нового элемента в дерево мы вначале обрабатываем граничное условие. Если мы достигли пустого поддерева, это значит, что мы в нужном месте нашего дерева, и вместо пустого дерева помещаем одноэлементное дерево, созданное из нашего значения. Если мы вставляем не в пустое дерево, следует кое-что проверить. Первое: если вставляемый элемент равен корневому элементу – просто возвращаем дерево текущего элемента. Если он меньше, возвращаем дерево, которое имеет то же корневое значение и то же правое поддерево, но вместо левого поддерева помещаем дерево с добавленным элементом. Так же (но с соответствующими поправками) обстоит дело, если значение больше, чем корневой элемент.

Следующей мы напишем функцию для проверки, входит ли некоторый элемент в наше дерево или нет. Для начала определим базовые случаи. Если мы ищем элемент в пустом дереве, его там определённо нет. Заметили – такой же базовый случай мы использовали для поиска элемента в списке? Если мы ищем в пустом списке, то ничего не найдём. Если ищем не в пустом дереве, надо проверить несколько условий. Если элемент в текущем корне равен тому, что мы ищем, – отлично. Ну а если нет, тогда как быть?.. Мы можем извлечь пользу из того, что все элементы в левом поддереве меньше корневого элемента. Поэтому, если искомый элемент меньше корневого, начинаем искать в левом поддереве. Если он больше – ищем в правом поддереве.

treeElem :: (Ord a) => a –> Tree a –> Bool

treeElem x EmptyTree = False

treeElem x (Node a left right)

| x == a = True

| x < a = treeElem x left

| x > a = treeElem x right

Всё, что нам нужно было сделать, – переписать предыдущий параграф в коде. Давайте немного «погоняем» наши деревья. Вместо того чтобы вручную задавать деревья (а мы можем!), будем использовать свёртку для того, чтобы создать дерево из списка. Запомните: всё, что обходит список элемент за элементом и возвращает некоторое значение, может быть представлено свёрткой. Мы начнём с пустого дерева и затем будем проходить список справа налево и вставлять элемент за элементом в дерево-аккумулятор.

ghci> let nums = [8,6,4,1,7,3,5]

ghci> let numsTree = foldr treeInsert EmptyTree nums

ghci> numsTree

Node 5

(Node 3

(Node 1 EmptyTree EmptyTree)

(Node 4 EmptyTree EmptyTree)

)

(Node 7

(Node 6 EmptyTree EmptyTree)

(Node 8 EmptyTree EmptyTree)

)

ПРИМЕЧАНИЕ.Если вы вызовете этот код в интерпретаторе GHCi, то в качестве вывода будет одна длинная строка. Здесь она разбита на несколько строк, иначе она бы вышла за пределы страницы.

В этом вызове функции foldrфункция treeInsertиграет роль функции свёртки (принимает дерево и элемент списка и создаёт новое дерево); EmptyTree– стартовое значение аккумулятора. Параметр nums– это, конечно же, список, который мы сворачиваем.

Если напечатать дерево на консоли, мы получим не очень-то легко читаемое выражение, но если постараться, можно уловить структуру. Мы видим, что корневое значение – 5; оно имеет два поддерева, в одном из которых корневым элементом является 3, а в другом – 7, и т. д.

ghci> 8 `treeElem` numsTree

True

ghci> 100 `treeElem` numsTree

False

ghci> 1 `treeElem` numsTree

True

ghci> 10 `treeElem` numsTree

False

Проверка на вхождение также работает отлично. Классно!

Как вы можете видеть, алгебраические типы данных в языке Haskell нереально круты. Мы можем использовать их для создания чего угодно – от булевских значений и перечислимого типа для дней недели до бинарных поисковых деревьев и даже большего!

Мы уже изучили несколько стандартных классов типов языка Haskell и некоторые типы, имеющие для них экземпляры. Также мы знаем, как автоматически сделать для наших типов экземпляры стандартных классов, стоит только попросить Haskell автоматически сгенерировать нужное нам поведение. В этой главе будет рассказано о том, как писать свои собственные классы типов и как создавать экземпляры класса вручную.

Вспомним, что классы типов по сути своей подобны интерфейсам. Они определяют некоторое поведение (проверку на равенство, проверку на «больше-меньше», перечисление элементов). Типы, обладающие таким поведением, можно сделать экземпляром класса типов. Поведение класса типов определяется функциями, входящими в класс, или просто декларацией класса; элементы класса мы потом должны будем реализовать. Таким образом, если мы говорим, что для типа имеется экземпляр класса, то подразумеваем, что можем использовать все функции, определённые в классе типов в нашем типе.

ПРИМЕЧАНИЕ.Классы типов практически не имеют ничего общего с классами в таких языках, как Java или Python. Это сбивает с толку, поэтому советую вам забыть всё, что вы знаете о классах в императивных языках!

Возьмём для примера класс типов Eq: он используется в отношении неких значений, которые можно проверить на равенство. Он определяет операторы ==и /=. Если у нас есть тип, скажем, Car( автомобиль ), и сравнение двух автомобилей с помощью функции ==имеет смысл, то имеет смысл и определить для типа Carэкземпляр класса Eq.

Вот как класс Eqопределён в стандартном модуле:

class Eq a where

(==) :: a –> a –> Bool

(/=) :: a –> a –> Bool

x == y = not (x /= y)

x /= y = not (x == y)

О-хо-хо!.. Новый синтаксис и новые ключевые слова. Не беспокойтесь, скоро мы это поясним. Прежде всего, мы записали декларацию class Eq a where– это означает, что мы определяем новый класс, имя которого Eq. Идентификатор a– это переменная типа; иными словами, идентификатор играет роль типа, который в дальнейшем будет экземпляром нашего класса. Эту переменную необязательно называть именно a; пусть даже имя не состоит из одной буквы, но оно непременно должно начинаться с символа в нижнем регистре. Затем мы определяем несколько функций. Нет необходимости писать реализацию функций – достаточно только декларации типа.

Некоторым будет проще понять эту декларацию, если мы запишем class Eq equatable where, а затем декларации функций, например (==) :: equatable –> equatable –> Bool.