-
FunctionalDependencies -
- Подразумевает:
- С момента:
-
6.8.1
Разрешает использование функциональных зависимостей в объявлениях классов.
Функциональные зависимости реализованы так, как описал Марк Джонс в [Jones2000].
Функциональные зависимости вводятся вертикальной чертой в синтаксисе объявления класса; например:
class (Monad m) => MonadState s m | m -> s where ... class Foo a b c | a b -> c where ...
Дополнительную документацию можно найти на вики Haskell.
“Type Classes with Functional Dependencies”, Марк П. Джонс, В Трудах 9-й Европейской конференции по программированию, ESOP 2000, Берлин, Германия, март 2000 г., Springer-Verlag LNCS 1782, .
6.8.7.1. Правила для функциональных зависимостей
В объявлении класса все типы переменных класса должны быть достижимы (в смысле, упомянутом в Снятие ограничений на контексты классов) из свободных переменных каждого типа метода. Например:
class Coll s a where empty :: s insert :: s -> a -> s
неверно, потому что тип empty не упоминает a. Функциональные зависимости могут сделать переменную типа достижимой:
class Coll s a | s -> a where empty :: s insert :: s -> a -> s
Альтернативно, Coll можно переписать как
class Coll s a where empty :: s a insert :: s a -> a -> s a
что устанавливает связь между типом коллекции a (а именно (s a)) и типом элемента a. Иногда это не срабатывает, в этом случае можно разделить класс следующим образом:
class CollE s where empty :: s class CollE s => Coll s a where insert :: s -> a -> s
6.8.7.2. Общие сведения о функциональных зависимостях
Следующее описание мотивации и использования функциональных зависимостей взято из руководства пользователя Hugs, воспроизведено здесь (с небольшими изменениями) с любезного разрешения Марка Джонса.
Рассмотрим следующий класс, предназначенный как часть библиотеки типов коллекций:
class Collects e ce where
empty :: ce
insert :: e -> ce -> ce
member :: e -> ce -> Bool
Переменная типа e здесь представляет тип элемента, а ce — тип контейнера. В рамках этой структуры мы можем определить экземпляры этого класса для списков или характеристических функций (обе из которых могут использоваться для представления коллекций любого типа равенства), битовых наборов (которые могут использоваться для представления коллекций символов) или хеш-таблиц (которые могут использоваться для представления любой коллекции, элементы которой имеют функцию хеширования). Опуская стандартные детали реализации, это приведет к следующим объявлениям:
instance Eq e => Collects e [e] where ...
instance Eq e => Collects e (e -> Bool) where ...
instance Collects Char BitSet where ...
instance (Hashable e, Collects a ce)
=> Collects e (Array Int ce) where ...
Все это выглядит многообещающе; у нас есть класс и ряд интересных реализаций. К сожалению, есть некоторые серьезные проблемы с объявлением класса. Во-первых, пустая функция имеет неоднозначный тип:
empty :: Collects e ce => ce
Под «неоднозначным» мы подразумеваем, что имеется переменная типа e, которая появляется слева от символа =>, но не справа. Проблема в том, что, согласно теоретическим основам перегрузки Haskell, мы не можем гарантировать хорошо определенную семантику для любого члена с неоднозначным типом.
Мы можем обойти эту конкретную проблему, удалив пустой член из объявления класса. Однако, хотя оставшиеся члены, insert и member, не имеют неоднозначных типов, мы все равно сталкиваемся с проблемами при попытке использовать их. Например, рассмотрим следующие две функции:
f x y = insert x . insert y g = f True 'a'
для которых GHC выводит следующие типы:
f :: (Collects a c, Collects b c) => a -> b -> c -> c g :: (Collects Bool c, Collects Char c) => c -> c
Обратите внимание, что тип для f позволяет двум параметрам x и y иметь разные типы, даже если он пытается вставить каждое из двух значений, одно за другим, в одну и ту же коллекцию. Если мы пытаемся смоделировать коллекции, содержащие только один тип значения, то это явно неточный тип. Что еще хуже, определение для g принимается без вывода ошибки типа. В результате ошибка в этом коде не будет отмечена в месте ее появления. Вместо этого она появится только при попытке использования g, которая может даже находиться в другом модуле.
6.8.7.2.1. Попытка использования классов конструкторов
Столкнувшись с описанными выше проблемами, некоторые программисты Haskell могут быть искушены использовать что-то вроде следующей версии объявления класса:
class Collects e c where empty :: c e insert :: e -> c e -> c e member :: e -> c e -> Bool
Ключевое отличие здесь заключается в том, что мы абстрагируемся от конструктора типа c, который используется для формирования типа коллекции c e, а не от самого типа этой коллекции, представленного ce в исходном объявлении класса. Это позволяет избежать немедленных проблем, о которых мы упомянули выше: у empty тип Collects e c => c e, который не неоднозначен.
Функция f из предыдущего раздела имеет более точный тип:
f :: (Collects e c) => e -> e -> c e -> c e
Функция g из предыдущего раздела теперь отклоняется с ошибкой типа, как и ожидалось, поскольку тип f не позволяет двум аргументам иметь разные типы. Это пример класса с несколькими параметрами, который на практике действительно работает довольно хорошо, без проблем с неоднозначностью. Однако есть подвох. Эта версия класса Collects ни в коем случае не так обща, как первоначальный класс, по-видимому: только один из четырех экземпляров для Collects выше может быть использован с этой версией Collects, поскольку только один из них — экземпляр для списков — имеет тип коллекции, который можно записать в форме c
e, для некоторого конструктора типов c, и тип элемента e.
