Kann ich die Verwendung von UndecidableInstances in dieser Show-Instanz für eine kostenlose Monade eliminieren?

Question

Ich habe gerade versucht, meinen Kopf um freie Monaden zu wickeln; als Lernhilfe, ich habe eine Show Instanz für die folgenden Free Art schreiben verwaltet:

{-# 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) 

Die Verwendung von UndecidableInstances stört mich etwas; Gibt es einen Weg, darauf zu verzichten? Alles, was Google liefert, ist , was im Grunde die selbe Show Klassifizierungsdefinition ist wie ich.

Answer 1

Sie tatsächlich die für Show hier UndecidableInstance Anforderung beseitigen, wenn Sie nicht die gleiche Sache für Read oder Eq tun können.

Der Trick besteht darin, den Inhalt Ihres Funktors durch etwas zu ersetzen, das Sie direkter zeigen können, aber über das Sie niemandem mehr erzählen. Folglich werden wir unsere Exporte nach nur begrenzen:

{-# LANGUAGE FlexibleContexts #-} 

module Free (Free(..)) where 

und einen Datentyp für Dinge bang können wir nur 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 

Nun, wenn wir nie Showable jemand erzählen, die einzigen Instanzen für Show (f Showable) werden Instanzen, die a im Argument polymorphen waren, höchstens eingeschränkt bis zu einer Show-Instanz. Solange der Endbenutzer nicht aktiv versucht, den Code mit anderen Erweiterungen zu unterlaufen, ist dies eine vernünftige Argumentation. Eine gewisse Herablassung ist möglich, wenn funktionale Abhängigkeiten und/oder überlappende/unentscheidbare Instanzen hinzugefügt werden, aber nur Dinge, die die Absicht untergraben, nichts, was einen zum Absturz bringen kann.

Mit dieser aus dem Weg können wir eine entscheidbare Show Instanz erstellen.

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) 

Die hier gegebene Implementierung beseitigt nicht die Notwendigkeit für FlexibleContexts, aber Sie können das beseitigen - wenn Sie wirklich die Notwendigkeit für Haskell 98 Kompatibilität fühlen - durch ein paar zusätzliche Klasse Schichten zu schreiben.

Ich benutze diesen Trick in ein paar Paketen - einschließlich meines ad Pakets - um die Notwendigkeit von unentscheidbaren Instanzen zu reduzieren.