Haskell conflitto di dipendenza funzionale

Question

Perché questo si traduce in un conflitto?

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 

Si noti che il codice verrà compilato se mi tolgo la dependecy funzionale.

Avevo l'impressione che le dipendenze funzionali non consentissero altro che cose come quelle che seguono, quando in realtà 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 

Stesso b parametro, eppure diversi a parametri. Non dovrebbe b -> a non consentire questo, in quanto ciò significa che a è determinato in modo univoco da b?

Answer 1

Avete provato in realtà utilizzando la seconda versione? Suppongo che mentre le istanze vengono compilate, inizierai a ottenere errori di ambiguità e di sovrapposizione quando chiami foo.

Il più grande ostacolo qui è che fundeps non interagisce con le variabili di tipo nel modo in cui ci si potrebbe aspettare che esse - la selezione di istanze non cerca realmente soluzioni, ma combacia ciecamente tentando l'unificazione. Nello specifico, quando scrivi Foo a a, lo a è completamente arbitrario e può quindi unificarsi con un tipo come b -> b. Quando il secondo parametro ha il formato b -> b, pertanto corrisponde a entrambe le istanze, ma i fondi indicano che in un caso il primo parametro deve essere b -> b, ma nell'altro deve essere b. Da qui il conflitto.

---

Dal momento che questo sorprende quanto pare la gente, ecco cosa succede se si tenta di utilizzare la seconda versione:

• bar = foo()() risultati in:

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

  ... perché il fundep dice , tramite la seconda istanza, che qualsiasi tipo come secondo parametro determina in modo univoco Bool come primo. Quindi il primo parametro deve essere Bool.

• bar = foo True() risultati in:

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

  ... perché il fundep dice, attraverso la prima istanza di, che qualsiasi tipo del secondo parametro determina univocamente lo stesso tipoper la prima. Quindi il primo parametro deve essere ().

• bar = foo() True risultati in errori dovuti alla entrambi casi, dal momento che questa volta sono d'accordo che il primo parametro dovrebbe essere Bool.

• bar = foo True True risultati in:

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

  ... perché entrambi i casi sono soddisfatti, e quindi si sovrappongono.

Abbastanza divertente, eh?

Answer 2

La prima istanza dice per qualsiasia poi il fundep ti restituisce un a. Ciò significa che escluderà praticamente qualsiasi altra cosa, poiché qualsiasi altra cosa dovrebbe unificarsi con quella variabile libera e quindi forzare la scelta di quell'istanza.

Modifica: Inizialmente avevo suggerito il secondo esempio funzionato. Lo ha fatto su ghc 7.0.4, ma non aveva senso che lo facesse, e questo problema sembra essere stato risolto nelle versioni più recenti.