[Haskell] really undecidable instances?

David Menendez zednenem at psualum.com
Sun Oct 30 15:59:48 EST 2005

Benjamin Franksen writes:

> This is the data type declaration:
> > data Node23 tree a
> >   = N2 (tree a) a (tree a)
> >   | N3 (tree a) a (tree a) a (tree a)
> and this is the instance, where the error is reported:
> > instance (Pretty a, Pretty (tree a)) => Pretty (Node23 tree a) where
> >   ...
> The class Pretty is from Daan Leijen's pprint library.
> I think that the 'non-type variable' refered to above is the
> application (tree a) in the constraint (Pretty (tree a)), which is
> arguably "almost" a type variable. In this case I think it is even
> more obvious that it can't cause a loop, since the LHS clearly has a
> type constructor removed, right?
> I mention this mainly because my module is otherwise completely H98
> and I thought it would be nice to keep it that way. I need the Pretty
> instance for debugging only, so it's not really a show-stopper. Still
> I wonder if somebody knows a work-around that doesn't need a language
> extension (some newtype trick, maybe?).

I believe the "correct" way to do this is with a Pretty-promoting
constructor class.

    class Pretty'1 f where
        pretty'1 :: Pretty a => f a -> Doc
        prettyList'1 :: Pretty a => [f a] -> Doc
    instance (Pretty a, Pretty'1 tree) => Pretty (Node23 tree a) where

Your typical Pretty'1 instance will look like this:

    instance Pretty'1 T where
        pretty'1 = pretty
        prettyList'1 = prettyList
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"

More information about the Haskell mailing list