Can I eliminate the use of UndecidableInstances in this Show instance for a Free Monad?

haskell, monads

Solution

You actually can eliminate the UndecidableInstance requirement for `Show` here, though you can't do the same thing for `Read` or `Eq`.

The trick is to replace the contents of your functor with something you can show more directly, but that you don't tell anyone else about. Consequently, we'll limit our exports to just:

{-# LANGUAGE FlexibleContexts #-}

module Free (Free(..)) where

and bang out a data type for things we can only `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

Now, if we never tell anyone about `Showable`, the only instances for `Show (f Showable)` will be instances that were polymorphic in the argument to `a`, constrained at most up to a Show instance. This is sound reasoning as long as the end user isn't actively trying to subvert your code using other extensions. Some hinkiness is possible with the addition of functional dependencies and/or overlapping/undecidable instances but only things that subvert intent, nothing that can cause you to crash.

With that out of the way we can build a decidable `Show` instance.

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)

The implementation given here doesn't eliminate the need for `FlexibleContexts`, but you can eliminate that too -- if you really feel the need for Haskell 98 compatibility -- by writing a couple of additional class layers.

I use this trick in a couple of packages -- including my `ad` package -- to reduce the need for undecidable instances.

Problem

I've just been trying to wrap my head around free monads; as a learning aid, I've managed to write a `Show` instance for the following `Free` type: ``` {-# 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) ``` The use of `UndecidableInstances` bothers me somewhat; is there a way to do without it? All that Google yields is this blog post by Edward Kmett, which comfortingly has basically the same `Show` class definition as I do.

Original source