returning to instance overlap

[Bertram Felgenhauer]

Serge D. Mechveliani wrote:
> Dear GHC developers,

I'm not one of them, but maybe I can help anyway.

> can you exaplain, please, how to use overlapping instances? 
> 
> For example, the following program uses overlapping instances for  
> DShow [a]  and  DShow String,  but ghc-6.8.2 reports an error:
> 
> -----------------------------------------------------------------
> class DShow a where  dShows :: a -> String -> String
> 
> instance DShow Char where  dShows = showChar 
> instance DShow Int  where  dShows = shows 
> 
> instance DShow a => DShow [a]                                   -- (1)
>   where 
>   dShows _ = showString "contrived show value"    
> 
> instance DShow String where  dShows = shows                     -- (2)
> 
> f :: DShow a => [a] -> String 
> f               xs  =  dShows xs "" 
>                        -- dShows (head xs) ""    -- compare to this
> 
> main = putStr (shows (f "abc", f [1, 2, 3 :: Int]) "\n")
> -----------------------------------------------------------------

Does the trick from the Show class help you? Simplified, it is
the following:

class Show a where
    show :: a -> String
    showList :: [a] -> String
    showList = default implementation for showList

instance Show Char where
    show = ...
    showList = specific implementation for String

instance Show a => Show [a] where
    show = showList

By putting the showList function into the Show class, we get
a special treatment of Strings in Haskell 98, without any overlapping
instances at all.

> I compile this under 
>   -fglasgow-exts -fallow-overlapping-instances 
>   -fallow-undecidable-instances  
>   -fno-warn-overlapping-patterns -fwarn-unused-binds 
>   -fwarn-unused-matches -fwarn-unused-imports
> 
> But the  ghc-6.8.2  compiler reports  
> 
>    Overlapping instances for DShow [a]
>       arising from a use of `dShows' at IOverlap.hs:21:23-34
>     Matching instances:
>       instance [overlap ok] (DShow a) => DShow [a]
>         -- Defined at IOverlap.hs:(14,0)-(16,45)
>       instance [overlap ok] DShow String
>         -- Defined at IOverlap.hs:18:0-42
>     (The choice depends on the instantiation of `a'
>      To pick the first instance above, use -fallow-incoherent-instances
>      when compiling the other instance declarations)
>     In the expression: dShows xs ""
>     In the definition of `f': f xs = dShows xs ""

If you haven't done so already, you should read
    http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap
    (http://tinyurl.com/2cq3zm)

What ghc is saying here is that there are two instances of DShow that
can potentially match DShow [a]. That's bad because the compiler might
pick a 'wrong' instance if it proceeds.

Even with -fallow-incoherent-instances, the compiler is free to choose
either instance, although it will try to use the most specific instance
that fits the requirements.

In your case, however, the most specific instance of DShow for [a]
that fits the requirements (which are that the instance can be
derived from the function's context alone) is DShow a => DShow [a],
so the compiler picks that one. (Btw, one key point to keep in mind
here is that ghc does not have any run time type information).

You can fix your program by declaring

    f :: DShow [a] => [a] -> String

or even

    f :: (DShow a, DShow [a]) => [a] -> String

which will postpone the selection of the instance of DShow [a] to
the point where f is called.

> 3. Also DoCon uses overlapping instances, and works under ghc-6.8.2, 
>    somehow (probably, I need to recall what precisely this usage is). 

There's only trouble with overlapping instances when you have several
instances for the same type with different behaviour. (I don't know
whether that's true or not for DoCon.)

> 4. Maybe, it is good compile the above declaration
> 
>   f :: DShow a => [a] -> String 
>   f xs = dShows xs "" 
> 
> by relating to  dShows  the _set_   S = {dShows of (1), dShows of (2)}   
> of two instances,
> putting to the code the set of two implementations.

That might work to some extent, but I think there are good reasons not
to do that.

1) the number of different implementations of f that you have to keep
   around can be very large. Consider

   f :: (DShow a, DShow b, DShow c) => [a] -> [b] -> [c] -> String
   f as bs cs = dShows as . dShows bs . dShows cs $ ""

   which will need 8 copies of f to work.

2) with higher order functions, the final type the function will get
   called with may never be known until runtime, say,

   g :: (forall a . DShow a => [a] -> String)
     -> Either String [Int] -> String
   g f (Left a)  = f a
   g f (Right b) = f b

   (consider g (\xs -> dShows xs "") -- which dShows should be used here?)

HTH,

Bertram