¿Puedo eliminar el uso de Incertidumbres Indecibles en esta instancia de Show para una Monad gratuita?

Question

He estado tratando de envolver mi cabeza alrededor de las mónadas libres; como una ayuda para el aprendizaje, me las he arreglado para escribir una instancia Show para el siguiente Free Tipo:

{-# LANGUAGE FlexibleContexts, UndecidableInstances #-} 

-- Free monad datatype 
data Free f a = Return a | Roll (f (Free f a)) 

instance Functor f => Monad (Free f) where 
    return = Return 
    Return a >>= f = f a 
    Roll ffa >>= f = Roll $ fmap (>>= f) ffa 

-- Show instance for Free; requires FlexibleContexts and 
-- UndecidableInstances 
instance (Show (f (Free f a)), Show a) => Show (Free f a) where 
    show (Return x) = "Return (" ++ show x ++ ")" 
    show (Roll ffx) = "Roll (" ++ show ffx ++ ")" 


-- Identity functor with Show instance 
newtype Identity a = Id a deriving (Eq, Ord) 

instance Show a => Show (Identity a) where 
    show (Id x) = "Id (" ++ show x ++ ")" 

instance Functor (Identity) where 
    fmap f (Id x)= Id (f x) 


-- Example computation in the Free monad 
example1 :: Free Identity String 
example1 = do x <- return "Hello" 
       y <- return "World" 
       return (x ++ " " ++ y) 

El uso de UndecidableInstances me molesta un poco; ¿Hay alguna manera de vivir sin eso? Todo lo que Google produce es this blog post by Edward Kmett, que reconfortantemente tiene básicamente la misma definición de clase Show que yo.

Answer 1

En realidad puede eliminar el requisito de UndecidableInstance Show aquí, aunque no se puede hacer lo mismo para Read o Eq.

El truco consiste en reemplazar el contenido de su functor por algo que pueda mostrar más directamente, pero que no le cuenta a nadie más. En consecuencia, nos limitaremos nuestras exportaciones a poco:

{-# LANGUAGE FlexibleContexts #-} 

module Free (Free(..)) where 

y golpear a un tipo de datos para las cosas que sólo puede show.

newtype Showable = Showable (Int -> ShowS) 

showable :: Show a => a -> Showable 
showable a = Showable $ \d -> showsPrec d a 

instance Show Showable where 
    showsPrec d (Showable f) = f d 

Ahora, si nunca decirle a nadie sobre Showable, los únicos casos de Show (f Showable) serán instancias que fueron polimórficos en el argumento de a, limitada como máximo hasta un Show ejemplo. Este es un buen razonamiento siempre que el usuario final no intente subvertir su código con otras extensiones. Es posible que se produzca algo extraño con la adición de dependencias funcionales y/o instancias superpuestas/indecidibles, pero solo cosas que subvierten el intento, nada que pueda hacer que falle.

Con eso fuera del camino podemos construir una instancia decidible Show.

data Free f a = Pure a | Free (f (Free f a)) 

instance (Functor f, Show (f Showable), Show a) => Show (Free f a) where 
    showsPrec d (Pure a) = showParen (d > 10) $ showString "Pure " . showsPrec 10 a 
    showsPrec d (Free as) = showParen (d > 10) $ showString "Free " . showsPrec 10 (fmap showable as) 

La implementación dada aquí no elimina la necesidad de FlexibleContexts, pero se puede eliminar ese también - si usted realmente siente la necesidad de Haskell 98 Compatibilidad - escribiendo un par de capas de clase adicionales.

Utilizo este truco en un par de paquetes, incluido mi paquete ad, para reducir la necesidad de instancias indecidibles.