2012-03-03 18 views
6

Estoy tratando de definir un par de instancias de clase inductivamente. Esto es:Haskell "no" tipo restricción

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

instance (not?)Foo a => Bar a b 
    foo x = ... 

instance Foo a => Bar a b 
    foo x = ... 

Los primeros casos determina la acción base, y los segundos llama de forma recursiva foo. ¿Hay alguna manera de hacer esto? Un buen ejemplo sería aplanar una lista, donde en el primer caso es la función de identidad y en el segundo es una aplicación recursiva de concat.

+10

Tenga en cuenta que en Haskell, es imposible estar seguro de que un tipo determinado sea * no * una instancia de una clase de tipo determinada, porque alguien más podría compilar su código con parte de su propio código que proporciona la instancia. –

Respuesta

5

Aquí hay un implementation of a flatten function que funciona con cualquier nivel de lista anidada. Aunque no recomendaría usarlo, aquí solo para demostrar cómo lograr algo así en Haskell.

+5

Usar IncoherentInstances es una invitación al problema. – augustss

+1

@augustss, muy cierto, de ahí el disclamer que puse en la parte superior. Sin embargo, no creo que sea posible implementar 'flatten' sin' IncoherentInstances' (que probablemente sea una muy buena indicación de que diseñar una programa que dependa de esta función es una mala idea). –

+1

@ is7s: la solución no puede derivar el tipo de la lista aplanada (por lo que debe especificarla como 'aplanar [[3], [4]] :: [Int]'. Para ese trabajo, necesita las tres extensiones que diste. Sin embargo, es una solución que vale la pena. –

8

No hay forma de hacerlo directamente, por una razón muy simple: la selección de instancias solo mira la "cabeza", es decir, la parte después del =>. Nada de lo que coloque en el contexto, la parte anterior al =>, puede influir en qué instancia se selecciona.

Para casos simples, a menudo puede evitar el problema por completo, como por ejemplo si hay un número limitado de tipos de "caso base". Un ejemplo común sería listas de nivel de tipo, donde tendría un caso recursivo para Cons y un caso base de Nil y eso es todo.

En el caso general, normalmente necesitará algún tipo de clase de "prueba condicional" que seleccione un tipo según si se cumple alguna condición, luego transfiera la implementación real a una clase "auxiliar" que toma el el valor del resultado condicional como parámetro y lo usa para seleccionar una instancia.

+1

¿Cómo implementaría una lista genérica aplanando un miembro de la clase? – Jonathan

+7

Bueno, la respuesta más honesta es que no lo haría. No hay forma de hacerlo sin romper las entradas polimórficas y, en mi opinión, no es lo suficientemente útil como para justificar la molestia. Dicho esto, para aplanar las listas, creo que podría confiar en que las instancias solapadas puedan elegir entre el caso recursivo o el caso base. ¿Estás usando 'OverlappingInstances' aquí? Probablemente lo necesite de una manera u otra. –

+3

¿Por qué querrías una función de aplanamiento de lista genérica? Raramente es útil. – augustss

Cuestiones relacionadas