Полиморфизм

В первой лекции уже было показано, что функциональная парадигма прог­рам­ми­ро­ва­ния поддерживает чистый или параметрический полиморфизм. Однако большинство сов­ре­менных языков программирования не обходятся без так называемого полиморфизма ad hoc, или перегрузки. Например, перегрузка практически повсеместно используется для сле­дующих целей:

· Литералы 1, 2, 3 и т.д. (т.е. цифры) используются как для записи целых чисел, так и для за­писи чисел произвольной точности.

· Арифметические операции (например, сложение — знак " + ") используются для ра­бо­ты с данными различных типов (в том числе и с нечисловыми данными, например — кон­катенация для строк).

· Оператор сравнения (в Haskell’е знак двойного равенства — " == ") используется для срав­нения данных различных типов.

Перегруженное поведение операций различное для каждого типа данных (зачастую та­кое поведение вообще может быть не определено или определено ошибочно), в то время, как в параметрическом полиморфизме тип данных, вообще говоря, не важен. Однако в Has­kell’е есть механизм для использования перегрузки.

Рассмотреть возможность использования полиморфизма ad hoc проще всего на примере опе­рации сравнения. Существует большое множество типов, для которых можно и це­ле­со­образно переопределить операцию сравнения, но для некоторых типов эта операция бес­полезна. Например, сравнение функций бессмысленно, функции необходимо вы­чис­лять и сравнивать результаты этих вычислений. Однако, например, может возникнуть не­об­ходимость сравнивать списки. Конечно, здесь речь идет о сравнении значений, а не сравнении ука­зателей (как, например, это сделано в Java).

Рассмотрим функцию element, которая возвращает значение истины в зависимости от то­го, присутствует заданный элемент в заданном списке, или нет (в целях стиля данная фун­кция описана в инфиксной форме):

x `element` [] = False

x `element` (y:ys) = (x == y) || (x `element` ys)

Здесь видно, что у функции element тип (a ® [a] ® Bool), но при этом тип операции " == " должен быть (a ® a ® Bool). Т.к. переменная типа a может обозначать любой тип (в том числе и список), целесообразно переопределить операцию " == " для работы с лю­бым типом данных.

Классы типов являются решением этой проблемы в Haskell’е. Для того, чтобы рас­смот­реть этот механизм в действии далее определяется класс типов, содержащий оператор ра­вен­ства.

class Eq a where

(==) :: a -> a -> Bool

В этой конструкции использованы служебные слова "class" и "where", а также пе­ре­мен­ная типов a. Символ "Eq" является именем определяемого класса. Эта запись может быть прочитана следующим образом: "Тип a является экземпляром класса Eq, если для это­го типа перегружена операция сравнения " == " соответствующего типа". Необходимо от­метить, что операция сравнения должна быть определена на паре объектов одного и то­го же типа.

Ограничение того факта, что тип a должен быть экземпляром класса Eq записывается как (Eq a). Поэтому выражение (Eq a) не является описанием типа, но оно описывает ог­ра­ни­чение, накладываемое на тип a, и это ограничение в Haskell’е называется контекстом. Кон­тексты располагаются перед определением типов и отделяются от них символами " => ":

(==) :: (Eq a) => a -> a -> Bool

Эта запись может быть прочитана как "Для каждого типа a, который является эк­зем­пля­ром класса Eq, определена операция " == ", которая имеет тип (a ® a ® Bool)". Эта опе­рация должна быть использована в функции element, поэтому ограничение рас­про­с­т­ра­ня­ется и на неё. В этом случае необходимо явно указывать тип функции:

element :: (Eq a) => a -> [a] -> Bool

Этой записью декларируется тот необходимый факт, что функция element определена не для всех типов данных, но только для тех, для которых определена соответствующая опе­рация сравнения.

Однако теперь возникает проблема определения того, какие типы являются эк­зем­пля­ра­ми класса Eq. Для этого в Haskell’е есть служебное слово "instance". Например, для того, что­бы предписать, что тип Integer является экземпляром класса Eq, необходимо написать:

instance Eq Integer where

x == y = x `integerEq` y

В этом выражении определение операции " == " называется определением метода (как в объектно-ориентированной парадигме). Функция integerEq может быть любой (и не обя­за­тельно инфиксной), главное, чтобы у нее был тип (a ® a ® Bool). В этом случае скорее все­го подойдет примитивная функция сравнения двух натуральных чисел. В свою очередь про­читать написанное выражение можно следующим образом: "Тип Integer является эк­зем­пляром класса Eq, и далее приводится определение метода, который производит срав­не­ние двух объектов типа Integer".

Таким же образом можно определить операцию сравнения и для бесконечных ре­кур­сив­ных типов. Например, для типа Tree (см. лекцию 4) определение будет выглядеть сле­ду­ющим образом:

instance (Eq a) => Eq (Tree a) where

Leaf a == Leaf b = a == b

(Branch l1 r1) == (Branch l2 r2) = (l1 == l2) && (r1 == r2)

_ == _ = False

Естественно, что если в языке определено понятие класса, должно быть определена и кон­цепция наследования. Хотя в Haskell’е под классом понимается нечто более аб­с­т­рак­т­ное, чем в обычных объектно-ориентированных языках, в Haskell’е также есть и нас­ле­до­ва­ние. Но в то же время концепция наследования определяется столь же изощренно, что и по­нятие класса. Например, от определённого выше класса Eq можно унаследовать класс Ord, который будет представлять сравнимые типы данных. Его определение будет выг­ля­деть следующим образом:

class (Eq a) => Ord a where

(<), (>), (<=), (>=) :: a -> a -> Bool

min, max :: a -> a -> a

Все экземпляры класса Ord должны определять кроме операций "меньше", "больше", "мень­ше или равно", "больше или равно", "минимум" и "максимум" ещё и операцию срав­нения " == ", т.к. её класс Ord наследует от класса Eq.

Самое удивительно заключается в том, что Haskell поддерживает множественное нас­ле­до­вание. В случае использования нескольких базовых классов, всех их просто надо пе­ре­чис­лить через запятую в соответствующей секции. При этом экземпляры классов, уна­с­ле­до­ванных от нескольких базовых классов, должны, естественно, поддерживать и все ме­то­ды базовых классов.