Ao escrever algum código usandoUndecidableInstances anteriormente, encontrei algo que achei muito estranho. Consegui criar acidentalmente algum código que verifica tipicamente quando achava que não deveria:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}

data Foo = Foo

class ConvertFoo a b where
  convertFoo :: a -> b

instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
  convertFoo = convertFoo . (convertFoo :: a -> Foo)

evil :: Int -> String
evil = convertFoo

Especificamente, oconvertFoo A função verifica tipicamente quando fornecidaqualquer entrada para produzirqualquer saída, como demonstrado peloevil função. No começo, pensei que talvez eu conseguisse implementar acidentalmenteunsafeCoerce, mas isso não é bem verdade: na verdade, tentar chamar meuconvertFoo função (fazendo algo comoevil 3, por exemplo) simplesmente entra em um loop infinito.

I tipo de entender o que está acontecendo em um sentido vago. Minha compreensão do problema é algo como isto:

A instância deConvertFoo que eu defini trabalhos emqualquer entrada e saída,a eb, limitado apenas pelas duas restrições adicionais de que as funções de conversão devem existira -> Foo eFoo -> b.De alguma forma, essa definição é capaz de corresponder a qualquer tipo de entrada e saída; portanto, parece que a chamada paraconvertFoo :: a -> Foo está escolhendo a própria definição deconvertFoo por si só, já que é o único disponível.Desde aconvertFoo se chama infinitamente, a função entra em um loop infinito que nunca termina.Desde aconvertFoo nunca termina, o tipo dessa definição é inferior, entãotecnicamente nenhum dos tipos é violado e o programa verifica de novo.

Agora, mesmo que o entendimento acima esteja correto, ainda estou confuso sobre o motivo de todo o programa checar. Especificamente, eu esperaria que oConvertFoo a Foo eConvertFoo Foo b restrições a falhar, dado que não existem tais instâncias.

I Faz entendo (pelo menos imprecisamente) que restrições não importam ao escolher uma instância - a instância é escolhida com base apenas no cabeçalho da instância e depois as restrições são verificadas - para que eu pudesse ver que essas restrições podem resolver muito bem por causa da minhaConvertFoo a b exemplo, o mais permissivo possível. No entanto, isso exigiria que o mesmo conjunto de restrições fosse resolvido, o que eu acho que colocaria o typechecker em um loop infinito, fazendo com que o GHC travasse na compilação ou me desse um erro de estouro de pilha (o último dos quais eu vi antes).

Claramente, porém, o typechecker faznão loop, porque felizmente atinge o fundo e compila meu código com alegria. Por quê? Como o contexto da instância é satisfeito neste exemplo em particular? Por que isso não me dá um erro de tipo ou produz um loop de digitação?