[m-dev.] Re: For review: changes to graph.m

[Fergus Henderson]

Peter Schachte, you wrote:
> 
> It has occured to me that an extension to type classes could provide an
> answer to this.

The extension you're after, I think, is called "overlapping instance
declarations".  It is supported in Gofer, but not in Haskell.

E.g. you can have 

	-- this example uses Haskell syntax
	
	class Map m where
		map_init :: m		-- returns an empty map
		...

	type AssocList k v = ...
	instance Eq k => Map (AssocList k v) where
		map_init = assoc_list_init
		...

	type Tree k v = ...
		-- the `Comparable' type-class is called `Ord' in Haskell
	instance (Ord k) => Map (Tree k v) where	
		map_init = tree_init
		...

	type Tree k v = ...
	instance (Hashable k) => Map (Tree k v) where
		map_init = hash_init
		...

> The remaining question is how the compiler finds all the different
> implementations of a type class, and how it chooses the best one. One
> solution would be to have a file for each type class that the user wants
> to use as if it were a type that lists the types that inhabit that class
> in order of preference.  The compiler would then pick the first type for
> which parametric types meet the type class criteria, as described above.

I think you can have code such as

	let
		map0 = map_init
		map1 = map_insert map0 "foo" 42
	in 
		..
	
and I think then Gofer's type inference will figure out which instance
declaration to use based on which type-classes String is an instance
of.  If String is an instance of just Eq, it would use an AssocList.
If String was an instance of both Eq and Ord (which is a subclass of
Eq), then it would use Ord, because that is more specific.
If String has both Hash and Ord, and neither is a subclass of the other,
and there is no instance declaration requiring both Hash and Ord,
then I think it is ambiguous, and you have to resolve the ambiguity
with an explicit type declaration, or by providing an instance
declaration that is more specific than both.

This main problem with overlapping instance declarations is that
they basically prevent separate compilation.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.