code / art / projects

How the Haskell Prelude Avoids Overlapping Instances in Show

In reading about overlapping instances in haskell, I came across this proposal that mentioned that:

[Overlapping types] can sometimes be simulated with the extra-method trick used in the Show class of the Prelude for showing lists of characters differently than lists of other things.

I’d never thought about how haskell-98 can support a show "asdf" that returns


while show [1,2,3,4] returns


And I was surprised at the complexity of Show when I looked at the docs and implementation (to be honest, I had no idea how the class was implemented or that show was not the only method).

I thought the “extra-method trick” to avoid overlapping types was sufficiently cool and difficult to understand at first to warrant a short post about it. So here goes!

The basic problem

Remember that

type String = [Char]

so we can’t create an instance declaration for it in haskell-98. Something like

instance Show [Char] where

would require both FlexibleInstances and would also cause overlapping instances when we declare

instance Show a=> [a] where

since a [Char] is also a Show a=> [a]. This will never do!

The solution

To get around this, the Creators added a showList method, which allows an instance to define how a list of values of its type should be displayed. Here is the Show class:

-- note: showS is just String -> String, a CPS optimization for building up strings
class Show a where
    showsPrec :: Int -> a -> ShowS
    show :: a -> String
    showList :: [a] -> ShowS

Here’s the instance declaration for [a] where I’ve added the default show implementation from the class declaration:

instance Show a => Show [a]  where
    showsPrec _     = showList 
    show x          = shows x ""    -- default  

after a bit of indirection, we see show str is implemented as:

showList str "" 

where showList is from the Show instance for Char.

The “extra-method” trick pattern

So the general pattern here is when you have a perhaps-limited number of possibly-overlapping, recursive instances

instance Foo (Maybe Int) where
instance Foo (Maybe Bool) where

you can instead create an instance for the outer constructor:

instance Foo a=> Foo (Maybe a) where

define a new method (say maybeToFoo :: Maybe a -> Foo). And then delegate the behavior of Maybe Int and Maybe Char to the Int and Char instances respectively.

instance Foo Int where
instance Foo Bool where

Hopefully that makes sense.