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

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; пусть даже имя не состоит из одной буквы, но оно непременно должно начинаться с символа в нижнем регистре. Затем мы определяем несколько функций. Нет необходимости писать реализацию функций – достаточно только декларации типа.