¿La subclase de Haskell requiere instancias indecidibles?

Question

Considere el ejemplo de código siguiente:

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE UndecidableInstances #-} -- Is there a way to avoid this? 

-- A generic class with a generic function. 
class Foo a where 
    foo :: a -> a 

-- A specific class with specific functions. 
class Bar a where 
    bar :: a -> a 
    baz :: a -> a 

-- Given the specific class functions, we can implement the generic class function. 
instance Bar a => Foo a where 
    foo = bar . baz 

-- So if a type belongs to the specific class... 
instance Bar String where 
    bar = id 
    baz = id 

-- We can invoke the generic function on it. 
main :: IO() 
main = 
    putStrLn (foo "bar") 

(Mi código real es mucho más elaborado, lo que es un caso mínimo-abajo hervida para demostrar el patrón.)

No es claro por qué UndecidableInstances son necesarios aquí - el parámetro de tipo a aparece una vez en ambos lados de Bar a => Foo a, así que esperaba que las cosas "simplemente funcionaran". Obviamente me falta algo aquí. Pero, en cualquier caso, ¿hay alguna forma de hacerlo sin usar UndecidableInstances?

Answer 1

Hay algunos enfoques que puede tomar; No creo que haya proporcionado suficiente contexto para determinar cuál sería el más apropiado. Si está utilizando GHC-7.4, es posible que desee probar la extensión DefaultSignatures.

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE DefaultSignatures #-} 

-- A generic class with a generic function. 
class Foo a where 
    foo :: a -> a 
    default foo :: Bar a => a -> a 
    foo = bar . baz 

-- A specific class with specific functions. 
class Bar a where 
    bar :: a -> a 
    baz :: a -> a 

instance Bar String where 
    bar = id 
    baz = id 

instance Foo String 

main :: IO() 
main = 
    putStrLn (foo "bar") 

usted todavía tiene que declarar que un tipo es una instancia de Foo, pero no es necesario repetir la declaración de método porque se utiliza la implementación predeterminada.

Otro enfoque bastante ligero es utilizar un nuevo tipo. Si tiene funciones que necesitan una instancia Foo, puede ajustar una instancia Bar en el nuevo tipo.

newtype FooBar a = FooBar { unFooBar :: a } 

instance Bar a => Foo (FooBar a) where 
    foo = FooBar . bar . baz . unFooBar 

-- imported from a library or something... 
needsFoo :: Foo a => a -> b 

myFunc = needsFoo (FooBar someBar) 

Alternativamente, es posible que pueda pasar con la sustitución de foo con una función normal, o hacer una versión especializada para Bar casos:

-- if every `Foo` is also a `Bar`, you can just do this. No need for `Foo` at all! 
foo :: Bar a => a -> a 
foo = bar . baz 

-- if most `Foo`s aren't `Bar`s, you may be able to use this function when you have a `Bar` 
fooBar :: Bar a => a -> a 
foo = bar . baz 

Estas son probablemente las mejores soluciones si trabajan para tu situación.

Otra opción es declarar cada instancia de Foo manualmente. Aunque puede haber muchas instancias diferentes concebibles, es bastante común que las bases de código solo tengan un puñado de instancias que realmente se usan. Si eso es cierto aquí, probablemente sea menos trabajo simplemente escribir las 3 o 4 instancias que necesita en lugar de intentar implementar una solución más general.

Como último recurso, puede utilizar algo así como su código original, pero también tendrá que OverlappingInstances para que funcione (si es que no es necesario OverlappingInstances, entonces usted no necesita una clase Foo). Esta es la extensión que permite a GHC elegir la "instancia más específica" cuando hay múltiples coincidencias disponibles. Esto funcionará más o menos, aunque es posible que no obtenga lo que espera.

class Foo a where 
    foo :: a -> a 

class Bar a where 
    bar :: a -> a 
    baz :: a -> a 

instance Bar String where 
    bar = id 
    baz = id 

instance Bar a => Foo a where 
    foo = bar . baz 

instance Foo [a] where 
    foo _ = [] 

main :: IO() 
main = 
    print (foo "foo") 

Ahora main imprime una secuencia vacía. Hay dos instancias Foo, para a y [a]. Este último es más específico, por lo que se elige para foo "foo" ya que una cadena tiene el tipo [Char], aunque es probable que desee la primera. Por lo que ahora también había necesidad de escribir

instance Foo String where 
    foo = bar . baz 

momento en el que usted puede también dejar de lado la instancia Bar a => Foo a por completo.

Answer 2

Además de la respuesta anterior. La política utilizada en el módulo Data.Traversable de la biblioteca base es atractiva.En resumen, dar una instancia genérica en la biblioteca obliga al usuario final a aceptar su decisión, y esto no siempre es lo mejor que puede hacer. Data.Traversable contiene funciones como foldMapDefault, que ofrece la implementación predeterminada, pero la decisión de la implementación específica depende del usuario.