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

Как мы уже видели, конструкторы алгебраических типов данных могут иметь несколько полей (или не иметь вовсе), и у каждого поля должен быть конкретный тип. Принимая это во внимание, мы можем создать тип, конструктор которого имеет поля того же самого типа! Таким образом мы можем создавать рекурсивные типы данных, где одно значение некоторого типа содержит другие значения этого типа, а они, в свою очередь, содержат ещё значения того же типа, и т. д.

Посмотрите на этот список: [5]. Это упрощённая запись выражения 5:[]. С левой стороны от оператора : ставится значение, с правой стороны – список (в нашем случае пустой). Как насчёт списка [4,5]? Его можно переписать так: 4:(5:[]). Смотря на первый оператор :, мы видим, что слева от него – всё так же значение, а справа – список (5:[]). То же можно сказать и в отношении списка 3:(4:(5:6:[])); это выражение можно переписать и как 3:4:5:6:[] (поскольку оператор : правоассоциативен), и как [3,4,5,6].

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

Ну что ж, давайте используем алгебраические типы данных, чтобы создать наш собственный список.

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

Это можно прочитать почти как наше определение списка в одном из предыдущих разделов. Это либо пустой список, либо комбинация некоторого значения («головы») и собственно списка («хвоста»). Если такая формулировка трудна для понимания, то с использованием синтаксиса записей она будет восприниматься легче.

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:[]).