[Haskell-cafe] local instances / scoped instances

[Anthony Clayden]

Can anybody explain the idea of typeclass instances being
declared with a scope? I’m not sure if these two terms
 mean the same. Perhaps the difference is:
* ‘local instances’ are declared in the familiar
   let-style: `let <instance> in <expr>`
   So the scope is the body of the `in` expr.
* ‘scoped instances’ are declared as usual at the top
   level in a module.
  Scope is controlled by the export/import naming.
  (That is, there’s a way to name/identify instances for
   export/import. Note that currently you can’t
   control scope of instances;
   They’re imported to any module that (transitively)
   imports the module where an instance is declared.)

(I'm doubtful that controlling scope of the
 name-for-instance would actually have
 the desired effect. Compare if I declare:

> data T = MkT Int
> f :: T -> String

and export `f`, but not `T` nor `MkT`;
nevertheless the type of `f` in some distant module
is still `T -> String` (or `M.T -> String`). So detail
of the type itself is exported.

What are the use cases for instances being anything other
than top-level/global scope?

One seems to be so that a method can use a value/function 
declared in a surrounding scope, without needing an explicit
parameter passed around the whole program. 
This is explored in [Kis04] (and linked references, esp.
‘Implicit configurations’), particularly for passing
run-time parameters into methods. 
(What imperative programmers might do via global variables.
 In Haskell: nowadays Implicit Parameters.)

[Kis04] (and especially the link to “The pioneering
work” of Kaes) laments that Kaes’ original description 
of typeclasses/instances has never been delivered. 
I’m not convinced Kaes is actually describing local
instances. He’s giving the formal semantics 
for instances using let-binding; 
because he’s using let as the standard way in Lambda
Calculus to introduce any binding.

Usual let-binding in LC provides a fresh name for each
binding. That is, if that same name is in an outer scope, 
the outer binding is ‘shadowed’/unreachable within the
scope of the fresh name. 

But instance binding is different:
* There’s no fresh name: the class name is exactly
   the one already in scope.
* There’s no ‘shadowing’: this instance is _in
   addition to_ those already in scope.
   — that’s what ‘overloading’ needs.

Overloading a class method with two or more instances in the
same scope means there’s no principal type for the method 
[W&B88 Appendix A.7]. 
That’s why in Haskell classes/instances/methods are at top
level only. The methods then do have a most-general
 principal type `show :: (Show a) => a -> String`.

This early work was of course before MPTCs, FunDeps,
Overlaps, Flexible Instances/Contexts, 
constrained existentials, constrained GADTs. 
AFAICT it was expected there would be only one instance per
type. So making instances global probably wasn’t too
limiting.

I’ve seen some later ideas (especially ‘scoped
instances’ blocking the export of an instance) 
where the intent seems to be to have 
_different_ instances in different scopes for the
same class/same type. 
For example (apparently) a ‘pretty print’ format for
`show`. Or an alternative `Ord` for case-insensitive
 sorting of Chars/Strings.

What are the use cases here? In particular, what’s wrong
with either:
* using a different class/method name for different
   behaviour (for example supplying a different comparison
   via `sortBy`); or
* wrapping in a newtype and declaring an instance of
  `Show/Ord` on the different nominal type?

I’m worried: classes come with laws. 
For example wrt case-insensitive `Ord`: `Eq` is a
superclass. So if we get case-insensitive `‘A’ <=
‘a’` and
`‘a’ <= ‘A’`, the laws expect ` ‘A’ ==
‘a’ `. 
Specifically the base library `Data.Set` relies on those
laws for `Ord` to build balanced trees.

(There’s also a whole load of puzzlement to do with 
how the instance scoping rules work, as explored in [Kis04].
But I don’t want to worry about the implementation yet.)


AntC

[Kis04] Local instances: frequently still discussed and
still not implemented, Kiselyov O. 
??originally 2004, current version 2014
http://okmij.org/ftp/Haskell/TypeClass.html#local
See also papers linked/referenced from that site.
(Thank you Oleg for bringing out the issues.)

[Kaes88] Parametric Overloading in Polymorphic Programming
Languages, Kaes S. 1988
https://link.springer.com/content/pdf/10.1007%2F3-540-19027-9_9.pdf

[W&B88] How to make ad-hoc Polymorphism less ad-hoc, Wadler
P. & Blott S. 1988
https://people.csail.mit.edu/dnj/teaching/6898/papers/wadler88.pdf