Resolución de instancia Ambigous en Haskell

types type-inference

Question

Introducción y caso de uso de ejemplo

¡Hola! Tengo un problema en Haskell. Consideremos el siguiente código

class PolyMonad m1 m2 m3 | m1 m2 -> m3 where
polyBind :: m1 a -> (a -> m2 b) -> m3 b

que solo declara una unión de poly mónada. Un buen ejemplo de caso de uso sería:

newtype Pure a = Pure { fromPure :: a } deriving (Show)
instance PolyMonad Pure Pure Pure where
polyBind a f = f (fromPure a)
instance PolyMonad Pure IO IO where
polyBind a f = f (fromPure a)
instance PolyMonad IO Pure IO where
polyBind a f = (fromPure . f) <$> a
instance PolyMonad IO IO IO where
polyBind a f = a >>= f

y usándolo con -XRebindableSyntax como tal:

test = do
Pure 5
print "hello"
Pure ()

pero podemos hacer mucho más con esto: esta fue solo una prueba para mostrarle un ejemplo de caso.

El problema

Consideremos un uso un poco más complejo. Quiero escribir una clase similar a Polymonad, que no siempre dará salida a m3 b , pero en algunos casos específicos producirá m3 (X b) para una X específica. Para simplificar, supongamos que queremos dar salida a m3 (X b) SÓLO cuando m1 o m2 eran IO .

Parece que no podemos hacerlo ahora en Haskell sin perder flexibilidad. Necesito las siguientes funciones para compilar sin agregar ningún tipo de información (el código Haskell es uno generado):

tst1 x = x `polyBind` (/_ -> Pure 0)
tst2 = (Pure 1) `polyBind` (/_ -> Pure 0)
tst3 x y = x `polyBind` (/_ -> y `polyBind` (/_ -> Pure 0))

De todos modos, estas funciones se compilan bien utilizando la clase PolyMonad .

Fundep intenta resolver el problema

Uno de los intentos podría ser:

class PolyMonad2 m1 m2 m3 b | m1 m2 b -> out where
polyBind2 :: m1 a -> (a -> m2 b) -> out

y, por supuesto, podemos escribir fácilmente todas las instancias necesarias, como:

instance PolyMonad2 Pure Pure b (Pure b) where
polyBind2 a f = f (fromPure a)
instance PolyMonad2 Pure IO b (IO (X b)) where
polyBind2 a f = fmap X $ f (fromPure a)
-- ...

pero nuestras funciones de prueba no compilarán al usar polyBind2 lugar de polyBind . La primera función ( tst1 x = x polyBind2 (/_ -> Pure 0) ) genera un error de compilación:

Could not deduce (PolyMonad2 m1 Pure b0 out)
arising from the ambiguity check for ‘tst1’
from the context (PolyMonad2 m1 Pure b out, Num b)
bound by the inferred type for ‘tst1’:
(PolyMonad2 m1 Pure b out, Num b) => m1 a -> out
at /tmp/Problem.hs:51:1-37
The type variable ‘b0’ is ambiguous
When checking that ‘tst1’
has the inferred type ‘forall (m1 :: * -> *) b out a.
(PolyMonad2 m1 Pure b out, Num b) =>
m1 a -> out’
Probable cause: the inferred type is ambiguous

Las familias de tipo cerrado intentan resolver el problema

Una forma ligeramente mejor sería usar closed type families aquí, como:

class PolyMonad3 m1 m2 where
polyBind3 :: m1 a -> (a -> m2 b) -> OutputOf m1 m2 b
type family OutputOf m1 m2 a where
OutputOf Pure Pure a = Pure a
OutputOf x y a = Pure (X a)

pero cuando intentamos compilar la función tst1 ( tst1 x = x polyBind3 (/_ -> Pure 0) ) obtenemos otro error de tiempo de compilación:

Could not deduce (OutputOf m1 Pure b0 ~ OutputOf m1 Pure b)
from the context (PolyMonad3 m1 Pure, Num b)
bound by the inferred type for ‘tst1’:
(PolyMonad3 m1 Pure, Num b) => m1 a -> OutputOf m1 Pure b
at /tmp/Problem.hs:59:1-37
NB: ‘OutputOf’ is a type function, and may not be injective
The type variable ‘b0’ is ambiguous
Expected type: m1 a -> OutputOf m1 Pure b
Actual type: m1 a -> OutputOf m1 Pure b0
When checking that ‘tst1’
has the inferred type ‘forall (m1 :: * -> *) a b.
(PolyMonad3 m1 Pure, Num b) =>
m1 a -> OutputOf m1 Pure b’
Probable cause: the inferred type is ambiguous

Un hacky intento de hacerlo alrededor

He encontrado otra solución, pero hacky y al final no funciona. Pero es muy interesante. Consideremos la siguiente clase de tipo:

class PolyMonad4 m1 m2 b out | m1 m2 b -> out, out -> b where
polyBind4 :: m1 a -> (a -> m2 b) -> out

Por supuesto, la dependencia funcional out -> b es simplemente incorrecta, porque no podemos definir tales instancias como:

instance PolyMonad4 Pure IO b (IO (X b)) where
polyBind4 a f = fmap X $ f (fromPure a)
instance PolyMonad4 IO IO b (IO b) where
polyBind4 = undefined

pero juguemos con él y lo declaramos así (usando -XUndecidableInstances ):

instance out~(Pure b) => PolyMonad4 Pure Pure b out where
polyBind4 a f = f (fromPure a)
instance out~(IO(X b)) => PolyMonad4 Pure IO b out where
polyBind4 a f = fmap X $ f (fromPure a)
instance out~(IO b) => PolyMonad4 IO IO b out where
polyBind4 = undefined
instance out~(IO(X b)) => PolyMonad4 IO Pure b out where
polyBind4 = undefined

Lo que es gracioso, algunas de nuestras funciones de prueba SE compilan y funcionan, a saber:

tst1'' x = x `polyBind4` (/_ -> Pure 0)
tst2'' = (Pure 1) `polyBind4` (/_ -> Pure 0)

pero este no:

tst3'' x y = x `polyBind4` (/_ -> y `polyBind4` (/_ -> Pure 0))

lo que resulta en error de tiempo de compilación:

Could not deduce (PolyMonad4 m3 Pure b0 (m20 b))
arising from the ambiguity check for ‘tst3''’
from the context (PolyMonad4 m3 Pure b1 (m2 b),
PolyMonad4 m1 m2 b out,
Num b1)
bound by the inferred type for ‘tst3''’:
(PolyMonad4 m3 Pure b1 (m2 b), PolyMonad4 m1 m2 b out, Num b1) =>
m1 a -> m3 a1 -> out
at /tmp/Problem.hs:104:1-62
The type variables ‘m20’, ‘b0’ are ambiguous
When checking that ‘tst3''’
has the inferred type ‘forall (m1 :: * -> *)
(m2 :: * -> *)
b
out
a
(m3 :: * -> *)
b1
a1.
(PolyMonad4 m3 Pure b1 (m2 b), PolyMonad4 m1 m2 b out, Num b1) =>
m1 a -> m3 a1 -> out’
Probable cause: the inferred type is ambiguous

Aún más intento de hacky usando envoltura de tipo nuevo

Le dije que es aún más hacky, porque nos lleva a usar -XIncoherentInstances , que son Just (Pure evil) . Una de las ideas podría ser, por supuesto, escribir newtype wrapper:

newtype XWrapper m a = XWrapper (m (X (a)))

y algunos utils para descomprimirlo:

class UnpackWrapper a b | a -> b where
unpackWrapper :: a -> b
instance UnpackWrapper (XWrapper m a) (m (X a)) where
unpackWrapper (XWrapper a) = a
instance UnpackWrapper (Pure a) (Pure a) where
unpackWrapper = id
instance UnpackWrapper (IO a) (IO a) where
unpackWrapper = id

ahora podemos declarar fácilmente las siguientes instancias:

instance PolyMonad Pure Pure Pure
instance PolyMonad Pure IO (XWrapper IO)
instance PolyMonad IO Pure (XWrapper IO)
instance PolyMonad IO IO IO 

pero una vez más, no podemos ejecutar nuestras pruebas al combinar las funciones de vinculación y desenlace.

polyBindUnwrap a f = unpackWrapper $ polyBind a f

las funciones de prueba no compilan de nuevo. Podemos -XIncoherentInstances aquí con algunas -XIncoherentInstances (ver el listado del código al final), pero hasta ahora no obtuve ningún resultado aceptable.

La última pregunta

¿Es esto un problema que no se puede hacer usando la implementación actual de GHC Haskell?

Listado de código completo

Aquí hay una lista de código completo, que se puede ejecutar en GHC> = 7.8:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
import Control.Applicative
class PolyMonad m1 m2 m3 | m1 m2 -> m3 where
polyBind :: m1 a -> (a -> m2 b) -> m3 b
----------------------------------------------------------------------
-- Some utils
----------------------------------------------------------------------
newtype Pure a = Pure { fromPure :: a } deriving (Show)
newtype X a = X { fromX :: a } deriving (Show)
main = return ()
----------------------------------------------------------------------
-- Example use cases
----------------------------------------------------------------------
instance PolyMonad Pure Pure Pure where
polyBind a f = f (fromPure a)
instance PolyMonad Pure IO IO where
polyBind a f = f (fromPure a)
instance PolyMonad IO Pure IO where
polyBind a f = (fromPure . f) <$> a
instance PolyMonad IO IO IO where
polyBind a f = a >>= f
-- works when using rebindable syntax
--test = do
-- Pure 5
-- print "hello"
-- Pure ()
tst1 x = x `polyBind` (/_ -> Pure 0)
tst2 = (Pure 1) `polyBind` (/_ -> Pure 0)
tst3 x y = x `polyBind` (/_ -> y `polyBind` (/_ -> Pure 0))
----------------------------------------------------------------------
-- First attempt to solve the problem
----------------------------------------------------------------------
class PolyMonad2 m1 m2 b out | m1 m2 b -> out where
polyBind2 :: m1 a -> (a -> m2 b) -> out
instance PolyMonad2 Pure Pure b (Pure b) where
polyBind2 a f = f (fromPure a)
instance PolyMonad2 Pure IO b (IO (X b)) where
polyBind2 a f = fmap X $ f (fromPure a)
-- ...
-- tst1 x = x `polyBind2` (/_ -> Pure 0) -- does NOT compile
----------------------------------------------------------------------
-- Second attempt to solve the problem
----------------------------------------------------------------------
class PolyMonad3 m1 m2 where
polyBind3 :: m1 a -> (a -> m2 b) -> OutputOf m1 m2 b
type family OutputOf m1 m2 a where
OutputOf Pure Pure a = Pure a
OutputOf x y a = Pure (X a)
-- tst1 x = x `polyBind3` (/_ -> Pure 0) -- does NOT compile
----------------------------------------------------------------------
-- Third attempt to solve the problem
----------------------------------------------------------------------
class PolyMonad4 m1 m2 b out | m1 m2 b -> out, out -> b where
polyBind4 :: m1 a -> (a -> m2 b) -> out
instance out~(Pure b) => PolyMonad4 Pure Pure b out where
polyBind4 a f = f (fromPure a)
instance out~(IO(X b)) => PolyMonad4 Pure IO b out where
polyBind4 a f = fmap X $ f (fromPure a)
instance out~(IO b) => PolyMonad4 IO IO b out where
polyBind4 = undefined
instance out~(IO(X b)) => PolyMonad4 IO Pure b out where
polyBind4 = undefined
tst1'' x = x `polyBind4` (/_ -> Pure 0)
tst2'' = (Pure 1) `polyBind4` (/_ -> Pure 0)
--tst3'' x y = x `polyBind4` (/_ -> y `polyBind4` (/_ -> Pure 0)) -- does NOT compile
----------------------------------------------------------------------
-- Fourth attempt to solve the problem
----------------------------------------------------------------------
class PolyMonad6 m1 m2 m3 | m1 m2 -> m3 where
polyBind6 :: m1 a -> (a -> m2 b) -> m3 b
newtype XWrapper m a = XWrapper (m (X (a)))
class UnpackWrapper a b | a -> b where
unpackWrapper :: a -> b
instance UnpackWrapper (XWrapper m a) (m (X a)) where
unpackWrapper (XWrapper a) = a
instance UnpackWrapper (Pure a) (Pure a) where
unpackWrapper = id
instance UnpackWrapper (IO a) (IO a) where
unpackWrapper = id
--instance (a1~a2, out~(m a2)) => UnpackWrapper (m a1) out where
-- unpackWrapper = id
--{-# LANGUAGE OverlappingInstances #-}
--{-# LANGUAGE IncoherentInstances #-}
instance PolyMonad6 Pure Pure Pure where
polyBind6 = undefined
instance PolyMonad6 Pure IO (XWrapper IO) where
polyBind6 = undefined
instance PolyMonad6 IO Pure (XWrapper IO) where
polyBind6 = undefined
instance PolyMonad6 IO IO IO where
polyBind6 = undefined
--polyBind6'' a f = unpackWrapper $ polyBind6 a f
--tst1'''' x = x `polyBind6''` (/_ -> Pure 0)
--tst2'''' = (Pure 1) `polyBind4` (/_ -> Pure 0)
--tst3'''' x y = x `polyBind4` (/_ -> y `polyBind4` (/_ -> Pure 0)) -- does NOT compile

Answer 1

No creo que esta pregunta dependa de familias de tipo inyectivo.

El bit de familias de tipo inyectivo se menciona en el mensaje de error alrededor de la familia de tipo cerrado OutputOf . Pero, esa función en realidad no es inyectiva, la segunda ecuación ya que permite cualquier x e y . A GHC le gusta recordar a los usuarios el hecho de que no hace análisis de inyectividad para familias de tipos, pero a veces (como aquí), esta advertencia no es útil.

En cambio, los problemas que enfrentas parecen derivarse de números sobrecargados. Cuando dice Pure 0 , GHC infiere correctamente el tipo Num a => Pure a . El problema es que las funciones de nivel de tipo a las que está accediendo (tipo de resolución de clase, dependencias funcionales, familias de tipos) se preocupan mucho por la elección específica que se hace aquí. Por ejemplo, es muy posible que cualquiera de sus enfoques se comporte de manera diferente para Int que para Integer . (Por ejemplo, podría tener diferentes instancias de PolyMonad2 o ecuaciones adicionales en OutputOf ).

La solución a todo esto podría ser utilizar RebindableSyntax y definir fromInteger para que sea monomórfico, por lo tanto, arregle el tipo numérico y evite las molestias.

Answer 2

Creo que la diferencia fundamental es que aquí:

class PolyMonad m1 m2 m3 | m1 m2 -> m3 where
polyBind :: m1 a -> (a -> m2 b) -> m3 b

El b es completamente polimórfico; no es un parámetro para la clase de tipo, por lo que se puede seleccionar la instancia y aplicar la dependencia funcional para determinar m3 de m1 y m2 independientemente de b . También aparece en dos lugares; si el tipo inferencer conoce el tipo de resultado o el tipo de la función que se pasa a polyBind , entonces puede determinar suficientemente b . Y un tipo como Num b => b felizmente "fluirá a través" de muchas aplicaciones de polyBind hasta que se use en un lugar que arregle un tipo de concreto. Aunque creo que puede ser solo la restricción de monomorfismo que establece el tipo que le salva de un error de variable de tipo ambiguo en este caso (exactamente para lo que fue diseñado).

Mientras que aquí:

class PolyMonad2 m1 m2 m3 b | m1 m2 b -> out where
polyBind2 :: m1 a -> (a -> m2 b) -> out

b aparece como un parámetro de clase de tipo. Si estamos intentando inferir qué es, necesitamos determinar completamente b antes de poder seleccionar una instancia. Y no hay ninguna razón para que b tenga una relación particular con la estructura del tipo (o, mejor dicho, esa relación puede ser diferente para cada instancia individual, que es, después de todo, lo que estás tratando de lograr), así que no es posible "sigue la b por" una cadena de llamadas polyBind2 a menos que hayas resuelto todas las instancias por completo.

Y si b es un número polimórfico Num b => b y out está restringido por su uso para que sea de la forma Num c => mc (para algún constructor de tipo m ), no hay ninguna razón para que c y b tengan que ser el la misma instancia Num . Entonces, en una serie encadenada de llamadas polyBind2 operando en números, cada resultado intermedio podría estar usando una instancia Num diferente, y sin conocer ninguna de ellas, no hay forma de seleccionar las instancias correctas de PolyMonad2 que unifican la b con algo dentro. El tipo de incumplimiento solo se aplica si todas las restricciones en la variable son clases de preludio numérico, pero aquí la b está involucrada en la restricción PolyMonad2 m1 m2 m3 b , por lo que no puede ser incumplida (lo cual es probablemente una buena cosa, ya que exactamente de qué tipo usted elige podría afectar qué instancia se usa y cambiar drásticamente el comportamiento del programa, son solo las clases numéricas que se conocen como "aproximaciones" entre sí, de modo que si el programa es ambiguo sobre qué instancia utilizar, entonces es semi-razonable para simplemente elija arbitrariamente uno en lugar de quejarse de la ambigüedad).

Lo mismo vale para cualquier método para determinar desde m1 , m2 b hasta donde yo sé, ya sean dependencias funcionales, familias de tipos o alguna otra cosa. Sin embargo, no estoy seguro de cómo resolver realmente ese problema aquí, sin proporcionar más anotaciones de tipo.