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

Question

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.

Answer 1

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.