Рекурсивные типы данных: списки

Самые впечатляющие возможности той системы создания своих типов, что есть в Haskell, проявляются при создании рекурсивных и потенциально бесконечных структур данных. Начнем со списка:

data List a = Empty | Cons a (List a) deriving Show

О чем говорит эта запись? Список значений типа a – это или пустой список, или пара из значения типа a и списка типа a, созданная конструктором данных Cons. Давайте еще раз: любой список, согласно этому определению – это или пустой список, или пара (значение, список). Вам это ничего не напоминает?

Что такое Empty? Что такое Cons? Это все конструкторы данных: с их помощью можно создать список:

Empty :: List a

Cons :: a -> List a -> List a

Empty возвращает пустой список, а Cons принимает значение типа a, потом список типа a, и возвращает новый список типа a. Например, давайте создадим небольшие списки, начиная с пустого. Таким образом, удлиняясь и удлиняясь, список может стать потенциально бесконечным:

Empty :: List a

Cons 'a' Empty :: List Char

Cons 'a' (Cons 'b' Empty) :: List Char

Cons 'a' (Cons 'b' (Cons 'c' Empty)) :: List Char

Давайте напишем функцию, которая находит длину списка. Как и любая функция, которая работает со сложным типом данных, эта функция должна уметь обрабатывать все возможные значения типа List a:

len :: List a -> Int

len Empty = 0

len (Cons x xs) = 1 + len xs

В этой функции показано, как функция должна работать, если List a является значением Empty, и если List a является Cons от значения и другого списка. Вам ничего эта функция не напоминает? Давайте-ка вспомним стандартную функцию length, которая работает на стандартных списках:

length :: [a] -> Int

length [] = 0

length (x:xs) = 1 + length xs

Стопроцентное повторение ведь! Возьмем опять наше определение List a и немного его преобразуем: заменим Empty на [], Cons на (:), ну и List a на [a], и получится:

data List a = Empty | Cons a (List a)

data [] a = [] | (:) a []

data [a] = [] | a : [a]

Последнее, впрочем, уже чистый синтаксический сахар: такое (запись вида [a]) позволено только обычным стандартным спискам. Но идея ясна – обычные списки объявляются именно так, как мы записали. Обычный список значений типа a – это или пустой список [], или запись вида x : xs, где x – это значение этого типа a, а xs – это опять список значений типа a.

Думаю, теперь должно быть абсолютно понятно, почему нельзя напрямую обратиться к последнему элементу списка, а только к хвосту: потому что список – это, по сути, пара (голова, хвост), и обращаться можно только к одному из этих элементов.

Рекурсивные типы данных: деревья

Аналогичным образом создаются структуры данных для деревьев:

data Tree a = Empty | Leaf a | Branches (Tree a) (Tree a) deriving Show

Что такое дерево типа a, согласно этому определению? Во-первых, деревом может быть пустое дерево. Во-вторых, деревом может быть лист со значением типа a. И третий вариант – деревом может быть разветвление на две ветви, каждая из которых может быть опять произвольным деревом.

Вот примеры деревьев:

Empty :: Tree a

Leaf 'a' :: Tree Char

Branches (Leaf 'a') (Leaf 'b') :: Tree Char

Branches (Leaf 'a') (Branches Empty (Leaf 'b')) :: Tree Char

Различных типов деревьев может быть очень много, какого типа дерево создали мы такой структурой данных? Во-первых, наше дерево бинарное: любое ветвление – двоичное. Во-вторых, наше дерево может быть пустым. В-третьих, наше дерево хранит значения только в листах. Видите, как эти три утверждения следуют из определения нашего типа данных? Если вдруг понадобится использовать дерево с произвольным количеством потомков у узла, или если понадобится хранить значения в узлах – придется делать другой тип данных.

Как работать с таким деревом? Точно так же, как мы работали с определяемыми самостоятельно списками, или любыми другими собственными типами данных. Давайте, например, напишем функцию, которая собирает в список в произвольном порядке все листья с заданного дерева. Функция должна обработать все три случая, все три формы существования дерева:

fringe :: Tree a -> [a]

fringe Empty = []

fringe (Leaf x) = [x]

fringe (Branches lt rt) = fringe lt ++ fringe rt

Если дерево пустое, функция возвращает пустой список. Если дерево состоит из одного листа, функция возвращает список с единственным значением. И наконец, если дерево – это две ветви, то возвращается список из листьев с левого дерева, к которым добавлены листья с правого дерева. По сути, это LDF обход дерева – левый обход в глубину.

В качестве второго примера, напишем функцию, которая применяет к каждому элементу дерева какую-то функцию, сохраняя структуру дерева нетронутой:

mapTree :: (a -> b) -> Tree a -> Tree b

mapTree f Empty = Empty

mapTree f (Leaf x) = Leaf (f x)

mapTree f (Branches lt rt) =

Branches (mapTree f lt) (mapTree f rt)

Функция преобразует лист, если он ей встретился, в такой же лист – но с измененным значением. И проталкивает изменения рекурсивно вниз по веткам, если ей встретились ветки.

Кстати, обратите внимание на тип функции mapTree, и сравните его с типом функции map:

mapTree :: (a -> b) -> Tree a -> Tree b

map :: (a -> b) -> [a] -> [b]

Не правда ли, у этих функций слишком много общего? Но это уже – совсем другая история.