conflicto de dependencia funcional de Haskell

Question

¿Por qué esto provoca un conflicto?

class Foo a b | b -> a where 
    foo :: a -> b -> Bool 

instance Eq a => Foo a a where 
    foo = (==) 

instance Eq a => Foo a (a -> a) where 
    foo x f = f x == x 

Tenga en cuenta que el código se compilará si elimino la dependencia funcional.

Tenía la impresión de que las dependencias funcionales solo deberían rechazar cosas como las siguientes, cuando de hecho, compila!

class Foo a b | b -> a where 
    foo :: a -> b -> Bool 

instance Eq a => Foo a a where 
    foo = (==) 

instance Eq a => Foo Bool a where 
    foo _ x = x == x 

mismo b parámetro, sin embargo, diferentes parámetros a. ¿No debería b -> a rechazar esto, ya que esto significa que a está determinado únicamente por b?

Answer 1

¿Has probado realmente usando la segunda versión? Supongo que, mientras se compilan las instancias, comenzará a recibir errores de ambigüedad y superposición cuando llame al foo.

El mayor obstáculo es que FUNDEPS no interactúan con las variables de tipo de la forma en que podría esperar que ellos - selección de instancias en realidad no se buscan soluciones, que coincide a ciegas intentando unificación. Específicamente, cuando escribe Foo a a, el a es completamente arbitrario y, por lo tanto, puede unificarse con un tipo como b -> b. Cuando el segundo parámetro tiene el formato b -> b, por lo tanto, coincide con ambas instancias, pero las fundeps dicen que en un caso el primer parámetro debe ser b -> b, pero en el otro que debe ser b. De ahí el conflicto.

---

Dado que este aparentemente sorprende a la gente, esto es lo que ocurre si se intenta utilizar la segunda versión:

• bar = foo()() resultados en:

  Couldn't match type `Bool' with `()' 
      When using functional dependencies to combine 
      Foo Bool a, 
  

  ... porque el Fundep dice , a través de la segunda instancia, que cualquier tipo como el segundo parámetro determina de manera única Bool como el primero. Por lo tanto, el primer parámetro debe ser Bool.

• bar = foo True() resultados en:

  Couldn't match type `()' with `Bool' 
      When using functional dependencies to combine 
      Foo a a, 
  

  ... porque el Fundep dice, a través de la primera ejemplo, que cualquier tipo que el segundo parámetro determina de forma única la mismo tipo para el primero. Por lo tanto, el primer parámetro debe ser ().

• bar = foo() True resultado en errores debidos a ambos casos, ya que esta vez están de acuerdo en que el primer parámetro debe ser Bool.

• bar = foo True True resultados en:

  Overlapping instances for Foo Bool Bool 
      arising from a use of `foo' 
  

  ... debido a que ambos casos están satisfechos, y por lo tanto se superponen.

Pretty fun, huh?

Answer 2

La primera instancia dice para cualquier a entonces el Fundep le devuelve una a. Esto significa que excluirá prácticamente cualquier otra cosa, ya que cualquier otra cosa debe unificarse con esa variable libre y, por lo tanto, forzar la elección de esa instancia.

Edit: Inicialmente, había sugerido que funcionara el segundo ejemplo. Lo hizo en ghc 7.0.4, pero no tenía sentido que lo hiciera, y este problema parece haberse resuelto en versiones más nuevas.