Haskell/GHC UndecidableInstances - esempio per controllo di tipo non terminante?

Question

Ho scritto un codice Haskell che richiede -XUndecidableInstances da compilare. Capisco perché succede, che c'è una certa condizione che è violata e quindi GHC urla.

Tuttavia, non mi sono mai imbattuto in una situazione in cui il controllo di tipo sarebbe effettivamente sospeso o finito in un ciclo infinito.

Che aspetto ha una definizione di istanza non terminante? Puoi fare un esempio?

Answer 1

Ad esempio:

{-# LANGUAGE UndecidableInstances #-} 

class C a where 
    f :: a -> a 

instance C [[a]] => C [a] where 
    f = id 

g x = x + f [x] 

Quello che sta accadendo: Quando si digita f [x] il compilatore deve garantire che x :: C [a] per alcuni a. La dichiarazione di istanza indica che x può essere di tipo C [a] solo se è anche di tipo C [[a]]. Quindi il compilatore deve garantire che sia x :: C [[a]], ecc. E venga catturato in un ciclo infinito.

Vedi anche Can using UndecidableInstances pragma locally have global consequences on compilation termination?

Answer 2

C'è un classico, un po 'esempio allarmante (che coinvolge l'interazione con dipendenze funzionali) in this paper from HQ:

class Mul a b c | a b -> c where 
    mul :: a -> b -> c 
instance Mul a b c => Mul a [b] [c] where 
    mul a = map (mul a) 

f b x y = if b then mul x [y] else y 

Abbiamo bisogno mul x [y] avere lo stesso tipo di y, così, prendendo x :: x e y :: y, abbiamo bisogno

instance Mul x [y] y 

WHI ch, secondo l'istanza data, possiamo avere. Naturalmente, dobbiamo prendere y ~ [z] per qualche z tale che

instance Mul x y z 

cioè

instance Mul x [z] z 

e siamo in un ciclo.

E 'inquietante, perché quella Mul esempio assomiglia ricorsione è strutturalmente riducendo, a differenza del caso chiaramente patologica in risposta di Petr. Eppure fa loop GHC (con la soglia di noia che si attiva per evitare di appendere).

Il guaio, come sono sicuro che ho detto da qualche parte in qualche tempo, è che l'identificazione y ~ [z] è fatto, nonostante il fatto che z dipende funzionalmente su y. Se usassimo una notazione funzionale per la dipendenza funzionale, potremmo vedere che il vincolo dice y ~ Mul x [y] e respingere la sostituzione come in violazione del controllo di occorrenza.

Incuriosito, ho pensato di dare a questo un vortice,

class Mul' a b where 
    type MulT a b 
    mul' :: a -> b -> MulT a b 

instance Mul' a b => Mul' a [b] where 
    type MulT a [b] = [MulT a b] 
    mul' a = map (mul' a) 

g b x y = if b then mul' x [y] else y 

Con UndecidableInstances abilitato, ci vuole un bel po 'per il ciclo di time out. Con UndecidableInstances disabilitato, l'istanza è ancora accettata e il tipografo continua a scorrere, ma il taglio avviene molto più rapidamente.

Quindi ... divertente vecchio mondo.