Выбрав F# для изучения в качестве первого функционального языка, на самом деле мне всё равно пришлось разбираться с Haskell и OCaml, так как для них существует море различных материалов и документации, давно выработаны различные практики программирования и существуют многочисленные (по сравнению с F#) дружелюбно настроенные коммьюнити. Да и после небольшого изучения ML-языков разобраться с синтаксисом Haskell вовсе не составляет труда, а потом начинают затягивать интересные языковые особенности…

По мере поверхностного знакомства с Haskell, я всё чаще стал встречать такое языковое средство, как классы типов (type classes), которые существуют в Haskell уже более десятка лет. Классы типов являются механизмом для поддержки специального (ad-hoc) полиморфизма, во многом напоминающим перегрузку функций в ООП-языках. Назначение классов типов - определение обобщённых операции над некоторым ограниченным множеством типов. Например, функции (+) и (==) в Haskell определены над некоторыми множествами типов, но не над всеми. Однако существует возможность расширить эти функции и на пользовательские типы.

Как выглядят классы типов в Haskell? Давайте рассмотрим следующий пример определения класса типа Eq, предназначенного для проверки эквивалентности двух значений:

class Eq a where
  (==) :: a -> a -> Bool
  (!=) :: a -> a -> Bool

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

В данной декларации мы определяем класс типов с именем Eq, для входящих в который типов a определены две операции (==) и (!=) с типом a -> a -> Bool. Дополнительно описаны реализации данных операций по-умолчанию, что позволяет расширять класс Eq для своих типов путём определения только одной из операций. Функции-члены класса типов на самом деле являются обычными функциями с интересной сигнатурой: (==) :: Eq a => a -> a -> Bool. Часть Eq a => в определении типа называют “контекстом”, который для .NET-программиста гораздо чаще встречался под термином generic type parameter constraint (ограничение на тип-параметр). То есть Eq a => - просто ограничение на тип-параметр a, требующее вхождение типа a в класс типов Eq.

А давайте перепишем эту декларацию в виде обычного определения абстрактного класса в F#?

// абстрактный класс, параметризованный типом 'a
[<AbstractClass>]
type Eq<'a>() =
  // никакого состояния, только абстрактные члены
  abstract equals    : 'a -> 'a -> bool
  abstract notEquals : 'a -> 'a -> bool
  // и реализации этих членов по-умолчанию
  default __.equals x y = not (__.notEquals x y)
  default __.notEquals x y = not (__.equals x y)

Выглядит похоже, не так ли? Теперь перейдём к определениям экземпляров классов типов (расширении класса на новый конкретный тип):

instance Eq Integer where
  (==) = eqInteger

То есть мы заменяем тип-параметр a на конкретный тип, которым мы хотим расширить класс Eq и реализуем любой из членов (или сразу оба). Функция eqInteger :: Integer -> Integer -> Bool специализирована на сравнении целых чисел. Перепишем на F#?

// экземпляр класса типа - наследник Eq<'a>
let intEq =
  { new Eq<int>() with // конкретный тип 'a
      override __.equals x y = (x = y) }

Компилятор Haskell гарантирует уникальность экземпляров - нельзя определить ещё один экземпляр Eq Integer с другой реализацией, а вот в F# нас никто не ограничивает в создании другого наследника Eq<’a>.

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

remove :: Eq a => a -> [a] -> [a]
remove x xs = filter (/= x) xs

Обратите внимание на сигнатуру функции - контекст Eq a выбрался “наружу” и теперь присутствует и в типе функции remove. Это ограничивает нас в использовании функции remove только над такими списками, элементами которых являются типы, входящие в класса типов Eq. Самое интересное - как такую функцию реализовать в F# без магии компилятора?

/// remove : Eq<'a> -> 'a -> 'a list -> 'a list
let remove (hidden: Eq<_>) x xs =
  List.filter (hidden.notEquals x) xs

Очень просто - в функцию необходимо добавить аргумент (который скрывается от пользователя компилятором Haskell) типа Eq<’a>, содержащий нужный экземпляр класса типа. Данная техника называется dictionary passing - компилятор Haskell скрыто передаёт “словарь” из функций-членов класса типов. Нам же в F# приходится самим находить нужный экземпляр Eq<’a>, определённый заранее (который и представляет собой этот “словарь”), и передавать его явным параметром:

> remove intEq 1 [1; 2; 1; 1; 3]
val it : int list = [2; 3]

Вот и всё - простейшие классы типов представляют собой лишь неявные параметры (implicit parameters), которые компилятор разрешает по месту вызова! В случае вызова функции с Eq a => другой функции с Eq a => “словарь” просто передаётся между функциями по цепочке. Вызов функции-члена класса типов не тяжелее обычного виртуального вызова метода класса. Все другие функции с контекстами в сигнатуре получают overhead в виде скрытых дополнительных параметров по числу контекстов.

Самая соль классов типов в том, что экземпляры вовсе отделены от типа, для которого они определяются - можно определить понятие эквивалентности (экземпляр Eq) для какого-нибудь чужого типа из сторонней библиотеки, не изменяя кода самой библиотеки (например, чтобы реализовать сторонним типом некоторые интерфейсы, отвечающие за проверку эквивалентности). Эта простая особенность открывает очень и очень интересные возможности Haskell, позволяет решить expression problem и эмулировать открытые типы данных и функций.

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

class (Eq a) => Ord a where
  compare              :: a -> a -> Ordering
  (<), (<=), (>), (>=) :: a -> a -> Bool
  max, min             :: a -> a -> a

Причём множественного наследования, так как ограничений может быть несколько. Но все эти возможности можно изобразить и в виде классов, либо через отношения наследования (в случае одиночного “наследования” классов типов), либо через агрегирование словарей в словарях (в случае множественного).

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

Классы типов очень хорошо зарекомендовали себя в Haskell, почему их нет в F#? Не смотря на отсутствие классов типов в F#, имеющиеся средства объектно-ориентированной стороны языка - классы, виртуальные функции и перегрузка - легко позволяют выражать функционал классов типов, например, как это было показано выше. Классы типов стали бы возможностью одного языка, 80% их функционала так или иначе давно покрыты в базовых классах .NET Framework.

Однако мы пока совсем упускаем из виду большую область применения классов типов, требующую от системы типов поддержку полиморфизма конструкторов типов (type constructor polymorphism), речь о котором пойдёт в следующем посте.