Изучай Haskell во имя добра!

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

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

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

Улучшение нашего списка

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

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].