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

Посмотрите на этот список: [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:[]).

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

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)-образцы. Впрочем, большая часть сообщества языка их отвергает. – Прим. ред. .