Haskell: неочевидные примеры функциональных зависимостей

Question

Примеры функциональных зависимостей, которые я видел, сводятся к отображению container -> element и arguments -> result (как в Mult Matrix Vector Vector). Кажется, что они лучше выражены функциями типа. В теории базы данных рассматриваются более сложные отношения, которые не относятся к этой форме (например, a -> b, b -> a).

Есть примеры использования FD в Haskell, которые не могут быть красиво написаны с использованием функций типа?

Answer 1

Как уже сказал Генрих Апфельмус, MPTC + FunDeps и TF являются эквивалентными. Различия возникают, когда они сочетаются с другими расширениями, в частности с перекрывающимися экземплярами. TF недопустимы при разрешении перекрытия, в то время как FunDeps позволяют перекрывать друг друга. Например, с помощью FunDeps легко реализовать равенство типа:

data HTrue 
data HFalse 

class TypeEq a b eq | a b -> eq 
instance    TypeEq a a HTrue 
instance eq ~ HFalse => TypeEq a b eq 

Ключевые моменты здесь перекрываются. В принципе можно реализовать равенство типов без перекрытия, но для этого потребуется поддержка компилятора. Этот подход описан Олегом здесь: http://okmij.org/ftp/Haskell/typeEQ.html

P.S. На этой странице был отправлен lengthy discussion в списке рассылки haskell-prime.

Answer 2

Как Мануэль Чакраварти explains, функции типа и функциональные зависимости имеют примерно такую ​​же выразительность, вы можете перевести одну формулировку в другую. Они только начинают различаться, когда вы смотрите на взаимодействие с другими языковыми расширениями, такими как GADT или UndecidableInstances. Полагаю, что эти типы семейств в настоящее время предпочитают реализацию в GHC, потому что их взаимодействие с GADT и экзистенциальными типами существенно проще.