Czy mogę wyeliminować użycie UndecidableInstances w tej instancji Show dla darmowej monady?

Question

Właśnie próbowałem owijać moją głowę wokół wolnych monad; jako pomoc w nauce, udało mi się napisać instancji Show na następny Free typu:

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

Zastosowanie UndecidableInstances denerwuje mnie nieco; czy istnieje sposób, aby obejść się bez niego? Wszystko, co Google zyskuje, to this blog post by Edward Kmett, co pocieszająco ma w zasadzie taką samą definicję klasy jak ja.

Answer 1

rzeczywiście może wyeliminowanie wymogu UndecidableInstance dla Show tutaj, chociaż nie można zrobić to samo dla Read lub Eq.

Sztuką jest zastąpienie treści funktora czymś, co można pokazać bardziej bezpośrednio, ale nie mów nikomu o tym innym. W związku z tym, będziemy ograniczać naszego eksportu po prostu:

{-# LANGUAGE FlexibleContexts #-} 

module Free (Free(..)) where 

i walić się typ danych rzeczy możemy jedynie 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 

Teraz, jeśli nie powiemy nikomu o Showable, jedyne przypadki dla Show (f Showable) będą przypadki, które były polimorficzny w argumencie do a, ograniczonej co najwyżej do pokazu instancji. Jest to uzasadnienie dźwiękowe, o ile użytkownik końcowy nie próbuje aktywnie przekreślić kodu za pomocą innych rozszerzeń. Niektóre huki są możliwe dzięki dodatkowym zależnościom funkcjonalnym i/lub nakładającym się/nierozstrzygalnym instancjom, ale tylko rzeczom, które podważają intencje, nic, co może spowodować awarię.

Po wykonaniu tej czynności możemy zbudować rozstrzygającą instancję 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) 

Realizacja podane tutaj nie eliminuje potrzebę FlexibleContexts, ale można wyeliminować, które też - jeśli czujesz potrzebę Haskell 98 kompatybilności - pisząc kilka dodatkowych warstw klasy.

Używam tej sztuczki w kilku pakietach - w tym moim pakiecie ad - w celu zmniejszenia zapotrzebowania na nierozstrzygalne wystąpienia.