Mercury Bugs - mercury
View Issue Details
0000185mercuryBugpublic2011-02-03 17:452011-02-16 14:00
Reportermgiuca 
Assigned To 
PrioritynormalSeveritymajorReproducibilityalways
StatusconfirmedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0000185: Cannot make typeclass instance for parameterised equivalence type
DescriptionIt seems that it is impossible to create a typeclass instance for any type that is all of the following:
1. parameterised, and
2. declared in another module to the instance declaration, and
3. declared abstractly and defined in the "implementation" section, and
4. defined as an equivalence type (==).

Notably, this includes the 'set' type. I have created a tiny self-contained example:

In the file foo.m:

:- module foo.

:- interface.

:- type foo(T).

:- implementation.

:- type foo(T) == bar(T).

:- type bar(T) ---> bar.

In the file problem.m:

:- module problem.

:- interface.

:- typeclass myclass(T) where [
    func f(T) = int
].

:- implementation.

:- import_module foo.

:- instance myclass(foo(T)) where [
    f(_) = 4
].

Notice that the type 'foo' is parameterised, abstract, and defined as an equivalence to bar. In the other module, I am attempting to make foo(T) an instance of myclass. 'foo' compiles properly, but compiling 'problem' leads to this nonsensical error:

problem.m:013: In instance declaration for `problem.myclass(foo.foo(T))':
problem.m:013: the first arg contains a type variable which is used in
problem.m:013: another arg

With -E, it explains, "types in instance declarations must be functors with distinct variables as arguments". If I am reading this correctly, it is telling me that I have used the type variable `T' in multiple arguments to foo, which can't be true because it only has one argument.

For a real-world example, in 'problem', replace 'foo' with 'set'; the same error arises. I haven't found any way to make 'set' an instance of a typeclass.
Additional InformationCan anybody suggest a workaround for this issue? I would like to make 'set' a member of a typeclass.

This isn't a problem for many other standard library types. For example, it doesn't affect 'list' because list is not defined as an equivalence type. It doesn't affect 'map' because map is not abstract (even though it doesn't appear in the documentation, map(K, V) is defined as equivalent to tree234(K, V) under a subsequent "interface" section, so it is not considered abstract).
TagsNo tags attached.
Attached Files

Notes
(0000304)
juliensf   
2011-02-04 01:07   
The usual workaround (which has in fact, already been implemented for most of the other
abstract equivalence types in the standard library) is to use a notag type to wrap the equivalence.
That is

:- type set == set_ordlist(T)

becomes:

:- type set ---> set(set_ordlist(T)).

and then modify the code in the set module appropriately. (There's no performance overhead
to this; such types are optimised so the representation is the argument.)
(0000305)
mgiuca   
2011-02-04 13:23   
So are you suggesting that the set module be changed this way? I can do it if you want.

Is this bug a duplicate of another, or was it simply known without having been reported?

The set module aside, can something at least be done about the error message? Such as "Not supported: Instance of parameterised abstract equivalence type."
(0000306)
juliensf   
2011-02-04 19:02   
Looking at the set module a bit closer, I don't think we want to do what I suggested.
It would make the union_list operation, amongst others, more expensive (because
you would need to make a pass over the list of sets in order to strip the tag -- I'm
not sure that the compiler is clever enough to realise that such a traversal is redundant.)

A possible workaround is to simply use the set_ordlist/1 type in place of set/1.
This is equivalent since the set module just forwards everything to set_ordlist anyway.
(set_ordlist/1 is wrapped in a notag type and is usable in type class instances.)

(In the long term, whenever Mercury supports constructor classes, I would expect the
existing set type to be replaced by a type class and the various set types in the stdlib
being instances of that.)

The problem with the error message in the foo.m and problem.m is definitely a bug
a needs to be looked at. Despite foo/1 being an asbstract type, its definition is exported
in the interface file for the module foo, so when compiling the module problem the compiler
can definitely see it!
(0000308)
mgiuca   
2011-02-07 10:47   
I see the point about union_list. Wouldn't a much simpler and less-destructive workaround be to move "set(T) == set_ordlist(T)" into the interface, making it non-abstract? It would be in the *second* interface section, so the equivalence is not visible in the user documentation. This is the same as the way map is defined.

I've tried it and it works.

--- library/set.m 13 Nov 2010 16:49:27 -0000 1.89
+++ library/set.m 6 Feb 2011 23:45:30 -0000
@@ -381,8 +381,11 @@
 
 :- interface.
 
+:- import_module set_ordlist.
 :- import_module term. % for var/1.
 
+:- type set(T) == set_ordlist(T).
+
 :- pragma type_spec(set.list_to_set/2, T = var(_)).
 :- pragma type_spec(set.list_to_set/1, T = var(_)).
 
@@ -409,10 +412,6 @@
 
 :- implementation.
 
-:- import_module set_ordlist.
-
-:- type set(T) == set_ordlist(T).
-
 set.list_to_set(List, Set) :-
     set_ordlist.list_to_set(List, Set).
(0000313)
juliensf   
2011-02-16 14:00   
I've made the above change to the definition of set(T).

The issue with the error message still needs to be resolved.

Issue History
2011-02-03 17:45mgiucaNew Issue
2011-02-04 01:07juliensfNote Added: 0000304
2011-02-04 13:23mgiucaNote Added: 0000305
2011-02-04 19:02juliensfNote Added: 0000306
2011-02-04 19:03juliensfStatusnew => confirmed
2011-02-07 10:47mgiucaNote Added: 0000308
2011-02-16 14:00juliensfNote Added: 0000313