[Haskell-cafe] [Q] multiparam class undecidable types

[Matthias Fischmann]

Thanks Oleg,

that was very helpful.  i can work with that.  read the rest of this
if you are curious where your hints took me.

you are right, I need to make the functional dependency explicit:

| class Table t c | t -> c where
|   toLists   :: t -> [[c]]
|   fromLists :: [[c]] -> t
| 
| instance Table [[c]] c where
|   toLists   = id
|   fromLists = id
| 
| instance (Table t c, Show c) => Show t where
|   showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (head . head $ toLists t)

this compiles, and 'show' prints the first cell of each table.  i also
understand now why i can't just print all of them: [[Int]] is one of
the types where the instances overlap.

| instance Show Int
| instance Show a => Show [a]

vs.

| instance Table [[Int]] Int
| instance (Table [[Int]] Int, Show Int) => Show [[Int]]

the advanced overlap code you are referencing below is fascinating,
but isn't it a different problem?  i don't want to distinguish
different the cases "Show c" and "Typeable c", but i want to use
whatever instance of "Show c" is available to implement "Show t".

i can't make your solution work for this, because one of the two
overlapping instances (namely "Show a => Show [a]") is already
provided by the surrounding code that i cannot outfit with the
advanced overlap trick.  or am i missing something here?

i think what i will do is to instantiate all table types individually:

| instance Show c => Show (SimpleTable c) where
|   showsPrec p t = showParen (p > 10) $ showString "FastTable " .
|                                         shows (toLists t)

cheers,
matthias



On Wed, May 09, 2012 at 06:41:00AM -0000, oleg at okmij.org wrote:
> Date: 9 May 2012 06:41:00 -0000
> From: oleg at okmij.org
> To: fis at etc-network.de
> CC: haskell-cafe at haskell.org
> Subject: Re: [Q] multiparam class undecidable types 
> 
> 
> > | instance (Table a c, Show c) => Show a where
> > 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;
> 
> No, the instance defines how to show values of any type; that type
> must be an instance of Table. There is no `if' here: instances are
> selected regardless of the context such as (Table a c, Show c)
> above. The constraints in the context apply after the selection, not
> during.
> 
> Please see 
> 	``Choosing a type-class instance based on the context''
> 	http://okmij.org/ftp/Haskell/TypeClass.html#class-based-overloading
> 
> for the explanation and the solution to essentially the same problem.
> 
> There are other problems with the instance:
> 
> | instance (Table a c, Show c) => Show a where
> 
> For example, there is no information for the type checker to determine
> the type c. Presumably there could be instances
> 	Table [[Int]] Int
> 	Table [[Int]] Bool
> So, when the a in (Table a c) is instantiated to [[Int]] 
> there could be two possibilities for c: Int and Bool. You can argue
> that the type of the table uniquely determines the type of its
> cells. You should tell the type checker of that, using functional
> dependencies or associated types:
> 
> 	class Table table where
> 	  type Cell table :: *
> 	  toLists :: table -> [[Cell table]]
> 
> 
>