-
FunctionalDependencies -
- Подразумевает:
- Начиная с версии:
-
6.8.1
Разрешает использовать функциональные зависимости в объявлениях классов.
Функциональные зависимости реализованы в соответствии с описанием Марка Джонса в [Jones2000].
Функциональные зависимости вводятся вертикальной чертой в синтаксисе объявления класса; например:
class (Monad m) => MonadState s m | m -> s where ... class Foo a b c | a b -> c where ...
Дополнительную документацию можно найти в вики Haskell.
«Классы типов с функциональными зависимостями», Марк П. Джонс, в Трудах 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 имеет неоднозначный тип:
empty :: Collects e ce => ce
Под «неоднозначным» мы понимаем, что существует переменная типа e, которая встречается слева от символа =>, но не справа. Проблема в том, что, согласно теоретическим основам перегрузки в Haskell, мы не можем гарантировать корректную семантику для какого-либо терма с неоднозначным типом.
Эту конкретную проблему можно обойти, удалив элемент empty из объявления класса. Однако, хотя у оставшихся элементов 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.
6.8.7.2.2. Добавление функциональных зависимостей
Чтобы получить более полезную версию класса Collects, GHC предоставляет механизм, позволяющий программистам указывать зависимости между параметрами класса с несколькими параметрами (Читателям, интересующимся теоретическими основами и предыдущими исследованиями: использование информации о зависимостях можно рассматривать как обобщение предложения о «параметрических классах типов», выдвинутого Ченом, Худаком и Одерским, или как частный случай более поздней схемы Марка Джонса для «улучшения» типов с контекстами. Основные идеи также обсуждаются в более теоретическом и абстрактном ключе в рукописи [Jones1999], где они представлены как одна из точек в общем пространстве проектирования систем неявной параметризации). Для начала рассмотрим абстрактный пример — объявление вида:
class C a b where ...
«Исследование пространства проектирования неявной параметризации на основе типов», Марк П. Джонс, Орегонский институт науки и технологий, технический отчёт, июль 1999 г.
которое просто сообщает, что C можно рассматривать как бинарное отношение на типах (или конструкторах типов — в зависимости от видов a и b). В определения классов можно включать дополнительные условия, задающие информацию о зависимостях между параметрами, как в следующих примерах:
class D a b | a -> b where ... class E a b | a -> b, b -> a where ...
Используемая здесь между символами | и where запись a -> b — не путайте её с типом функции — указывает, что параметр a однозначно определяет параметр b; её можно прочитать как «a определяет b». Таким образом, D — это не просто отношение, а частичная функция. Аналогично, из двух зависимостей, включённых в определение E, видно, что E представляет собой частичное взаимно однозначное отображение между типами.
В общем случае зависимости имеют форму x1 ... xn -> y1 ... ym, где x1, …, xn и y1, …, yn — переменные типов, причём n>0 и m>=0. Это означает, что параметры y однозначно определяются параметрами x. Если с одной из сторон зависимости указано несколько переменных, в качестве разделителей можно использовать пробелы, как в t -> a b. Обратите внимание, что класс может быть аннотирован несколькими зависимостями, разделёнными запятыми, как в приведённом выше определении E. Некоторые зависимости, записываемые в таком формате, избыточны и будут отклонены, поскольку не несут полезной информации и могут указывать на ошибку в программе. К таким зависимостям относятся a -> a, a -> a a, a -> и т. д. Избыточность может возникнуть и при задании нескольких зависимостей, как в a->b, b->c, a->c, если некоторое подмножество подразумевает остальные зависимости. Такие примеры не считаются ошибками. Обратите внимание, что зависимости указываются только в объявлениях классов и не встречаются в других частях языка. В частности, синтаксис объявлений экземпляров, ограничений классов и типов остаётся без изменений.
Добавляя зависимости в объявление класса, программист может точнее задать каждый класс с несколькими параметрами. Компилятор, в свою очередь, отвечает за проверку того, что набор экземпляров, доступных в каждой точке программы, согласуется с объявленными зависимостями. Например, следующие два объявления экземпляров не могут находиться в одной области видимости, поскольку они нарушают зависимость для D, хотя каждое из них по отдельности было бы допустимым:
instance D Bool Int where ... instance D Bool Char where ...
Обратите также внимание, что следующее объявление недопустимо даже само по себе:
instance D [a] b where ...
Проблема здесь в том, что этот экземпляр позволил бы связать один конкретный вариант [a] более чем с одним вариантом b, что противоречит зависимости, заданной в определении D. В более общем случае это означает, что в любом экземпляре вида:
instance D t s where ...
для некоторых конкретных типов t и s в s могут появляться только переменные, входящие в t. Следовательно, если тип t известен, то s будет однозначно определён.
Преимущество включения информации о зависимостях состоит в том, что она позволяет определять более универсальные классы с несколькими параметрами без проблем с неоднозначностью и получать более точные типы. Чтобы показать это, вернёмся к примеру с классом коллекций и добавим простую зависимость к исходному определению Collects:
class Collects e ce | ce -> e where empty :: ce insert :: e -> ce -> ce member :: e -> ce -> Bool
Зависимость ce -> e указывает, что тип e элементов однозначно определяется типом коллекции ce. Обратите внимание, что оба параметра Collects имеют вид Type; классов конструкторов здесь нет. Также обратите внимание, что все экземпляры Collects, приведённые ранее, можно использовать вместе с этим новым определением.
А что насчёт проблем с неоднозначностью, возникших при исходном определении? Функция empty по-прежнему имеет тип Collects e ce => ce, но теперь его не нужно считать неоднозначным. Хотя переменная e не встречается справа от символа =>, зависимость для класса Collects говорит, что она однозначно определяется переменной ce, которая встречается справа от символа =>. Следовательно, контекст использования empty по-прежнему может предоставлять достаточно информации для определения типов и ce, и e без неоднозначности. В более общем случае тип следует считать неоднозначным, только если он содержит слева от => переменную, которая не определяется однозначно (прямо или косвенно) переменными справа.
Зависимости также помогают получать более точные типы для определённых пользователем функций, благодаря чему ошибки обнаруживаются раньше, а типы, с которыми работают программисты, становятся менее громоздкими. Вспомним предыдущее определение функции f:
f x y = insert x y = insert x . insert y
для которой изначально был получен следующий тип:
f :: (Collects a c, Collects b c) => a -> b -> c -> c
Однако, используя информацию о зависимостях для Collects, мы можем вывести, что a и b должны быть равны, поскольку они оба выступают вторым параметром в ограничении Collects с одним и тем же первым параметром c. Поэтому для f можно вывести более короткий и точный тип:
f :: (Collects a c) => a -> a -> c -> c
Аналогично, предыдущее определение g теперь будет отмечено как ошибка типа.
Хотя здесь приведено всего несколько примеров, должно быть очевидно, что добавление информации о зависимостях помогает сделать классы с несколькими параметрами более полезными на практике: оно устраняет проблемы с неоднозначностью и позволяет задавать более универсальные наборы объявлений экземпляров.
