[Haskell-cafe] Understanding GHC's instance inference.

[Takayuki Muranushi]

Dear everyone,

I have a code
https://github.com/nushio3/practice/blob/master/instance-inference/zipf-11-1.hs

that produces a type-error when I remove a type signature.
https://github.com/nushio3/practice/blob/master/instance-inference/zipf-11.hs

The strange point is the following error message from ghc 7.6.1
(abbreviated; the full error text is included as the comment of the
code):

    No instance for (PType
                       (Cons
                          V.Vector
                          (V.Vector Double)
                          (Cons
                             V.Vector
                             (V.Vector Char)
                             (Cons V.Vector (V.Vector Int) (Nil V.Vector))))
                       ((Double -> Char -> Int -> String) -> a0))
      arising from a use of `forZN'
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there is a potential instance available:
      instance [overlap ok] (Zip v, Reduce v f0 vaS r (Nil v)) =>
                            PType (Cons v (v i) vaS) ((i -> f0) -> v r)



ghc presents only one potential instance, and it seems to me that by setting
v = V.Vector
i = Double
f0 = Char -> Int -> String
r = String

etc, you can actually match the 'potential' instance. The fact that
this code typechecks with an additional type signature (zipf-11-1.hs)
shows that there is a way to satisfy the constraint. So the question:
why the instance inference stops here, when there is only one
potential instance and no ambiguity? Or is it? What are potential
instances?

I thought the cause of the error is that ghc cannot match (v r) with
(a0), and so I tried to shrink the example before I post. However my
guess was wrong. Tinyer example did typecheck:

https://github.com/nushio3/practice/blob/master/instance-inference/copy-01.hs
https://github.com/nushio3/practice/blob/master/instance-inference/copy-02.hs
https://github.com/nushio3/practice/blob/master/instance-inference/copy-04.hs

If you have any sample codes that fails to typecheck and presents only
one "potential instance" , that will be a great clue for me. Also,
please recommend me any reading material for instance inference.
(Haskell 98 deals with instance declaration syntax, and there are
variety of text for type inference, but I could find few for instance
inference.)


Best,
--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html