Полиморфизм в Haskell

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

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

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

Параметрический полиморфизм

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

Пример параметрически полиморфной функции:

Prelude> let id x = x
Prelude> :t id
id :: t -> t
Prelude> id True
True
Prelude> id 5
5
Prelude> (id id) 4
4
Prelude> :t id True
id True :: Bool
Prelude> :t (id id)
(id id) :: t -> t

На принимаемое значение функции id не накладывается никаких ограничений. Что мы приняли в качестве аргумента, то и возвращаем. Все конкретные типы начинаются с большой буквы. Здесь у нас тип произволен и используется переменная типа t, вместо неё может быть подставлен любой тип. В примере с выражением (id id) тип внешней функции будет (t -> t) -> (t -> t). Таким образом у внутренней id тип t -> t, а у внешней (t -> t) -> (t -> t). Дальше происходит применение внешней функции id к внутренней функции id. При применении функция становится арности на единицу меньше. Внешняя id оказывается функцией двух аргументов: (t -> t) -> t -> t. К одному своему аргументу возвращает функцию одного аргумента.


Пример параметрически полиморфной функции двух аргументов:

Prelude> let k x y = x
Prelude> k 42 True
42
Prelude> k 42 55
42
Prelude> :t k
k :: t1 -> t -> t1

Здесь у нас опять присутствуют не конкретные типы, а переменные типа: t1 и t. Типы t1 и t не важны. Но это могут быть два разных типа. Здесь у нас тип возвращаемого значения это тип первого аргумента функции. Имя переменной типа совершено не важно.

Prelude> :t const
const :: a -> b -> a
Prelude> :t const True
const True :: b -> Bool

В результате выражения const True получается функция одного аргумента. Тип этого аргумента совершено не известен. Потому что это тот аргумент, который игнорируется, а значение возвращаемое этой функцией наоборот известно. Функция const всегда возвращает ту константу, которая передана ей в качестве первого аргумента.


Константа undefined подходит для любого типа. В любом месте, где у нас присутствует выражение произвольного типа мы можем подставить константу undefined. При этом выражение будет правильно типизировано.

Prelude> undefined
*** Exception: Prelude.undefined
Prelude> :t undefined
undefined :: t

Про константу undefined говорят, что она в Haskell населяет любой допустимый тип. Естественно undefined не единственный способ создать объект, который населяет любой тип. Функция error с переданными туда строкой ведет себя точно также как undefined, ну и поэтому она тоже населяет любой тип. Она тоже является константой произвольного типа.

Prelude> error "Hello, World!"
*** Exception: Hello, World!
Prelude> :t error "Hello, World!"
error "Hello, World!" :: t
Prelude> :t error
error :: [Char] -> a

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


Функция getSecondFrom, полиморфна по каждому из трех аргументов, полностью игнорирует первый и третий аргумент, и возвращает второй:

getSecondFrom :: a -> b -> c -> b
getSecondFrom a b c = b

Две функции одинаковой арности считаются разными, если существует набор значений их аргументов, на котором они дают разные результирующие значения. Можно реализовать 3 разных всегда завершающихся функции с типом a -> a -> b -> a -> a.

foo :: a -> a -> b -> a -> a

1. foo p1 p2 p3 p4 = p1
2. foo p1 p2 p3 p4 = p2
3. foo p1 p2 p3 p4 = p3

Можно ограничить степень полиморфизма функции с помощью явного указания её типа.

module Demo where

{- Мономорфная функция: -}
mono :: Char -> Char
mono x = x

{- Частичное ограничение полиморфизма функции -}
{- Функция мономорфна 1 аргументу и полиморфна по 2 -}
semiMono :: Char -> a -> Char
semiMono x y = x

Если не указывать тип явно, то Haskell выводит так называемый наиболее общий тип.

Prelude> let semiMono x y = x
Prelude> :t semiMono
semiMono :: t1 -> t -> t1

Haskell вывел самый общий тип из структуры выражения присутствующего в правой части. Аппликативная структура (то, каким образом идентификаторы применяются друг к другу) всего выражения, которое стоит в правой части как раз диктует некоторый набор уравнений. О каждом применении какого-то идентификатора к другому идентификатору Haskell может сказать следующее, справа тип произвольный, а вот слева тип должен быть обязательно стрелочный потому что применять мы можем только функцию. Haskell в процессе вывода типов строит некоторую систему уравнений основанную на этом соображении, дальше разрешает его наиболее общим образом. Соответствующий алгоритм носит название алгоритм Хиндли-Дамас-Милнера. Система вывода типов Haskell базируется именно на этом алгоритме. Этот алгоритм выводит самый общий из допустимых типов. Если на тип не наложено никаких ограничений, то Haskell говорит, что мы используем переменную типа. Если же накладываются ограничения, тогда Haskell говорит, что этот тип мономорфизирован и мы используем например тип Char.

Специальный полиморфизм

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


Наличие интерфейсов в типе функций:

Prelude> :t 7
7 :: Num a => a

Если мы в типе обнаруживаем символ следования =>, то этот символ разделяет тип на две части. Правая часть это тип выражения, мы говорим, что 7 имеет тип a. А то что стоит слева это так называемый контекст. Контекст состоит из двух частей, имя интерфейса Num, который должен выставлять тип a использующийся в правой части, ну и дальше мы говорим, что этот интерфейс должен быть применен к соответствующему типу. 7 имеет полиморфный тип a, но для этого типа a должен быть выставлен интерфейс Num.


Оператор сложения определен следующим образом:

Prelude> :t (+)
(+) :: Num a => a -> a -> a

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


Оператор больше выглядит следующим образом:

Prelude> :t (>)
(>) :: Ord a => a -> a -> Bool

Он принимает два аргумента одинакового типа и возвращает булево значение. Однако на аргументы опять наложено некоторое ограничение. Контекст Ord a означает, что тип a, который используется в определении оператора больше должен быть представителем класса типов Ord.


Более сложно устроенный контекст:

Prelude> :t (> 7)
(> 7) :: (Num a, Ord a) => a -> Bool

На тип аргумента, который мы должны передавать в оператор сравнения наложены два ограничения: из-за оператора больше на тип наложено ограничение Ord, и второй элемент контекста это ограничение Num. Контексты Num a и Ord a это разные контексты. Например комплексные числа являются представителем класса типа Num, но не являются представителем класса типа Ord.


Пары сравниваются лексикографически. Первый и второй элемент пары могут относиться к разным числам, например Int и Double.

Prelude> :t (> (1,2))
(> (1,2)) :: (Num t, Num t1, Ord t, Ord t1) => (t, t1) -> Bool

Первый элемент пары это полиморфный тип t. Второй элемент пары это полиморфный тип t1. И на оба эти типа наложены соответствующие ограничения.

Классы типов

Класс типов задает интерфейс, который конкретные типы могут реализовывать. Сам по себе класс типов представляет собой именованный набор имен функций с сигнатурами параметризованный общим типовым параметром.

Пример класса типов Eq (взят из стандартной библиотеки):

module Demo where

-- Eq - это имя класса типов.
-- a - это типовой параметр, который параметризует этот класс типов.
class Eq a where
-- Дальше идут перечисления сигнатур функций. Они должны обязательно начинаться с ненулевого отступа.
-- Здесь не задаются реализации, а присутствует только интерфейс.
-- В случает специального полиморфизма должна быть своя реализация для каждого конкретного типа, который будет подставлен в месте a.
 (==) :: a -> a -> Bool -- функция сравнения на равенство элементов типа a
 (/=) :: a -> a -> Bool -- функция сравнения на неравенство

Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :t (== 42)
(== 42) :: (Eq a, Num a) => a -> Bool
Prelude> :t (== 'x')
(== 'x') :: Char -> Bool
Prelude> :t elem
elem :: (Eq a, Foldable t) => a -> t a -> Bool

t a в последнем определении означает применение тИповой переменной t (описывающей однопараметрический конструктор типа) к тИповой переменной a. На переменную t наложено ограничение, она должна принадлежать к классу типов Foldable. Конструктор списка удовлетворяет этому ограничению, поэтому допустимый, хотя и не наиболее общий тип таков elem :: Eq a => a -> [] a -> Bool, или в более традиционной миксфиксной нотации elem :: Eq a => a -> [a] -> Bool .

Конкретный тип называется представителем класса типов, если для него реализованы все функции, которые объявлены в классе типов. Иногда вместо слова представитель используют слово экземпляр (instance).

-- Объявление представителя класса типов.
instance Eq Bool where
 True  == True  = True
 False == False = True
 _     == _     = False
 
 x /= y = not (x == y)

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

class Eq a where
 (==), (/=) :: a -> a -> Bool
 x /= y = not (x == y) -- реализация по умолчанию

instance Eq Bool where
 True  == True  = True
 False == False = True
 _     == _     = False

Реализация по умолчанию можно перекрывать.

Можно давать циклические реализации по умолчанию.

class Eq a where
 (==), (/=) :: a -> a -> Bool
 x /= y = not (x == y) 
 x == y = not (x /= y) 

Это дает следующую возможность. Мы можем писать представителя класса типа Eq реализуя либо равенство, либо неравенство.


Представителем класса типов можно объявлять не только конкретный тип, но и некоторые полиморфные типы. Например, у нас есть полиморфный тип двухэлементного кортежа - пары. Две пары можно определять на предмет равенства, они равны, если равны их первые и вторые элементы. Реализация представителя класса типов Eq для пары:

-- Полиморфные ограничения появляются в виде контекста.
instance (Eq a, Eq b) => Eq (a, b) where
 p1 == p2 = fst p1 == fst p2 && snd p1 == snd p2

-- Списки могут сравниваться на равенство, если их элементы сравнимы на равенство.
-- instance Eq a => Eq [a] where
-- реализация
-- списки равны, когда равны их длины и они совпадают поэлементно

Класс типов Printable, предоставляет один метод toString — функцию одной переменной, которая преобразует значение типа, являющегося представителем Printable, в строковое представление.

class Printable p where
 toString :: p -> [Char]
 
instance Printable Bool where
 toString True = "true"
 toString False = "false"

instance Printable () where
 toString () = "unit type"

instance (Printable a, Printable b) => Printable (a, b) where
 toString x = "(" ++ toString (fst x) ++ "," ++ toString (snd x) ++ ")"

Типы данных Bool и () являются представителями этого класса типов, обеспечивая следующее поведение:

GHCi> toString True
"true"
GHCi> toString False
"false"
GHCi> toString ()
"unit type"
GHCi> toString (False,())
"(false,unit type)"
GHCi> toString (True,False)
"(true,false)"

Отличия интерфейсов в Haskell от от интерфейсов в объектно-ориентированных языках

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