>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 нереально круты. Мы можем использовать их для создания чего угодно – от булевских значений и перечислимого типа для дней недели до бинарных поисковых деревьев и даже большего!