[Haskell-cafe] [Q] multiparam class undecidable types - how to get this example to typecheck?

[Matthias Fischmann]

Hi everybody,

I am torturing the ghc type inference extensions, and I think i
managed to break something, either in ghc or (more likely) in my
brain:


| {-# language FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-}
| 
| module Main
| where
| 
| class Table table cell where
|   toLists :: table -> [[cell]]
|   fromLists :: [[cell]] -> table
| 
| instance Table [[cell]] cell where
|   toLists = id
|   fromLists = id
| 
| -- why i am using a class (not relevant for my question) -
| -- data FastTable a = FastTable ...
| -- instance Table (FastTable a) a where ...
| 
| instance (Table a c, Show c) => Show a where
|   showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (toLists t)


ghc 7.0.3 sais:


|     Overlapping instances for Show [[cell0]]
|       arising from a use of `shows'
|     Matching instances:
|       instance Show a => Show [a] -- Defined in GHC.Show
|       instance (Table a c, Show c) => Show a
|         -- Defined at /home/mf/tmp/z.hs:18:10-38
|     In the second argument of `(.)', namely `shows (toLists t)'


I would have thought that there is on overlap: the instance in my code
above defines how to show a table if the cell is showable; the
(allegedly) overlapping instance defines how to show lists of alpha if
alpha is showable.

So I was expecting the reduction to go something like:

 . table ~> [[cell]] (via whichever instance of class Table applies)
 . [[cell]] ~> [cell] (via instance "Show a => Show [a]")
 . [cell] ~> cell (via instance "Show a => Show [a]")


But it gets worse.  I decided to ignore the problem for now and be
happy with at least showing the first cell in the upper left corner of
the table:


| instance (Table a c, Show c) => Show a where
|   showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (head . head $ toLists t)


to that, ghc 7.0.3 sais:


| /home/mf/tmp/z.hs:19:66:
|     Context reduction stack overflow; size = 21
|     Use -fcontext-stack=N to increase stack size to N
|       $dShow :: Show c19
|       $dShow :: Show c18
| [...]


shouldn't type inference be able to determine that

|  ((head . head $ toLists t) :: c

and use the instance guaranteed by the instance declaration's class
constraint (Show c)?

I suspect that there should be a type annotation that would make this
approach possible, but even then I am curious what this behavior
means.

Should I upgrade to a more grown-up release of ghc?

Any hints or pointers appreciated.  (:

Thanks,
Cheers,
Matthias