Haskell: Igualdad limitación en la instancia

Question

que estaba leyendo a través del anuncio de ClassyPrelude y llegó a aquí:

instance (b ~ c, CanFilterFunc b a) => CanFilter (b -> c) a where 
    filter = filterFunc 

El escritor a continuación, mencionaron que esto no funcionaría:

instance (CanFilterFunc b a) => CanFilter (c -> c) a where 
    filter = filterFunc 

que tiene sentido para yo, como c, no está relacionado con la restricción de la izquierda.

Sin embargo, lo que no se menciona en el artículo y lo que no entiendo es por qué esto no funcionaría:

instance (CanFilterFunc b a) => CanFilter (b -> b) a where 
    filter = filterFunc 

Podría alguien explicar por qué esto es diferente a la primera definición mencionada? Tal vez un ejemplo trabajado de inferencia tipo GHC sería útil?

Answer 1

Michael ya da una buena explicación en su artículo de blog, pero trataré de ilustrarlo con un ejemplo (artificial, pero relativamente pequeño).

Necesitamos las siguientes extensiones:

{-# LANGUAGE FlexibleInstances, TypeFamilies #-} 

Vamos a definir una clase que es más sencillo que CanFilter, con un solo parámetro. Estoy definiendo dos copias de la clase, porque quiero demostrar la diferencia de comportamiento entre los dos casos:

class Twice1 f where 
    twice1 :: f -> f 

class Twice2 f where 
    twice2 :: f -> f 

Ahora, vamos a definir una instancia para cada clase. Para Twice1, arreglamos las variables de tipo para que sean las mismas directamente, y para Twice2, les permitimos que sean diferentes, pero agregan una restricción de igualdad.

instance Twice1 (a -> a) where 
    twice1 f = f . f 

instance (a ~ b) => Twice2 (a -> b) where 
    twice2 f = f . f 

Con el fin de mostrar la diferencia, vamos a definir otra función sobrecargada como esto:

class Example a where 
    transform :: Int -> a 

instance Example Int where 
    transform n = n + 1 

instance Example Char where 
    transform _ = 'x' 

Ahora estamos en un punto en el que podemos ver una diferencia. Una vez que definimos

apply1 x = twice1 transform x 
apply2 x = twice2 transform x 

y pedir GHC para los tipos inferidos, obtenemos que

apply1 :: (Example a, Twice1 (Int -> a)) => Int -> a 
apply2 :: Int -> Int 

¿Por qué? Bueno, la instancia para Twice1 solo se activa cuando el tipo de fuente y el objetivo de la función son los mismos. Para transform y el contexto dado, no lo sabemos. GHC solo aplicará una instancia una vez que el lado derecho coincida, por lo que nos queda el contexto no resuelto. Si intentamos decir apply1 0, habrá un error de tipo que indica que aún no hay suficiente información para resolver la sobrecarga. Tenemos que especificar explícitamente que el tipo de resultado sea Int en este caso para pasar. Sin embargo, en Twice2, la instancia es para cualquier tipo de función. GHC lo resolverá inmediatamente (GHC nunca retrocede, por lo que si una instancia coincide claramente, siempre se elige), y luego intenta establecer las condiciones previas: en este caso, la restricción de igualdad, que fuerza al tipo de resultado a ser Int y nos permite para resolver la restricción Example, también. Podemos decir apply2 0 sin anotaciones adicionales.

Este es un punto bastante sutil acerca de la resolución de instancia de GHC, y la restricción de igualdad aquí ayuda al verificador de tipos de GHC de una manera que requiere menos anotaciones de tipo por parte del usuario.