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

data List a = Empty | Cons { listHead :: a, listTail :: List a}

deriving (Show, Read, Eq, Ord)

Конструктор Consможет вызвать недоумение. Идентификатор Cons– всего лишь альтернативное обозначение :. Как вы видите, в списках оператор :– это просто конструктор, который принимает значение и список и возвращает список. Мы можем использовать и наш новый тип для задания списка! Другими словами, он имеет два поля: первое типа aи второе типа [a].

ghci> Empty

Empty

ghci> 5 `Cons` Empty

Cons 5 Empty

ghci> 4 `Cons` (5 `Cons` Empty)

Cons 4 (Cons 5 Empty)

ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))

Cons 3 (Cons 4 (Cons 5 Empty))

Мы вызываем конструктор Consкак инфиксный оператор, чтобы наглядно показать, что мы используем его вместо оператора :. Конструктор Emptyиграет роль пустого списка [], и выражение 4 `Cons` (5 `Cons` Empty)подобно выражению 4:(5:[]).

Мы можем определить функцию как инфиксную по умолчанию, если её имя состоит только из специальных символов. То же самое можно сделать и с конструкторами, поскольку это просто функции, возвращающие тип данных. Смотрите:

infixr 5 :–:

data List a = Empty | a :–: (List a) deriving (Show, Read, Eq, Ord)

Первое: мы использовали новую синтаксическую конструкцию, декларацию ассоциативности функции. Если мы определяем функции как операторы, то можем присвоить им значение ассоциативности, но не обязаны этого делать. Ассоциативность показывает, какова приоритетность оператора и является ли он лево- или правоассоциативным. Например, ассоциативность умножения – infixl 7 *, ассоциативность сложения – infixl 6. Это значит, что оба оператора левоассоциативны, выражение 4 * 3 * 2означает ((4 * 3) * 2), умножение имеет более высокий приоритет, чем сложение, поэтому выражение 5 * 4 + 3означает (5 * 4) + 3.

Следовательно, ничто не мешает записать a :–: (List a)вместо Cons a (List a). Теперь мы можем представлять списки нашего нового спискового типа таким образом:

ghci> 3 :-: 4 :-: 5 :-: Empty

3 :-: (4 :-: (5 :-: Empty))

ghci> let a = 3 :-: 4 :-: 5 :-: Empty

ghci> 100 :-: a

100 :-: (3 :-: (4 :-: (5 :-: Empty))

Напишем функцию для сложения двух списков. Вот как оператор ++определён для обычных списков:

infixr 5 ++

(++) :: [a] –> [a] –> [a]

[] ++ ys = ys

(x:xs) ++ ys = x : (xs ++ ys)

Давайте просто передерём это объявление для нашего списка! Назовём нашу функцию ^++:

infixr 5 ++

(^++) :: List a –> List a –> List a

Empty ^++ ys = ys

(x :–: xs) ++ ys = x :–: (xs ++ ys)

И посмотрим, как это работает…

ghci> let a = 3 :-: 4 :-: 5 :-: Empty

ghci> let b = 6 :-: 7 :-: Empty

ghci> a ++ b

3 :-: (4 :-: (5 :-: (6 :-: (7 :-: Empty))))

Очень хорошо. Если бы мы хотели, мы могли бы реализовать все функции для работы со списками и для нашего спискового типа.

Обратите внимание, как мы выполняли сопоставление с образцом по (x :–: xs). Это работает, потому что на самом деле данная операция сопоставляет конструкторы. Мы можем сопоставлять по конструктору :–:потому, что это конструктор для нашего собственного спискового типа, так же как можем сопоставлять и по конструктору :, поскольку это конструктор встроенного спискового типа. Так как сопоставление производится только по конструкторам, можно искать соответствие по образцам, подобным (x :–: xs), или константам, таким как 8или 'a', поскольку на самом деле они являются конструкторами для числового и символьного типов [10] На самом деле в синтаксисе языка Haskell имеются ещё так называемые (n + k)-образцы. Впрочем, большая часть сообщества языка их отвергает. – Прим. ред. .

Теперь мы собираемся реализовать бинарное поисковое дерево. Если вам не знакомы поисковые деревья из языков наподобие С, вот что они представляют собой: элемент указывает на два других элемента, один из которых правый, другой – левый. Элемент слева – меньше, чем текущий, элемент справа – больше. Каждый из этих двух элементов также может ссылаться на два других элемента (или на один, или не ссылаться вообще). Получается, что каждый элемент может иметь до двух поддеревьев. Бинарные поисковые деревья удобны тем, что мы знаем, что все элементы в левом поддереве элемента со значением, скажем, пять, будут меньше пяти. Элементы в правом поддереве будут больше пяти. Таким образом, если нам надо найти 8 в нашем дереве, мы начнём с пятёрки, и так как 8 больше 5, будем проверять правое поддерево. Теперь проверим узел со значением 7, и так как 8 больше 7, снова выберем правое поддерево. В результате элемент найдётся всего за три операции сравнения! Если мы бы искали в обычном списке (или в сильно разбалансированном дереве), потребовалось бы до семи сравнений вместо трёх для поиска того же элемента.

ПРИМЕЧАНИЕ.Множества и отображения из модулей Data.Setи Data.Mapреализованы с помощью деревьев, но вместо обычных бинарных поисковых деревьев они используют сбалансированные поисковые деревья. Дерево называется сбалансированным, если высоты его левого и правого поддеревьев примерно равны. Это условие ускоряет поиск по дереву. В наших примерах мы реализуем обычные поисковые деревья.

Вот что мы собираемся сказать: дерево – это или пустое дерево, или элемент, который содержит некоторое значение и два поддерева. Такая формулировка идеально соответствует алгебраическому типу данных.

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

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

В языках, подобных С, мы бы делали это, изменяя указатели и значения внутри дерева. В Haskell мы на самом деле не можем изменять наше дерево – придётся создавать новое поддерево каждый раз, когда мы переходим к левому или правому поддереву. Таким образом, в конце функции добавления мы вернём полностью новое дерево, потому что в языке Haskell нет концепции указателей, есть только значения. Следовательно, тип функции для добавления элемента будет примерно следующим: a –> Tree a – > Tree a. Она принимает элемент и дерево и возвращает новое дерево с уже добавленным элементом. Это может показаться неэффективным, но язык Haskell умеет организовывать совместное владение большей частью поддеревьев старым и новым деревьями.