Haskell: ejemplos no evidentes de dependencias funcionales

Question

Los ejemplos de dependencias funcionales que he visto se reducen a la asignación container -> element y arguments -> result (como en Mult Matrix Vector Vector). Parecen estar mejor expresados ​​con funciones de tipo. En la teoría de la base de datos, se consideran relaciones más complejas que no son de esta forma (como a -> b, b -> a).

¿Hay ejemplos de uso de FDs en Haskell que no se pueden escribir con las funciones de tipo?

Answer 1

Como Heinrich Apfelmus ya dijo que MPTC + FunDeps y TF solo son equivalentes. Las diferencias surgen cuando se combinan con otras extensiones, en particular con casos superpuestos. Los TF no son correctos cuando se permite la superposición, mientras que FunDeps permite la superposición. Por ejemplo, es fácil implementar la igualdad de tipos con 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 

El punto clave aquí es la superposición. En principio, es posible implementar la igualdad de tipo sin superposición, pero requerirá compatibilidad con el compilador. Ese enfoque es descrito por Oleg aquí: http://okmij.org/ftp/Haskell/typeEQ.html

P.S. Hubo lengthy discussion en la lista de correo de Haskell-Prime sobre este tema.

Answer 2

Como Manuel Chakravarty explains, las funciones de tipo y las dependencias funcionales tienen aproximadamente la misma expresividad, puede traducir una formulación a la otra. Solo comienzan a diferir cuando observa la interacción con otras extensiones de lenguaje como GADT o UndecidableInstances. Entiendo que las familias en este tipo son actualmente favorecidas para la implementación en GHC porque su interacción con GADTs y tipos existenciales es sustancialmente más simple.