Теперь подумаем, как бы мы представили некую геометрическую фигуру в языке Haskell. Один из способов – использовать кортежи. Круг может быть представлен как (43.1, 55.0, 10.4), где первое и второе поле – координаты центра, а третье – радиус. Вроде бы подходит, но такой же кортеж может представлять вектор в трёхмерном пространстве или что-нибудь ещё. Лучше было бы определить свой собственный тип для фигуры. Скажем, наша фигура может быть кругом или прямоугольником.

data Shape = Circle Float Float Float | Rectangle Float Float Float Float

Ну и что это? Размышляйте следующим образом. Конструктор для значения Circle содержит три поля типа Float. Когда мы записываем конструктор значения типа, опционально мы можем добавлять типы после имени конструктора; эти типы определяют, какие значения будет содержать тип с данным конструктором. В нашем случае первые два числа – это координаты центра, третье число – радиус. Конструктор для значения Rectangle имеет четыре поля, которые также являются числами с плавающей точкой. Первые два числа – это координаты верхнего левого угла, вторые два числа – координаты нижнего правого угла.

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

ghci> :t Circle

Circle :: Float –> Float –> Float –> Shape

ghci> :t Rectangle

Rectangle :: Float –> Float –> Float –> Float –> Shape

Классно, конструкторы значений – такие же функции, как любые другие! Кто бы мог подумать!..

Давайте напишем функцию, которая принимает фигуру и возвращает площадь её поверхности:

area :: Shape –> Float

area (Circle _ _ r) = pi * r ^ 2

area (Rectangle x1 y1 x2 y2) = (abs $ x2 – x1) * (abs $ y2 – y1)

Первая примечательная вещь в объявлении – это декларация типа. Она говорит, что функция принимает фигуру и возвращает значение типа Float. Мы не смогли бы записать функцию типа Circle –> Float, потому что идентификатор Circle не является типом; типом является идентификатор Shape. По той же самой причине мы не смогли бы написать функцию с типом True –> Int. Вторая примечательная вещь – мы можем выполнять сопоставление с образцом по конструкторам. Мы уже записывали подобные сопоставления раньше (притом очень часто), когда сопоставляли со значениями [], False, 5, только эти значения не имели полей. Только что мы записали конструктор и связали его поля с именами. Так как для вычисления площади нам нужен только радиус, мы не заботимся о двух первых полях, которые говорят нам, где располагается круг.

ghci> area $ Circle 10 20 10

314.15927

ghci> area $ Rectangle 0 0 100 100

10000.0

Ура, работает! Но если попытаться напечатать Circle 10 20 5 в командной строке интерпретатора, то мы получим ошибку. Пока Haskell не знает, как отобразить наш тип данных в виде строки. Вспомним, что когда мы пытаемся напечатать значение в командной строке, интерпретатор языка Haskell вызывает функцию show, для того чтобы получить строковое представление значения, и затем печатает результат в терминале. Чтобы определить для нашего типа Shape экземпляр класса Show, модифицируем его таким образом:

data Shape = Circle Float Float Float | Rectangle Float Float Float Float

  deriving (Show)

Не будем пока концентрировать внимание на конструкции deriving (Show). Просто скажем, что если мы добавим её в конец объявления типа данных, Haskell автоматически определит экземпляр класса Show для этого типа. Теперь можно делать так:

ghci> Circle 10 20 5

Circle 10.0 20.0 5.0

ghci> Rectangle 50 230 60 90

Rectangle 50.0 230.0 60.0 90.0

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

ghci> map (Circle 10 20) [4,5,6,6]

[Circle 10.0 20.0 4.0,Circle 10.0 20.0 5.0,Circle 10.0 20.0 6.0,Circle 10.0 20.0 6.0]

Верный способ улучшить фигуру

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

data Point = Point Float Float deriving (Show)

data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

Обратите внимание, что при определении точки мы использовали одинаковые имена для конструктора типа и для конструктора данных. В этом нет какого-то особого смысла, но если у типа данных только один конструктор, как правило, он носит то же имя, что и тип. Итак, теперь у конструктора Circle два поля: первое имеет тип Point, второе – Float. Так легче разобраться, что есть что. То же верно и для прямоугольника. Теперь, после всех изменений, мы должны исправить функцию area:

area :: Shape –> Float

area (Circle _ r) = pi * r 2

area (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 – x1) * (abs $ y2 – y1)

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

ghci> area (Rectangle (Point 0 0) (Point 100 100))

10000.0

ghci> area (Circle (Point 0 0) 24)

1809.5574

Как насчёт функции, которая двигает фигуру? Она принимает фигуру, приращение координаты по оси абсцисс, приращение координаты по оси ординат – и возвращает новую фигуру, которая имеет те же размеры, но располагается в другом месте.

nudge :: Shape –> Float –> Float –> Shape

nudge (Circle (Point x y) r) a b = Circle (Point (x+a) (y+b)) r

nudge (Rectangle (Point x1 y1) (Point x2 y2)) a b

  = Rectangle (Point (x1+a) (y1+b)) (Point (x2+a) (y2+b))

Всё довольно очевидно. Мы добавляем смещение к точкам, определяющим положение фигуры:

ghci> nudge (Circle (Point 34 34) 10) 5 10

Circle (Point 39.0 44.0) 10.0

Если мы не хотим иметь дело напрямую с точками, то можем сделать вспомогательные функции, которые создают фигуры некоторого размера с нулевыми координатами, а затем их подвигать.

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

baseCircle :: Float –> Shape

baseCircle r = Circle (Point 0 0) r

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

baseRect :: Float –> Float –> Shape

baseRect width height = Rectangle (Point 0 0) (Point width height)

Теперь создавать формы гораздо легче: достаточно создать форму в начале координат, а затем сдвинуть её в нужное место:

ghci> nudge (baseRect 40 100) 60 23

Rectangle (Point 60.0 23.0) (Point 100.0 123.0)

Фигуры на экспорт

Конечно же, вы можете экспортировать типы данных из модулей. Чтобы сделать это, запишите имена ваших типов вместе с именами экспортируемых функций. В отдельных скобках, через запятую, укажите, какие конструкторы значений вы хотели бы экспортировать. Если хотите экспортировать все конструкторы значений, просто напишите две точки (..).

Если бы мы хотели поместить функции и типы, определённые выше, в модуль, то могли бы начать как-то так:

module Shapes

( Point(..)

, Shape(..)

, area

, nudge

, baseCircle

, baseRect

) where

Запись Shape(..) обозначает, что мы экспортируем все конструкторы данных для типа Shape. Тот, кто импортирует наш модуль, сможет создавать фигуры, используя конструкторы Rectangle и Circle. Это то же самое, что и Shape (Rectangle, Circle), но короче.

К тому же, если мы позже решим дописать несколько конструкторов данных, перечень экспортируемых объектов исправлять не придётся. Всё потому, что конструкция .. автоматически экспортирует все конструкторы соответствующего типа.

Мы могли бы не указывать ни одного конструктора для типа Shape, просто записав Shape в операторе экспорта. В таком случае тот, кто импортирует модуль, сможет создавать фигуры только с помощью функций baseCircle и baseRect.

Помните, конструкторы данных – это простые функции, принимающие поля как параметры и возвращающие значение некоторого типа (например, Shape) как результат. Если мы их не экспортируем, то вне модуля они будут недоступны. Отказ от экспорта конструкторов данных делает наши типы данных более абстрактными, поскольку мы скрываем их реализацию. К тому же, пользователи нашего модуля не смогут выполнять сопоставление с образцом для этих конструкторов данных. Это полезно, если мы хотим, чтобы программисты, импортирующие наш тип, работали только со вспомогательными функциями, которые мы специально для этого написали. Таким образом, у них нет необходимости знать о деталях реализации модуля, и мы можем изменить эти детали, когда захотим – лишь бы экспортируемые функции работали как прежде.

Модуль Data.Map использует такой подход. Вы не можете создать отображение напрямую при помощи соответствующего конструктора данных, потому что такой конструктор не экспортирован. Однако можно создавать отображения, вызвав одну из вспомогательных функций, например Map.fromList. Разработчики, ответственные за Data.Map, в любой момент могут поменять внутреннее представление отображений, и при этом ни одна существующая программа не сломается.

Разумеется, экспорт конструкторов данных для типов попроще вполне допустим.

Конструктор данных может принимать несколько параметров-значений и возвращать новое значение. Например, конструктор Car принимает три значения и возвращает одно – экземпляр типа Car. Таким же образом конструкторы типа могут принимать типы-параметры и создавать новые типы. На первый взгляд это несколько абстрактно, но на самом деле не так уж сложно. Если вы знакомы с шаблонами в языке С++, то увидите некоторые параллели. Чтобы получить более ясное представление о том, как работают типы-параметры, давайте посмотрим, как реализованы типы, с которыми мы уже встречались.

data Maybe a = Nothing | Just a

В данном примере идентификатор a – тип-параметр (переменная типа, типовая переменная). Так как в выражении присутствует тип-параметр, мы называем идентификатор Maybe конструктором типов. В зависимости от того, какой тип данных мы хотим сохранять в типе Maybe, когда он не Nothing, конструктор типа может производить такие типы, как Maybe Int, Maybe Car, Maybe String и т. д. Ни одно значение не может иметь тип «просто Maybe», потому что это не тип как таковой – это конструктор типов. Для того чтобы он стал настоящим типом, значения которого можно создать, мы должны указать все типы-параметры в конструкторе типа.

Итак, если мы передадим тип Char как параметр в тип Maybe, то получим тип Maybe Char. Для примера: значение Just 'a' имеет тип Maybe Char.

Обычно нам не приходится явно передавать параметры конструкторам типов, поскольку в языке Haskell есть вывод типов. Поэтому когда мы создаём значение Just 'a', Haskell тут же определяет его тип – Maybe Char.

Если мы всё же хотим явно указать тип как параметр, это нужно делать в типовой части выражений, то есть после символа ::. Явное указание типа может понадобиться, если мы, к примеру, хотим, чтобы значение Just 3 имело тип Maybe Int. По умолчанию Haskell выведет тип (Num a) => Maybe a. Воспользуемся явным аннотированием типа:

ghci> Just 3 :: Maybe Int

Just 3

Может, вы и не знали, но мы использовали тип, у которого были типы-параметры ещё до типа Maybe. Этот тип – список. Несмотря на то что дело несколько скрывается синтаксическим сахаром, конструктор списка принимает параметр для того, чтобы создать конкретный тип. Значения могут иметь тип [Int], [Char], [[String]], но вы не можете создать значение с типом [].

ПРИМЕЧАНИЕ. Мы называем тип конкретным, если он вообще не принимает никаких параметров (например, Int или Bool ) либо если параметры в типе заполнены (например, Maybe Char ). Если у вас есть какое-то значение, у него всегда конкретный тип.

Давайте поиграем с типом Maybe:

ghci> Just "Ха-ха"

Just "Ха-ха"

ghci> Just 84

Just 84

ghci> :t Just "Ха-ха"

Just "Ха-ха" :: Maybe [Char]

ghci> :t Just 84

Just 84 :: (Num t) => Maybe t

ghci> :t Nothing

Nothing :: Maybe a

ghci> Just 10 :: Maybe Double

Just 10.0

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

data IntMaybe = INothing | IJust Int

data StringMaybe = SNothing | SJust String

data ShapeMaybe = ShNothing | ShJust Shape

Более того, мы можем использовать типы-параметры для определения самого обобщённого Maybe, который может содержать данные вообще любых типов!

Обратите внимание: тип значения Nothing – Maybe a. Это полиморфный тип: в его имени присутствует типовая переменная – конкретнее, переменная a в типе Maybe a. Если некоторая функция принимает параметр типа Maybe Int, мы можем передать ей значение Nothing, так как оно не содержит значения, которое могло бы этому препятствовать. Тип Maybe a может вести себя как Maybe Int, точно так же как значение 5 может рассматриваться как значение типа Int или Double. Аналогичным образом тип пустого списка – это [a]. Пустой список может вести себя как список чего угодно. Вот почему можно производить такие операции, как [1,2,3] ++ [] и ["ха","ха","ха"] ++ [].

Параметризовать ли машины?

Когда имеет смысл применять типовые параметры? Обычно мы используем их, когда наш тип данных должен уметь сохранять внутри себя любой другой тип, как это делает Maybe a. Если ваш тип – это некоторая «обёртка», использование типов-параметров оправданно. Мы могли бы изменить наш тип данных Car с такого:

data Car = Car { company :: String

               , model :: String

               , year :: Int

               } deriving (Show)

на такой:

data Car a b c = Car { company :: a

                     , model :: b

                     , year :: c

                     } deriving (Show)

Но выиграем ли мы в чём-нибудь? Ответ – вероятно, нет, потому что впоследствии мы всё равно определим функции, которые работают с типом Car String String Int. Например, используя первое определение Car, мы могли бы создать функцию, которая отображает свойства автомобиля в виде понятного текста:

tellCar :: Car –> String

tellCar (Car {company = c, model = m, year = y}) =

  "Автомобиль " ++ c ++ " " ++ m ++ ", год: " ++ show y

ghci> let stang = Car {company="Форд", model="Мустанг", year=1967}

ghci> tellCar stang

"Автомобиль Форд Мустанг, год: 1967"

Приятная маленькая функция. Декларация типа функции красива и понятна. А что если Car – это Car a b c?

tellCar :: (Show a) => Car String String a –> String

tellCar (Car {company = c, model = m, year = y}) =

  "Автомобиль " ++ c ++ " " ++ m ++ ", год: " ++ show y

Мы вынуждены заставить функцию принимать параметр Car типа (Show a) => Car String String a. Как видите, декларация типа функции более сложна; единственное преимущество, которое здесь имеется, – мы можем использовать любой тип, имеющий экземпляр класса Show, как тип для типовой переменной c.

ghci> tellCar (Car "Форд" "Мустанг" 1967)

"Автомобиль Форд Мустанг, год: 1967"

ghci> tellCar (Car "Форд" "Мустанг" "тысяча девятьсот шестьдесят седьмой")

"Автомобиль Форд Мустанг, год: \"тысяча девятьсот шестьдесят седьмой\""

ghci> :t Car "Форд" "Мустанг" 1967

Car "Форд" "Мустанг" 1967 :: (Num t) => Car [Char] [Char] t

ghci> :t Car "Форд" "Мустанг" "тысяча девятьсот шестьдесят седьмой"

Car "Форд" "Мустанг" "тысяча девятьсот шестьдесят седьмой"

  :: Car [Char] [Char] [Char]

На практике мы всё равно в большинстве случаев использовали бы Car String String Int, так что в параметризации типа Car большого смысла нет. Обычно мы параметризируем типы, когда для работы нашего типа неважно, что в нём хранится. Список элементов – это просто список элементов, и неважно, какого они типа: список работает вне зависимости от этого. Если мы хотим суммировать список чисел, то в суммирующей функции можем уточнить, что нам нужен именно список чисел. То же самое верно и для типа Maybe. Он предоставляет возможность не иметь никакого значения или иметь какое-то одно значение. Тип хранимого значения не важен.

Ещё один известный нам пример параметризованного типа – отображения Map k v из модуля Data.Map. Параметр k – это тип ключей в отображении, параметр v – тип значений. Это отличный пример правильного использования параметризации типов. Параметризация отображений позволяет нам использовать любые типы, требуя лишь, чтобы тип ключа имел экземпляр класса Ord. Если бы мы определяли тип для отображений, то могли бы добавить ограничение на класс типа в объявлении:

data (Ord k) => Map k v = ...

Тем не менее в языке Haskell принято соглашение никогда не использовать ограничения класса типов при объявлении типов данных. Почему? Потому что серьёзных преимуществ мы не получим, но в конце концов будем использовать всё больше ограничений, даже если они не нужны. Поместим ли мы ограничение (Ord k) в декларацию типа или не поместим – всё равно придётся указывать его при объявлении функций, предполагающих, что ключ может быть упорядочен. Но если мы не поместим ограничение в объявлении типа, нам не придётся писать его в тех функциях, которым неважно, может ключ быть упорядочен или нет. Пример такой функции – toList :: Map k a –> [(k, a)]. Если бы Map k a имел ограничение типа в объявлении, тип для функции toList был бы таким: toList :: (Ord k) => Map k a –> [(k, a)], даже несмотря на то что функция не сравнивает элементы друг с другом.

Так что не помещайте ограничения типов в декларации типов данных, даже если это имело бы смысл, потому что вам всё равно придётся помещать ограничения в декларации типов функций.

Векторы судьбы

Давайте реализуем трёхмерный вектор и несколько операций для него. Мы будем использовать параметризованный тип, потому что хоть вектор и содержит только числовые параметры, он должен поддерживать разные типы чисел.

data Vector a = Vector a a a deriving (Show)

vplus :: (Num a) => Vector a –> Vector a –> Vector a

(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)

scalarProd :: (Num a) => Vector a –> Vector a –> a

(Vector i j k) `scalarProd` (Vector l m n) = i*l + j*m + k*n

vmult :: (Num a) => Vector a –> a –> Vector a

(Vector i j k) `vmult` m = Vector (i*m) (j*m) (k*m)

Функция vplus складывает два вектора путём сложения соответствующих координат. Функция scalarProd используется для вычисления скалярного произведения двух векторов, функция vmult – для умножения вектора на константу.

Эти функции могут работать с типами Vector Int, Vector Integer, Vector Float и другими, до тех пор пока тип-параметр a из определения Vector a принадлежит классу типов Num. По типам функций можно заметить, что они работают только с векторами одного типа, и все координаты вектора также должны иметь одинаковый тип. Обратите внимание на то, что мы не поместили ограничение класса Num в декларацию типа данных, так как нам всё равно бы пришлось повторять его в функциях.

Ещё раз повторю: очень важно понимать разницу между конструкторами типов и данных. При декларации типа данных часть объявления до знака = представляет собой конструктор типа, а часть объявления после этого знака – конструктор данных (возможны несколько конструкторов, разделённых символом |). Попытка дать функции тип Vector a a a -> Vector a a a -> a будет неудачной, потому что мы должны помещать типы в декларацию типа, и конструктор типа для вектора принимает только один параметр, в то время как конструктор данных принимает три. Давайте поупражняемся с нашими векторами:

ghci> Vector 3 5 8 `vplus` Vector 9 2 8

Vector 12 7 16

ghci> Vector 3 5 8 `vplus` Vector 9 2 8 `vplus` Vector 0 2 3

Vector 12 9 19

ghci> Vector 3 9 7 `vmult` 10

Vector 30 90 70

ghci> Vector 4 9 5 `scalarProd` Vector 9.0 2.0 4.0

74.0

ghci> Vector 2 9 3 `vmult` (Vector 4 9 5 `scalarProd`

Vector 9 2 4) Vector 148 666 222

В разделе «Классы типов» главы 2 приводились базовые сведения о классах типов. Мы упомянули, что класс типов – это нечто вроде интерфейса, который определяет некоторое поведение. Тип может быть сделан экземпляром класса, если поддерживает это поведение. Пример: тип Int есть экземпляр класса типов Eq, потому что класс Eq определяет поведение для сущностей, которые могут быть проверены на равенство. Так как целые числа можно проверить на равенство, тип Int имеет экземпляр для класса Eq. Реальная польза от этого видна при использовании функций, которые служат интерфейсом класса Eq, – операторов == и /=. Если тип имеет определённый экземпляр класса Eq, мы можем применять оператор == к значениям этого типа. Вот почему выражения 4 == 4 и "раз" /= "два" проходят проверку типов.

Классы типов часто путают с классами в языках вроде Java, Python, C++ и им подобных, что сбивает с толку множество людей. В вышеперечисленных языках классы – это нечто вроде чертежей, по которым потом создаются объекты, хранящие некое состояние и способные производить некие действия. Мы не создаём типы из классов типов – вместо этого мы сначала создаём свои типы данных, а затем думаем о том, как они могут себя вести. Если то, что мы создали, можно проверить на равенство, – определяем для него экземпляр класса Eq. Если наш тип может вести себя как нечто, что можно упорядочить, – создаём для него экземпляр класса Ord.

Давайте посмотрим, как язык Haskell умеет автоматически делать наши типы экземплярами таких классов типов, как Eq, Ord, Enum, Bounded, Show и Read. Haskell умеет порождать поведение для наших типов в этих контекстах, если мы используем ключевое слово deriving при создании типа данных.

Сравнение людей на равенство

Рассмотрим такой тип данных:

data Person = Person { firstName :: String

                     , lastName :: String

                     , age :: Int

                     }

Тип описывает человека. Предположим, что среди людей не встречаются тёзки одного возраста. Если у нас есть два описания, можем ли мы выяснить, относятся ли они к одному и тому же человеку? Есть ли в такой операции смысл? Конечно, есть. Мы можем сравнить записи и проверить, равны они или нет. Вот почему имело бы смысл определить для нашего типа экземпляр класса Eq. Порождаем экземпляр:

data Person = Person { firstName :: String

                     , lastName :: String

                     , age :: Int

                     } deriving (Eq)

Когда мы определяем экземпляр класса Eq для типа и пытаемся сравнить два значения с помощью операторов == или /=, язык Haskell проверяет, совпадают ли конструкторы значений (хотя в нашем типе только один конструктор), а затем проверяет все данные внутри конструктора на равенство, сравнивая каждую пару полей с помощью оператора ==. Таким образом, типы всех полей также должны иметь определённый экземпляр класса Eq. Так как типы полей нашего типа, String и Int, имеют экземпляры класса Eq, всё в порядке.

Запишем в файл несколько людей:

mikeD = Person {firstName = "Майкл", lastName = "Даймонд", age = 45}

adRock = Person {firstName = "Адам", lastName = "Горовиц", age = 45}

mca = Person {firstName = "Адам", lastName = "Яух", age = 47}

И проверим экземпляр класса Eq:

ghci> mca == adRock

False

ghci> mikeD == adRock

False

ghci> mikeD == mikeD

True

ghci> mca == Person {firstName = "Адам", lastName = "Яух", age = 47}

True

Конечно же, так как теперь тип Person имеет экземпляр класса Eq, мы можем передавать его любым функциям, которые содержат ограничение на класс типа Eq в декларации, например функции elem.

ghci> let beastieBoys = [mca, adRock, mikeD]

ghci> mikeD `elem` beastieBoys

True

Покажи мне, как читать

Классы типов Show и Read предназначены для сущностей, которые могут быть преобразованы в строки и из строк соответственно. Как и для класса Eq, все типы в конструкторе типов также должны иметь экземпляры для классов Show и/или Read, если мы хотим получить такое поведение. Давайте сделаем наш тип данных Person частью классов Show и Read:

data Person = Person { firstName :: String

                     , lastName :: String

                     , age :: Int

                     } deriving (Eq, Show, Read)

Теперь мы можем распечатать запись на экране:

ghci> mikeD

Person {firstName = "Michael", lastName = "Diamond", age = 43}

ghci> "mikeD is: " ++ show mikeD

"mikeD is: Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}"

Если бы мы попытались распечатать запись до того, как предусмотрели для типа Person экземпляры класса Show, язык Haskell пожаловался бы на то, что он не знает, как представить запись в виде строки. Но после того как мы определили экземпляр класса Show, всё проясняется.

Класс Read в чём-то является обратным классом типов для класса Show. Класс Show служит для преобразования значений нашего типа в строку, класс Read нужен для преобразования строк в значения типа. Запомните, что при использовании функции чтения мы должны явно аннотировать тип возвращаемого значения. Если не указать тип результата явно, язык Haskell не сможет угадать, какой тип мы желали бы получить. Чтобы это проиллюстрировать, поместим в файл строку, представляющую некоторого человека, а затем загрузим файл в GHCi:

mysteryDude = "Person { firstName =\"Майкл\"" ++

                     ", lastName =\"Даймонд\"" ++

                     ", age = 45}"

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

ghci> read mysteryDude :: Person

Person {firstName = "Майкл", lastName = "Даймонд", age = 45}

Если далее в программе мы используем результат чтения таким образом, что язык Haskell сможет вывести его тип, мы не обязаны использовать аннотацию типа.

ghci> read mysteryDude == mikeD

True

Так же можно считывать и параметризованные типы, но при этом следует явно указывать все типы-параметры.

Если мы попробуем сделать так:

ghci> read "Just 3" :: Maybe a

то получим сообщение об ошибке: Haskell не в состоянии определить конкретный тип, который следует подставить на место типовой переменной a. Если же мы точно укажем, что хотим получить Int, то всё будет прекрасно:

ghci> read "Just 3" :: Maybe Int

Just 3

Порядок в суде!

Класс типов Ord, предназначенный для типов, значения которых могут быть упорядочены, также допускает автоматическое порождение экземпляров. Если сравниваются два значения одного типа, сконструированные с помощью различных конструкторов данных, то меньшим считается значение, конструктор которого определён раньше. Рассмотрим, к примеру, тип Bool, значениями которого могут быть False или True. Для наших целей удобно предположить, что он определён следующим образом:

data Bool = False | True deriving (Ord)

Поскольку конструктор False указан первым, а конструктор True – после него, мы можем считать, что True больше, чем False.

ghci> True `compare` False

GT

ghci> True > False

True

ghci> True < False

False

Если два значения имеют одинаковый конструктор, то при отсутствии полей они считаются равными. Если поля есть, то выполняется их сравнение. Заметьте, что в этом случае типы полей должны быть частью класса типов Ord.

В типе данных Maybe a конструктор значений Nothing указан раньше Just – это значит, что значение Nothing всегда меньше, чем Just < нечто > , даже если это «нечто» равно минус одному миллиону триллионов. Но если мы сравниваем два значения Just, после сравнения конструкторов начинают сравниваться поля внутри них.

ghci> Nothing < Just 100

True

ghci> Nothing > Just (–49999)

False

ghci> Just 3 `compare` Just 2

GT

ghci>Just 100 > Just 50

True

Но сделать что-нибудь вроде Just (*3) > Just (*2) не получится, потому что (*3) и (*2) – это функции, а они не имеют экземпляров для класса Ord.

Любой день недели

Мы легко можем использовать алгебраические типы данных для того, чтобы создавать перечисления, и классы типов Enum и Bounded помогают нам в этом. Рассмотрим следующий тип:

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Так как все конструкторы значений нульарные (не принимают параметров, то есть не имеют полей), допустимо сделать для нашего типа экземпляр класса Enum. Класс типов Enum предназначен для типов, для значений которых можно определить предшествующие и последующие элементы. Также мы можем определить для него экземпляр класса Bounded – он предназначен для типов, у которых есть минимальное и максимальное значения. Ну и уж заодно давайте сделаем для него экземпляры всех остальных классов типов, которые можно сгенерировать автоматически, и посмотрим, что это даст.

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

  deriving (Eq, Ord, Show, Read, Bounded, Enum)

Так как для нашего типа автоматически сгенерированы экземпляры классов Show и Read, можно конвертировать значения типа в строки и из строк:

ghci> Wednesday

Wednesday

ghci> show Wednesday

"Wednesday"

ghci> read "Saturday" :: Day

Saturday

Поскольку он имеет экземпляры классов Eq и Ord, допускаются сравнение и проверка на равенство:

ghci> Saturday == Sunday

False

ghci> Saturday == Saturday

True

ghci> Saturday > Friday

True

ghci> Monday `compare` Wednesday

LT

Наш тип также имеет экземпляр класса Bounded, так что мы можем найти минимальный и максимальный день.

ghci> minBound :: Day

Monday

ghci> maxBound :: Day

Sunday

Благодаря тому что тип имеет экземпляр класса Enum, можно получать предшествующие и следующие дни, а также задавать диапазоны дней.

ghci> succ Monday

Tuesday

ghci> pred Saturday

Friday

ghci> [Thursday .. Sunday]

[Thursday,Friday,Saturday,Sunday]

ghci> [minBound .. maxBound] :: [Day]

[Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]

Замечательно!

Ранее мы упоминали, что типы [Char] и String являются эквивалентами и могут взаимно заменяться. Это осуществляется с помощью синонимов типов. Синоним типа сам по себе ничего не делает – он просто даёт другое имя существующему типу, облегчая понимание нашего кода и документации. Вот так стандартная библиотека определяет тип String как синоним для [Char]:

type String = [Char]

Ключевое слово type может ввести в заблуждение, потому что на самом деле мы не создаём ничего нового (создаём мы с помощью ключевого слова data), а просто определяем синоним для уже существующего типа.

Если мы создадим функцию, которая преобразует строку в верхний регистр, и назовём её toUpperString, то можем дать ей сигнатуру типа toUpperString :: [Char] –> [Char] или toUpperString :: String –> String. Обе сигнатуры обозначают одно и то же, но вторая легче читается.

Улучшенная телефонная книга

Когда мы работали с модулем Data.Map, то вначале представляли записную книжку в виде ассоциативного списка, а потом преобразовывали его в отображение. Как мы уже знаем, ассоциативный список – это список пар «ключ–значение». Давайте взглянем на этот вариант записной книжки:

phoneBook :: [(String,String)]

phoneBook =

  [("оля","555–29-38")

  ,("женя","452–29-28")

  ,("катя","493–29-28")

  ,("маша","205–29-28")

  ,("надя","939–82-82")

  ,("юля","853–24-92")

  ]

Мы видим, что функция phoneBook имеет тип [(String,String)]. Это говорит о том, что перед нами ассоциативный список, который отображает строки в строки, – но не более. Давайте зададим синоним типа, и мы сможем узнать немного больше по декларации типа:

type PhoneBook = [(String,String)]

Теперь декларация типа для нашей записной книжки может быть такой: phoneBook :: PhoneBook. Зададим также синоним для String.

type PhoneNumber = String

type Name = String

type PhoneBook = [(Name,PhoneNumber)]

Те, кто программирует на языке Haskell, дают синонимы типу String, если хотят сделать объявления более «говорящими» – пояснить, чем являются строки и как они должны использоваться.

Итак, реализуя функцию, которая принимает имя и номер телефона и проверяет, есть ли такая комбинация в нашей записной книжке, мы можем дать ей красивую и понятную декларацию типа:

inPhoneBook :: Name –> PhoneNumber –> PhoneBook –> Bool

inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook

Если бы мы не использовали синонимы типов, тип нашей функции был бы String –> String –> [(String,String)] –> Bool. В этом случае декларацию функции легче понять при помощи синонимов типов. Однако не надо перегибать палку. Мы применяем синонимы типов для того, чтобы описать, как используются существующие типы в наших функциях (таким образом декларации типов лучше документированы), или когда мы имеем дело с длинной декларацией типа, которую приходится часто повторять (вроде [(String,String)]), причём эта декларация обозначает что-то более специфичное в контексте наших функций.

Параметризация синонимов

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

type AssocList k v = [(k,v)]

Функция, которая получает значение по ключу в ассоциативном списке, может иметь тип (Eq k) => k –> AssocList k v –> Maybe v. Тип AssocList – это конструктор типов, который принимает два типа и производит конкретный тип, например AssocList Int String.

Мы можем частично применять функции, чтобы получить новые функции; аналогичным образом можно частично применять типы-параметры и получать новые конструкторы типов. Так же, как мы вызываем функцию, не передавая всех параметров для того, чтобы получить новую функцию, мы будем вызывать и конструктор типа, не указывая всех параметров, и получать частично применённый конструктор типа. Если мы хотим получить тип для отображений (из модуля Data.Map) с целочисленными ключами, можно сделать так:

type IntMap v = Map Int v

или так:

type IntMap = Map Int

В любом случае конструктор типов IntMap принимает один параметр – это и будет типом, в который мы будем отображать Int.

И вот ещё что. Если вы попытаетесь реализовать этот пример, вам потребуется произвести квалифицированный импорт модуля Data.Map. При квалифицированном импорте перед конструкторами типов также надо ставить имя модуля. Таким образом, мы бы записали: IntMap = Map.Map Int.

Убедитесь, что вы понимаете различие между конструкторами типов и конструкторами данных. Если мы создали синоним типа IntMap или AssocList, это ещё не означает, что можно делать такие вещи, как AssocList [(1,2),(4,5),(7,9)]. Это означает только то, что мы можем ссылаться на тип, используя другое имя. Можно написать: [(1,2),(3,5),(8,9)] :: AssocList Int Int, в результате чего числа в списке будут трактоваться как целые – но мы также сможем работать с этим списком как с обычным списком пар целых чисел. Синонимы типов (и вообще типы) могут использоваться в языке Haskell только при объявлении типов. Часть языка, относящаяся к объявлению типов, – собственно объявление типов (то есть при определении данных и типов) или часть объявления после символа :: (два двоеточия). Символ :: используется при декларировании или аннотировании типов.

Иди налево, потом направо

Ещё один чудесный тип, принимающий два других в качестве параметров, – это тип Either. Он определён приблизительно так:

data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)

У него два конструктора данных. Если используется конструктор Left, его содержимое имеет тип a; если Right – содержимое имеет тип b. Таким образом, мы можем использовать данный тип для инкапсуляции значения одного из двух типов. Когда мы работаем с типом Either a b, то обычно используем сопоставление с образцом по Left и Right и выполняем действия в зависимости от того, какой вариант совпал.

ghci> Right 20

Right 20

ghci> Left "в00т"

Left "в00т"

ghci> :t Right 'a'

Right 'a' :: Either a Char ghci> :t Left True

Left True :: Either Bool b

Из приведённого примера следует, что типом значения Left True является Either Bool b. Первый параметр типа Bool, поскольку значение создано конструктором Left; второй же параметр остался полиморфным. Ситуация подобна тому как значение Nothing имеет тип Maybe a.

Мы видели, что тип Maybe главным образом используется для того, чтобы представить результат вычисления, которое может завершиться неудачей. Но иногда тип Maybe не так удобен, поскольку значение Nothing не несёт никакой информации, кроме того что что-то пошло не так. Это нормально для функций, которые могут выдавать ошибку только в одном случае – или если нам просто не интересно, как и почему функция «упала». Поиск в отображении типа Data.Map может завершиться неудачей, только если искомый ключ не найден, так что мы знаем, что случилось. Но если нам нужно знать, почему не сработала некоторая функция, обычно мы возвращаем результат типа Either a b, где a – это некоторый тип, который может нам что-нибудь рассказать о причине ошибки, и b – результат удачного вычисления. Следовательно, ошибки используют конструктор данных Left, правильные результаты используют конструктор Right.

Например, в школе есть шкафчики для того, чтобы ученикам было куда клеить постеры Guns’n’Roses. Каждый шкафчик открывается кодовой комбинацией. Если школьнику понадобился шкафчик, он говорит администратору, шкафчик под каким номером ему нравится, и администратор выдаёт ему код. Если этот шкафчик уже кем-либо используется, администратор не сообщает код – они вместе с учеником должны будут выбрать другой вариант. Будем использовать модуль Data.Map для того, чтобы хранить информацию о шкафчиках. Это будет отображение из номера шкафчика в пару, где первый компонент указывает, используется шкафчик или нет, а второй компонент – код шкафчика.

import qualified Data.Map as Map

data LockerState = Taken | Free deriving (Show, Eq)

type Code = String

type LockerMap = Map.Map Int (LockerState, Code)

Довольно просто. Мы объявляем новый тип данных для хранения информации о том, был шкафчик занят или нет. Также мы создаём синоним для кода шкафчика и для типа, который отображает целые числа в пары из статуса шкафчика и кода. Теперь создадим функцию для поиска кода по номеру. Мы будем использовать тип Either String Code для представления результата, так как поиск может не удаться по двум причинам – шкафчик уже занят, в этом случае нельзя сообщать код, или номер шкафчика не найден вообще. Если поиск не удался, возвращаем значение типа String с пояснениями.

lockerLookup :: Int –> LockerMap –> Either String Code

lockerLookup lockerNumber map =

  case Map.lookup lockerNumber map of

   Nothing –> Left $ "Шкафчик № " ++ show lockerNumber ++

                     " не существует!"

   Just (state, code) –>

      if state /= Taken

        then Right code

        else Left $ "Шкафчик № " ++ show lockerNumber ++ " уже занят!"

Мы делаем обычный поиск по отображению. Если мы получили значение Nothing, то вернём значение типа Left String, говорящее, что такой номер не существует. Если мы нашли номер, делаем дополнительную проверку, занят ли шкафчик. Если он занят, возвращаем значение Left, говорящее, что шкафчик занят. Если он не занят, возвращаем значение типа Right Code, в котором даём студенту код шкафчика. На самом деле это Right String, но мы создали синоним типа, чтобы сделать наши объявления более понятными. Вот пример отображения:

lockers :: LockerMap lockers = Map.fromList

  [(100,(Taken,"ZD39I"))

  ,(101,(Free,"JAH3I"))

  ,(103,(Free,"IQSA9"))

  ,(105,(Free,"QOTSA"))

  ,(109,(Taken,"893JJ"))

  ,(110,(Taken,"99292"))

  ]

Давайте попытаемся узнать несколько кодов.

ghci> lockerLookup 101 lockers

Right "JAH3I"

ghci> lockerLookup 100 lockers

Left "Шкафчик № 100 уже занят!"

ghci> lockerLookup 102 lockers

Left "Шкафчик № 102 не существует!"

ghci> lockerLookup 110 lockers

Left "Шкафчик № 110 уже занят!"

ghci> lockerLookup 105 lockers

Right "QOTSA"

Мы могли бы использовать тип Maybe для представления результата, но тогда лишились бы возможности узнать, почему нельзя получить код. А в нашей функции причина ошибки выводится из результирующего типа.

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

Посмотрите на этот список: [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', поскольку на самом деле они являются конструкторами для числового и символьного типов.

Вырастим-ка дерево

Теперь мы собираемся реализовать бинарное поисковое дерево. Если вам не знакомы поисковые деревья из языков наподобие С, вот что они представляют собой: элемент указывает на два других элемента, один из которых правый, другой – левый. Элемент слева – меньше, чем текущий, элемент справа – больше. Каждый из этих двух элементов также может ссылаться на два других элемента (или на один, или не ссылаться вообще). Получается, что каждый элемент может иметь до двух поддеревьев. Бинарные поисковые деревья удобны тем, что мы знаем, что все элементы в левом поддереве элемента со значением, скажем, пять, будут меньше пяти. Элементы в правом поддереве будут больше пяти. Таким образом, если нам надо найти 8 в нашем дереве, мы начнём с пятёрки, и так как 8 больше 5, будем проверять правое поддерево. Теперь проверим узел со значением 7, и так как 8 больше 7, снова выберем правое поддерево. В результате элемент найдётся всего за три операции сравнения! Если мы бы искали в обычном списке (или в сильно разбалансированном дереве), потребовалось бы до семи сравнений вместо трёх для поиска того же элемента.

ПРИМЕЧАНИЕ. Множества и отображения из модулей Data.Set и Data.Map реализованы с помощью деревьев, но вместо обычных бинарных поисковых деревьев они используют сбалансированные поисковые деревья. Дерево называется сбалансированным, если высоты его левого и правого поддеревьев примерно равны. Это условие ускоряет поиск по дереву. В наших примерах мы реализуем обычные поисковые деревья.

Вот что мы собираемся сказать: дерево – это или пустое дерево, или элемент, который содержит некоторое значение и два поддерева. Такая формулировка идеально соответствует алгебраическому типу данных.

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

Что ж, отлично. Вместо того чтобы вручную создавать дерево, мы напишем функцию, которая принимает дерево и элемент и добавляет элемент к дереву. Мы будем делать это, сравнивая вставляемый элемент с корневым. Если вставляемый элемент меньше корневого – идём налево, если больше – направо. Эту же операцию продолжаем для каждого последующего узла дерева, пока не достигнем пустого дерева. После этого мы добавляем новый элемент вместо пустого дерева.

В языках, подобных С, мы бы делали это, изменяя указатели и значения внутри дерева. В Haskell мы на самом деле не можем изменять наше дерево – придётся создавать новое поддерево каждый раз, когда мы переходим к левому или правому поддереву. Таким образом, в конце функции добавления мы вернём полностью новое дерево, потому что в языке Haskell нет концепции указателей, есть только значения. Следовательно, тип функции для добавления элемента будет примерно следующим: a –> Tree a – > Tree a. Она принимает элемент и дерево и возвращает новое дерево с уже добавленным элементом. Это может показаться неэффективным, но язык Haskell умеет организовывать совместное владение большей частью поддеревьев старым и новым деревьями.

Итак, напишем две функции. Первая будет вспомогательной функцией для создания дерева, состоящего из одного элемента; вторая будет вставлять элемент в дерево.

singleton :: a –> Tree a

singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a –> Tree a –> Tree a

treeInsert x EmptyTree = singleton x

treeInsert x (Node a left right)

    | x == a = Node x left right

    | x < a = Node a (treeInsert x left) right

    | x > a = Node a left (treeInsert x right)

Функция singleton служит для создания узла, который хранит некоторое значение и два пустых поддерева. В функции для добавления нового элемента в дерево мы вначале обрабатываем граничное условие. Если мы достигли пустого поддерева, это значит, что мы в нужном месте нашего дерева, и вместо пустого дерева помещаем одноэлементное дерево, созданное из нашего значения. Если мы вставляем не в пустое дерево, следует кое-что проверить. Первое: если вставляемый элемент равен корневому элементу – просто возвращаем дерево текущего элемента. Если он меньше, возвращаем дерево, которое имеет то же корневое значение и то же правое поддерево, но вместо левого поддерева помещаем дерево с добавленным элементом. Так же (но с соответствующими поправками) обстоит дело, если значение больше, чем корневой элемент.

Следующей мы напишем функцию для проверки, входит ли некоторый элемент в наше дерево или нет. Для начала определим базовые случаи. Если мы ищем элемент в пустом дереве, его там определённо нет. Заметили – такой же базовый случай мы использовали для поиска элемента в списке? Если мы ищем в пустом списке, то ничего не найдём. Если ищем не в пустом дереве, надо проверить несколько условий. Если элемент в текущем корне равен тому, что мы ищем, – отлично. Ну а если нет, тогда как быть?.. Мы можем извлечь пользу из того, что все элементы в левом поддереве меньше корневого элемента. Поэтому, если искомый элемент меньше корневого, начинаем искать в левом поддереве. Если он больше – ищем в правом поддереве.

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

Мы уже изучили несколько стандартных классов типов языка Haskell и некоторые типы, имеющие для них экземпляры. Также мы знаем, как автоматически сделать для наших типов экземпляры стандартных классов, стоит только попросить Haskell автоматически сгенерировать нужное нам поведение. В этой главе будет рассказано о том, как писать свои собственные классы типов и как создавать экземпляры класса вручную.

Вспомним, что классы типов по сути своей подобны интерфейсам. Они определяют некоторое поведение (проверку на равенство, проверку на «больше-меньше», перечисление элементов). Типы, обладающие таким поведением, можно сделать экземпляром класса типов. Поведение класса типов определяется функциями, входящими в класс, или просто декларацией класса; элементы класса мы потом должны будем реализовать. Таким образом, если мы говорим, что для типа имеется экземпляр класса, то подразумеваем, что можем использовать все функции, определённые в классе типов в нашем типе.

ПРИМЕЧАНИЕ. Классы типов практически не имеют ничего общего с классами в таких языках, как Java или Python. Это сбивает с толку, поэтому советую вам забыть всё, что вы знаете о классах в императивных языках!

«Внутренности» класса Eq

Возьмём для примера класс типов Eq: он используется в отношении неких значений, которые можно проверить на равенство. Он определяет операторы == и /=. Если у нас есть тип, скажем, Car (автомобиль), и сравнение двух автомобилей с помощью функции == имеет смысл, то имеет смысл и определить для типа Car экземпляр класса Eq.

Вот как класс Eq определён в стандартном модуле:

class Eq a where

    (==) :: a –> a –> Bool

    (/=) :: a –> a –> Bool

    x == y = not (x /= y)

    x /= y = not (x == y)

О-хо-хо!.. Новый синтаксис и новые ключевые слова. Не беспокойтесь, скоро мы это поясним. Прежде всего, мы записали декларацию class Eq a where – это означает, что мы определяем новый класс, имя которого Eq. Идентификатор a – это переменная типа; иными словами, идентификатор играет роль типа, который в дальнейшем будет экземпляром нашего класса. Эту переменную необязательно называть именно a; пусть даже имя не состоит из одной буквы, но оно непременно должно начинаться с символа в нижнем регистре. Затем мы определяем несколько функций. Нет необходимости писать реализацию функций – достаточно только декларации типа.

Некоторым будет проще понять эту декларацию, если мы запишем class Eq equatable where, а затем декларации функций, например (==) :: equatable –> equatable –> Bool.

Мы определили тела функций для функций в классе Eq, притом определили их взаимно рекурсивно. Мы записали, что два экземпляра класса Eq равны, если они не отличаются, и что они отличаются, если не равны. Необязательно было поступать так, и всё же скоро мы увидим, чем это может быть полезно.

Если записать декларацию class Eq a where, описать в ней функцию таким образом: (==) :: a -> a -> Bool, а затем посмотреть объявление этой функции, мы увидим следующий тип: (Eq a) => a –> a –> Bool.

Тип для представления светофора

Итак, что мы можем сделать с классом после того, как объявили его? Весьма немногое. Но как только мы начнём создавать экземпляры этого класса, то станем получать интересные результаты. Посмотрим на этот тип:

data TrafficLight = Red | Yellow | Green

Он определяет состояние светофора. Обратите внимание, что мы не порождаем автоматическую реализацию классов для него. Мы собираемся реализовать их поддержку вручную, даже несмотря на то, что многое можно было бы сгенерировать автоматически, например экземпляры для классов Eq и Show. Вот как мы создадим экземпляр для класса Eq.

instance Eq TrafficLight where

   Red == Red = True

   Green == Green = True

   Yellow == Yellow = True

   _ == _ = False

Экземпляр создан с помощью ключевого слова instance. Таким образом, ключевое слово class служит для определения новых классов типов, а ключевое слово instance – для того, чтобы сделать для нашего типа экземпляр некоторого класса. Когда мы определяли класс Eq, то записали декларацию class Eq a where и сказали, что идентификатор a играет роль типа, который мы позднее будем делать экземпляром класса. Теперь мы это ясно видим, потому что когда мы создаём экземпляр, то пишем: instance Eq TrafficLight where. Мы заменили идентификатор на название нашего типа.

Так как операция == была определена в объявлении класса через вызов операции /= и наоборот, следует переопределить только одну функцию в объявлении экземпляра класса. Это называется минимальным полным определением класса типов – имеется в виду минимум функций, которые надо реализовать, чтобы наш тип мог вести себя так, как предписано классом. Для того чтобы создать минимально полное определение для класса Eq, нам нужно реализовать или оператор ==, или оператор /=. Если бы класс Eq был определён таким образом:

class Eq a where

    (==) :: a –> a –> Bool

    (/=) :: a –> a –> Bool

то нам бы потребовалось реализовывать обе функции при создании экземпляра, потому что язык Haskell не знал бы, как эти функции взаимосвязаны. В этом случае минимально полным определением были бы обе функции, == и /=.

Мы реализовали оператор == с помощью сопоставления с образцом. Так как комбинаций двух неравных цветов значительно больше, чем комбинаций равных, мы перечислили все равные цвета и затем использовали маску подстановки, которая говорит, что если ни один из предыдущих образцов не подошёл, то два цвета не равны.

Давайте сделаем для нашего типа экземпляр класса Show. Чтобы удовлетворить минимально полному определению для класса Show, мы должны реализовать функцию show, которая принимает значение и возвращает строку:

instance Show TrafficLight where

   show Red = "Красный свет"

   show Yellow = "Жёлтый свет"

   show Green = "Зелёный свет"

Мы снова использовали сопоставление с образцом, чтобы достичь нашей цели. Давайте посмотрим, как это всё работает:

ghci> Red == Red

True

ghci> Red == Yellow

False

ghci> Red `elem` [Red, Yellow, Green]

True

ghci> [Red, Yellow, Green]

[Красный свет,Жёлтый свет,Зелёный свет]

Можно было бы просто автоматически сгенерировать экземпляр для класса Eq с абсолютно тем же результатом (мы этого не сделали в образовательных целях). Кроме того, автоматическая генерация для класса Show просто напрямую переводила бы конструкторы значений в строки. Если нам требуется печатать что-то дополнительно, то придётся создавать экземпляр класса Show вручную.

Наследование классов

Также можно создавать классы типов, которые являются подклассами других классов типов. Декларация класса Num довольно длинна, но вот её начало:

class (Eq a) => Num a where

   ...

Как уже говорилось ранее, есть множество мест, куда мы можем втиснуть ограничения на класс. Наша запись равнозначна записи class Num a where, но мы требуем, чтобы тип a имел экземпляр класса Eq. Это означает, что мы должны определить для нашего типа экземпляр класса Eq до того, как сможем сделать для него экземпляр класса Num. Прежде чем некоторый тип сможет рассматриваться как число, мы должны иметь возможность проверять значения этого типа на равенство.

Ну вот и всё, что надо знать про наследование, – это просто ограничения на класс типа-параметра при объявлении класса. При написании тел функций в декларации класса или при их определении в экземпляре класса мы можем полагать, что тип a имеет экземпляр для класса Eq и, следовательно, допускается использование операторов == и /= со значениями этого типа.

Создание экземпляров классов для параметризованных типов

Но как тип Maybe и списковый тип сделаны экземплярами классов? Тип Maybe отличается, скажем, от типа TrafficLight тем, что Maybe сам по себе не является конкретным типом – это конструктор типов, который принимает один тип-параметр (например, Char), чтобы создать конкретный тип (как Maybe Char). Давайте посмотрим на класс Eq ещё раз:

class Eq a where

   (==) :: a –> a –> Bool

   (/=) :: a –> a –> Bool

   x == y = not (x /= y)

   x /= y = not (x == y)

Из декларации типа мы видим, что a используется как конкретный тип, потому что все типы в функциях должны быть конкретными (помните, мы обсуждали, что не можем иметь функцию типа a –> Maybe, но можем – функцию типа: a –> Maybe a или Maybe Int –> Maybe String). Вот почему недопустимо делать что-нибудь в таком роде:

instance Eq Maybe where

   ...

Ведь, как мы видели, идентификатор a должен принимать значение в виде конкретного типа, а тип Maybe не является таковым. Это конструктор типа, который принимает один параметр и производит конкретный тип.

Было бы скучно прописывать instance Eq (Maybe Int) where, instance Eq (Maybe Char) where и т. д. для всех существующих типов. Вот почему мы можем записать это так:

instance Eq (Maybe m) where

   Just x == Just y = x == y

   Nothing == Nothing = True

   _ == _ = False

Это всё равно что сказать, что мы хотим сделать для всех типов формата Maybe < нечто > экземпляр класса Eq. Мы даже могли бы записать (Maybe something), но обычно программисты используют одиночные буквы, чтобы придерживаться стиля языка Haskell. Выражение (Maybe m) выступает в качестве типа a в декларации class Eq a where. Тип Maybe не является конкретным типом, а Maybe m – является. Указание типа-параметра (m в нижнем регистре) свидетельствует о том, что мы хотим, чтобы все типы вида Maybe m, где m – любой тип, имели экземпляры класса Eq.

Однако здесь есть одна проблема. Заметили? Мы используем оператор == для содержимого типа Maybe, но у нас нет уверенности, что то, что содержит тип Maybe, может быть использовано с методами класса Eq. Вот почему необходимо поменять декларацию экземпляра на следующую:

instance (Eq m) => Eq (Maybe m) where

   Just x == Just y = x == y

   Nothing == Nothing = True

   _ == _ = False

Нам пришлось добавить ограничение на класс. Таким объявлением экземпляра класса мы утверждаем: необходимо, чтобы все типы вида Maybe m имели экземпляр для класса Eq, но при этом тип m (тот, что хранится в Maybe) также должен иметь экземпляр класса Eq. Такой же экземпляр породил бы сам язык Haskell, если бы мы воспользовались директивой deriving.

В большинстве случаев ограничения на класс в декларации класса используются для того, чтобы сделать класс подклассом другого класса. Ограничения на класс в определении экземпляра используются для того, чтобы выразить требования к содержимому некоторого типа. Например, в данном случае мы требуем, чтобы содержимое типа Maybe также имело экземпляр для класса Eq.

При создании экземпляров, если вы видите, что тип использовался как конкретный при декларации (например, a –> a –> Bool), а вы реализуете экземпляр для конструктора типов, следует предоставить тип-параметр и добавить скобки, чтобы получить конкретный тип.

Примите во внимание, что тип, экземпляр для которого вы пытаетесь создать, заменит параметр в декларации класса. Параметр a из декларации class Eq a where будет заменён конкретным типом при создании экземпляра; попытайтесь в уме заменить тип также и в декларациях функций. Сигнатура (==) :: Maybe –> Maybe –> Bool не имеет никакого смысла, но сигнатура (==) :: (Eq m) => Maybe m –> Maybe m –> Bool имеет. Впрочем, это нужно только для упражнения, потому что оператор == всегда будет иметь тип (==) :: (Eq a) => a –> a –> Bool независимо от того, какие экземпляры мы порождаем.

О, и ещё одна классная фишка! Если хотите узнать, какие экземпляры существуют для класса типов, вызовите команду : info в GHCi. Например, выполнив команду :info Num, вы увидите, какие функции определены в этом классе типов, и выведете список принадлежащих классу типов. Команда :info также работает с типами и конструкторами типов. Если выполнить :info Maybe, мы увидим все классы типов, к которым относится тип Maybe. Вот пример:

ghci> :info Maybe

data Maybe a = Nothing | Just a -- Defined in Data.Maybe

instance Eq a => Eq (Maybe a) -- Defined in Data.Maybe

instance Monad Maybe -- Defined in Data.Maybe

instance Functor Maybe -- Defined in Data.Maybe

instance Ord a => Ord (Maybe a) -- Defined in Data.Maybe

instance Read a => Read (Maybe a) -- Defined in GHC.Read

instance Show a => Show (Maybe a) -- Defined in GHC.Show

Мы уже встречали множество классов типов из стандартной библиотеки. Ознакомились с классом Ord, предусмотренным для сущностей, которые можно упорядочить. Вдоволь набаловались с классом Eq, предназначенным для сравнения на равенство. Изучили класс Show, предоставляющий интерфейс для типов, которые можно представить в виде строк. Наш добрый друг класс Read помогает, когда нам надо преобразовать строку в значение некоторого типа. Ну а теперь приступим к рассмотрению класса типов Functor, предназначенного для типов, которые могут быть отображены друг в друга.

Возможно, в этот момент вы подумали о списках: ведь отображение списков – это очень распространённая идиома в языке Haskell. И вы правы: списковый тип имеет экземпляр для класса Functor.

Нет лучшего способа изучить класс типов Functor, чем посмотреть, как он реализован. Вот и посмотрим:

fmap :: (a -> b) -> f a -> f b

Итак, что у нас имеется? Класс определяет одну функцию fmap и не предоставляет для неё реализации по умолчанию. Тип функции fmap весьма интересен. Во всех вышеприведённых определениях классов типов тип-параметр, игравший роль типа в классе, был некоторого конкретного типа, как переменная a в сигнатуре (==) :: (Eq a) => a –> a –> Bool. Но теперь тип-параметр f не имеет конкретного типа (нет конкретного типа, который может принимать переменная, например Int, Bool или Maybe String); в этом случае переменная – конструктор типов, принимающий один параметр. (Напомню: выражение Maybe Int является конкретным типом, а идентификатор Maybe – конструктор типов с одним параметром.) Мы видим, что функция fmap принимает функцию из одного типа в другой и функтор, применённый к одному типу, и возвращает функтор, применённый к другому типу.

Если это звучит немного непонятно, не беспокойтесь. Всё прояснится, когда мы рассмотрим несколько примеров.

Гм-м… что-то мне напоминает объявление функции fmap! Если вы не знаете сигнатуру функции map, вот она:

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

О, как интересно! Функция map берёт функцию из a в b и список элементов типа a и возвращает список элементов типа b. Друзья, мы только что обнаружили функтор! Фактически функция map – это функция fmap, которая работает только на списках. Вот как список сделан экземпляром класса Functor:

instance Functor [] where

   fmap = map

И всё! Заметьте, мы не пишем instance Functor [a] where, потому что из определения функции

fmap :: (a –> b) –> f a –> f b

мы видим, что параметр f должен быть конструктором типов, принимающим один тип. Выражение [a] – это уже конкретный тип (список элементов типа a), а вот [] – это конструктор типов, который принимает один тип; он может производить такие конкретные типы, как [Int], [String] или даже [[String]].

Так как для списков функция fmap – это просто map, то мы получим одинаковые результаты при их использовании на списках:

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

ghci>fmap (*2) [1..3]

[2,4,6]

ghci> map (*2) [1..3]

[2,4,6]

Что случится, если применить функцию map или fmap к пустому списку? Мы получим опять же пустой список. Но функция fmap преобразует пустой список типа [a] в пустой список типа [b].

Экземпляр класса Functor для типа Maybe

Типы, которые могут вести себя как контейнеры по отношению к другим типам, могут быть функторами. Можно представить, что списки – это коробки с бесконечным числом отсеков; все они могут быть пустыми, или же один отсек заполнен, а остальные пустые, или несколько из них заполнены. А что ещё умеет быть контейнером для других типов? Например, тип Maybe. Он может быть «пустой коробкой», и в этом случае имеет значение Nothing, или же в нём хранится какое-то одно значение, например "ХА-ХА", и тогда он равен Just "ХА-ХА".

Вот как тип Maybe сделан функтором:

instance Functor Maybe where

   fmap f (Just x) = Just (f x)

   fmap f Nothing = Nothing

Ещё раз обратите внимание на то, как мы записали декларацию instance Functor Maybe where вместо instance Functor (Maybe m) where – подобно тому как мы делали для класса YesNo. Функтор принимает конструктор типа с одним параметром, не конкретный тип. Если вы мысленно замените параметр f на Maybe, функция fmap работает как (a –> b) –> Maybe a –> Maybe b, только для типа Maybe, что вполне себя оправдывает. Но если заменить f на (Maybe m), то получится (a –> b) –> Maybe m a –> Maybe m b, что не имеет никакого смысла, так как тип Maybe принимает только один тип-параметр.

Как бы то ни было, реализация функции fmap довольно проста. Если значение типа Maybe – это Nothing, возвращается Nothing. Если мы отображаем «пустую коробку», мы получим «пустую коробку», что логично. Точно так же функция map для пустого списка возвращает пустой список. Если это не пустое значение, а некоторое значение, упакованное в конструктор Just, то мы применяем функцию к содержимому Just:

ghci> fmap (++ " ПРИВЕТ, Я ВНУТРИ JUST") (Just "Серьёзная штука.")

Just "Серьёзная штука. ПРИВЕТ, Я ВНУТРИ JUST"

ghci> fmap (++ " ПРИВЕТ, Я ВНУТРИ JUST") Nothing

Nothing

ghci> fmap (*2) (Just 200)

Just 400

ghci> fmap (*2) Nothing

Nothing

Деревья тоже являются функторами

Ещё один тип, который можно отображать и сделать для него экземпляр класса Functor, – это наш тип Tree. Дерево может хранить ноль или более других элементов, и конструктор типа Tree принимает один тип-параметр. Если бы мы хотели записать функцию fmap только для типа Tree, её сигнатура выглядела бы так: (a –> b) –> Tree a –> Tree b.

Для этой функции нам потребуется рекурсия. Отображение пустого дерева возвращает пустое дерево. Отображение непустого дерева – это дерево, состоящее из результата применения функции к корневому элементу и из правого и левого поддеревьев, к которым также было применено отображение.

instance Functor Tree where

   fmap f EmptyTree = EmptyTree

   fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

Проверим:

ghci> fmap (*2) EmptyTree

EmptyTree

ghci> fmap (*4) (foldr treeInsert EmptyTree [5,7,3])

Node 20 (Node 12 EmptyTree EmptyTree) (Node 28 EmptyTree EmptyTree)

Впрочем, тут следует быть внимательным! Если тип Tree используется для представления бинарного дерева поиска, то нет никакой гарантии, что дерево останется таковым после применения к каждому его узлу некоторой функции. Проход по дереву функцией, скажем, negate превратит дерево поиска в обычное дерево.

И тип Either является функтором

Отлично! Ну а теперь как насчёт Either a b? Можно ли сделать его функтором? Класс типов Functor требует конструктор типов с одним параметром, а у типа Either их два. Гм-м… Придумал – мы частично применим конструктор Either, «скормив» ему один параметр, и таким образом он получит один свободный параметр. Вот как для типа Either определён экземпляр класса Functor в стандартных библиотеках:

instance Functor (Either a) where

   fmap f (Right x) = Right (f x)

   fmap f (Left x) = Left x

Что же здесь происходит? Как видно из записи, мы сделали экземпляр класса не для типа Either, а для Either a. Это потому, что Either – конструктор типа, который принимает два параметра, а Either a – только один. Если бы функция fmap была только для Either a, сигнатура типа выглядела бы следующим образом:

(b –> c) –> Either a b –> Either a c

поскольку это то же самое, что

(b –> c) –> (Either a) b –> (Either a) c

В реализации мы выполняем отображение в конструкторе данных Right, но не делаем этого в Left. Почему? Вспомним, как определён тип Either a b:

data Either a b = Left a | Right b

Если мы хотим применять некую функцию к обеим альтернативам, параметры a и b должны конкретизироваться одним и тем же типом. Если попытаться применить функцию, которая принимает строку и возвращает строку, то b у нас – строка, а a – число; это не сработает. Также, когда мы смотрели на тип функции fmap для типа Either a, то видели, что первый параметр не изменяется, а второй может быть изменён; первый параметр актуализируется конструктором данных Left.

Здесь можно продолжить нашу аналогию с коробками, представив часть Left как пустую коробку, на которой сбоку записано сообщение об ошибке, поясняющее, почему внутри пусто.

Отображения из модуля Data.Map также можно сделать функтором, потому что они хранят (или не хранят) значения. Для типа Map k v функция fmap будет применять функцию v –> v' на отображении типа Map k v и возвращать отображение типа Map k v'.

ПРИМЕЧАНИЕ. Обратите внимание: апостроф не имеет специального значения в типах (как не имеет его и в именовании значений). Этот символ используется для обозначения схожих понятий, незначительно отличающихся друг от друга.

Попытайтесь самостоятельно догадаться, как для типа Map k определён экземпляр класса Functor!

На примере класса типов Functor мы увидели, что классы типов могут представлять довольно мощные концепции высокого порядка. Также немного попрактиковались в частичном применении типов и создании экземпляров. В одной из следующих глав мы познакомимся с законами, которые должны выполняться для функторов.