Brandon.Si(mmons)

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

"\"asdf\""

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

"[1,2,3,4]"

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.

Comments