Типы и классы

В результате изучения материала главы 5 студент должен: знать

• • систему классов в языке Haskell;
• • как определять экземпляры классов;
• • состав некоторых стандартных классов; уметь
• • описывать собственные классы и экземпляры классов;
• • применять систему классов для описания полиморфных функций;
• • пользоваться стандартными типами Maybe и Either для представления неопределенных значений;

владеть

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

Определение классов

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

Итак, класс — это набор операций (функций), которые могут применяться к объектам определенных типов. В языке Haskell классы определяются формально, т. е. просто объявляется набор функций и бинарных операций, которые могут получать в качестве аргументов или возвращать результат определенного типа. Конкретный тип объявляется экземпляром класса, если для него определены все функции, объявленные в классе. Если некоторый тип объявлен как экземпляр некоторого класса, то мы будем также говорить, что тип принадлежит этому классу. Фактически любой тип может принадлежать любому количеству классов, в этом смысле понятие класса в Haskell довольно близко соответствует понятиям интерфейса в традиционных языках программирования, однако есть и глубокие отличия, которые делают аппарат классов мощным выразительным средством языка.

В языке Haskell изначально определено довольно большое количество классов, которым принадлежат стандартные типы языка. Например, нам уже встречался класс Eq, содержащий операции сравнения ¹ == * и ' ! =¹. Все стандартные примитивные типы, такие как Int, Char, Bool, принадлежат этому классу, так как для них определены соответствующие операции. Для того чтобы объявить, что заданный тип принадлежит некоторому классу (определить экземпляр класса), нужно предоставить реализацию всех функций, определенных в классе.

Рассмотрим определение класса Eq, как оно представлено в стандартной библиотеке языка:

class Eq a where

(==), (≠): а -> а -> Bool.

х ≠ у = not (х == у) В этом определении вводится идентификатор класса Eq с одним параметром а. Далее в классе объявляются две бинарные операции с обозначениями ¹ ==¹ и ' ! =', типы которых содержат вхождения параметра а. Далее задается «реализация по умолчанию» для одной из этих операций — операции ' ! =¹. Это позволит в дальнейшем при определении экземпляра класса ограничиваться определением только одной операции — ^f ==¹, тогда в качестве реализации для второй операции ' ! =¹ будет выбрана реализация по умолчанию.

Для того чтобы определить экземпляр класса Eq, нужно указать, что некоторый тип «принадлежит» классу Eq, и описать реализацию операций этого класса — в случае класса Eq это будет реализация операции * ==¹. Вот как можно, например, определить реализацию операций сравнения на равенство для типа Bool: instance Eq Bool where

True == True = True.

False == False = True.

== _ = False.

В этом определении идентификатор типа Bool занимает позицию фактического параметра класса Eq. Тем самым объявляется, что тип Bool является экземпляром класса Eq, а далее приведены уравнения, определяющие, что два логических значения равны только в том случае, когда они оба образованы конструкторами True или оба — False. Аналогичным образом можно было бы привести описания реализаций класса Eq и для всех остальных примитивных типов, хотя, конечно, на самом деле такое определение корректными средствами языка фактически можно выполнить только для типа Bool, поскольку значений остальных типов слишком много, иногда (как для типа Integer) — бесконечно много.

Легко определяются экземпляры класса Eq для некоторых сложных типов, например для списков и кортежей. Вот как, например, будет выглядеть определение экземпляра класса для списков: instance Eq, а => Eq [a] where [] == [] = True.

(x:xs) == (у: ys) = x == у && xs == ys == = False.

Здесь, во-первых, имеется ограничение (Eq, а =>) на тип элементов списка. Сравнивать списки можно только в том случае, если элементы списков можно сравнить между собой. Далее, первое уравнение в определении операции сравнения говорит о том, что два пустых списка равны между собой. В правой части второго уравнения имеются два применения операции сравнения на равенство. Одно из них — сравнение первых элементов списков, это та операция, которая может быть применена, поскольку задан контекст, согласно которому элементы списков принадлежат классу Eq. Второе применение — это рекурсивное обращение к операции сравнения списков меньшей длины. Третье уравнение в определении реализации равенства списков говорит о том, что списки разной длины не равны между собой.

Разумеется, этот экземпляр класса Eq уже определен в языке, фактически мы им пользовались, например, при сравнении строк. Заметим, что поскольку сравнение списков определено только для случая, когда сравнение определено для элементов, то ошибкой было бы сравнивать между собой списки из несравнимых элементов, скажем, функций. Сравнение такого списка даже с пустым списком является синтаксической ошибкой. Проверку произвольного списка на пустоту нужно делать с помощью стандартной функции null, как, например, это сделано в листинге 4.18.

Также определим экземпляр этого же класса для кортежей из двух элементов произвольного типа: instance (Eq a, Eq b) => Eq (a, b) where

(al, bl) == (a2, b2) = al == a2 && bl == b2.

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

Описание экземпляра класса позволяет включить в этот класс новый тин. Например, мы можем включить в класс наш тип двоичных деревьев — Tree. Для этого нужно определить реализацию, по крайней мере, операции «равно» для объектов типа Tree. Мы будем считать равными деревья, имеющие одинаковую структуру и содержащие в соответствующих узлах равные значения. Такое определение подразумевает, что над значениями узлов также можно выполнять операцию сравнения с помощью оператора (==). Таким образом, мы должны задать реализацию с контекстом типа, который накладывает ограничение на параметр типа Tree. Выглядеть такое определение будет следующим образом (листинг 5.1).

Листинг 5.1. Описание функции сравнения деревьев instance Eq, а => Eq (Tree a) where Null == Null = True.

• (Tree nodel til tl2) == (Tree node2 t21 t22) =
• (nodel == node2) && (til == t21) && (tl2 == t22)

_ == _ = False.

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

Ранее мы использовали еще один стандартный класс языка Haskell класс Ord, задающий набор операций сравнения значений. Этот класс является расширением класса Eq, поскольку в него, наряду с «новыми» операциями ¹ <^f, ' >¹, * <=^! и ¹ >=¹, входят и операции класса Eq. Определение класса Ord в стандартной библиотеке выглядит следующим образом: class Eq, а => Ord a where

(), <=): а -> а -> Bool.

X <= у = X < у I I X == у.

X >= у = X > у I I X == у х = у).

X > у = not (х <= у).

«Базовый» класс участвует в этом определении в виде контекста, описывающего ограничение на определяемый параметр класса. Приведенное определение класса Ord можно читать следующим образом: «при условии, что тип, а принадлежит классу Eq, определение класса Ord для такого типа будет содержать набор операций ' <¹, ¹ >¹, '=' типа, а -> а -> Bool, при этом имеют место следующие реализации этих операций «по умолчанию» … «. Мы видим, что фактически в классе определены реализации «но умолчанию» для всех операций. Не означает ли это, что при определении экземпляра класса мы вообще можем ничего не реализовывать? Конечно же, нет. Но мы теперь можем определить любую из этих четырех операций, и тогда действительно все остальные будут определены через одну только эту операцию «по умолчанию». Например, если мы определим операцию ¹ <=', то тем самым будет определена операция ¹ >¹ через ее отрицание, а значит, будут также определены и операции ¹ >= * и ' <'. Говорят, что для класса есть «минимально необходимый набор операций», которые нужно реализовать для того, чтобы экземпляр класса был полностью определен. Для класса Eq таким минимально необходимым набором являются операция ¹ ==¹ или операция ' /=^?. Фактически мы можем определить операцию ^f /=^?, тогда операция ¹ == * будет определена по умолчанию, как ее отрицание. Для класса Ord минимально необходимым набором операций является любая из операций сравнений. Разумеется, мы вольны определить и другие операции, но на самом деле это бессмысленно и, зачастую, опасно, поскольку нарушает изначальный смысл, заложенный в операции класса.

Экземпляры класса Ord также имеются для большого набора стандартных типов. Приведем описания экземпляров класса Ord для типов Bool и списков: instance Ord Bool where

False < True = True _ < _ = False.

Фактически такая реализация задает упорядоченность логических значений: значение False меньше True. Остальные операции можно не определять, их определения возьмутся из описания класса Ord: instance Ord, а => Ord [a] where

[] < (у:уs) = True.

(x:xs) < (у: ys) = x < у | | (x ==.

у && xs < ys).

< _ = False.

Для списков мы определили то, что обычно называется лексикографическим порядком: результат сравнения списков определяется результатом сравнения первых неравных друг другу элементов. Если же один из списков является строгим префиксом другого, то более короткий список считается меньшим, чем более длинный. Такое определение совершенно естественно еще и потому, что задает полный порядок на всем множестве списков, элементы которых сравнимы по величине друг с другом. Конечно, порядок на множестве списков можно было бы определить и по-другому, но операции сравнения предполагают наличие определенного контракта — набора правил, которым должны удовлетворять реализации операций. Для операций сравнения таким контрактом будет тот факт, что операции ¹ <' и ¹ >¹ определяют строгий порядок, а операции ' =' — нестрогий порядок.

Определим экземпляр класса Ord для двоичных деревьев. Описание этого экземпляра класса можно сделать разными способами, но нужно следить за тем, чтобы контракт класса не был бы нарушен. Например, если определить сравнение деревьев следующим образом:

instance Ord, а => Ord (Tree a) where Null < Tree _ _ _ = True.

Tree rootl til trl < Tree root2 tl2 tr2 =.

rootl < root2 && til < tl2 && trl < tr2.

< _ = False.

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

instance Ord, а => Ord (Tree a) where Null < Tree _ _ _ = True.

Tree rootl til trl < Tree root2 tl2 tr2 = rootl < root2 | | rootl == root2 && (.

til < tl2 | | til == tr2 && trl < tr2).

< _ = False.

В этой реализации мы прежде всего сравниваем конструкторы, считая, что значение, созданное с помощью конструктора Null, всегда меньше любого значения, созданного конструктором Tree. Затем, если оба сравниваемые значения созданы конструктором Tree, сравниваем значения первого аргумента конструкторов. Если и это сравнение не определило результат, то сравниваются вторые аргументы конструктора, и т. д.

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

data Tree, а = Null | Tree a (Tree a) (Tree a) deriving (Eq, Ord).

Есть еще несколько классов, для которых имеются «стандартные» реализации. Среди них стоит, прежде всего, упомянуть классы Show и Read, в которых объявляются операции, позволяющие преобразовать значение в строку (класс Show) и, наоборот, преобразовать строку в значение некоторого типа (класс Read).

В классе Show определены три функции: class Show a where

showsPrec:: Int -> a -> String -> String.

show:: a -> String.

showList:: [a] -> String -> String.

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

Функция showList, как понятно из ее названия и сигнатуры, предназначена для преобразования в строку списка значений. Тип списка является экземпляром класса Show при условии, что элементы списка принадлежат этому классу. Однако иногда «стандартное» представление списков в виде строки неудобно, и в этом случае можно переопределить функцию showList так, чтобы обеспечить специальный способ представления списков для данного типа элементов. Так, список символов представляется в виде изображения строки.

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

data Tree, а = Null | Tree a (Tree a) (Tree a) deriving Show то в результате применения функции show к значению Tree 12 Null (Tree 15 Null Null) получится строка «Tree 12 Null (Tree 15 Null Null)». Интерпретатор GHC, выводя вычисленное значение, использует именно функцию show для представления результата.

Конечно, не обязательно использовать именно такой подход для представления значения в виде строки. Например, можно задать следующее определение экземпляра класса Show для двоичного дерева: instance Show, а => Show (Tree a) where show Null = «show (Tree root tl tr) =.

" («++ show tl ++ show root ++ show tr ++ «)» .

В этом случае значение Tree 12 Null (Tree 15 Null Null) будет представлено строкой ¹¹ (. 12 (. 15 .)) «.

Класс Read более сложен, и мы не будем пытаться реализовывать собственные функции для преобразования строки в значение некоторого типа. Однако, конечно же, основная функция этого класса read (строго говоря, в последних версиях языка эта функция уже не входит в определение класса, но определяется через функции из этого класса) применима к строкам для того, чтобы получить значение одного из стандартных типов. Например, выражение read «12» может выдать в качестве результата целое число 12. Однако здесь есть некоторые сложности. Число 12 действительно получится, если контекст вычисления подразумевает, что тип результата должен быть Int или Integer. Компилятору тин результата может быть и не известен. Попробуем, например, запросить тип выражения read «12» с помощью инструкции ¹ :t^!:

" :t read «12» .

read «12»:: Read a => a.

Как видим, ответ содержит мало информации: полученное значение будет иметь тип а, если для этого типа определен экземпляр класса Read. Попытка вычислить значение этого выражения также будет неудачной:

" read «12» .

No instance for (Read aO) arising from a use of 'read'.

The type variable 'aO' is ambiguous.

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

" read «12»:: Integer 12.

Как видим, теперь значение выражения вычисляется без проблем.

Теперь, если в определении типа Tree задать предложение deriving следующим образом:

data Tree, а = Null | Tree a (Tree a) (Tree a) deriving (Show, Read) мы сможем преобразовывать как строку в дерево, так и дерево в строку. Например, можно вычислить значения выражения read ¹¹ Tree 12 Null (Tree 15 Null Null).

" read «Tree 12 Null (Tree 15 Null Null) »:: Tree Integer.

Tree 12 Null (Tree 15 Null Null).

Здесь функция read используется для преобразования из строки в значение типа дерева («чтения» строки), а затем для вывода результата применяется функция show, которая, наоборот, преобразует значение типа Tree в строку.

Отметим, что значения функциональных типов не могут быть ни прочитаны, ни преобразованы в строку, так что, например, выражение read «х -> х»: Int -> Int не может быть вычислено.