[mercury-users] Another place for existentials?

[Michael Day]

> > % match is a type class for regular expressions
> > :- typeclass match(C, T) where [ ... ].
> > 
> > :- instance match(char, string).	% can match characters in strings
> > :- instance match(string, string).	% can match strings in strings
> 
> OK, fine so far ...
> 
> > :- instance match(list(T), U) <= match(T, U).	% error
> 
> This will fail to compile because it doesn't satisfy the restriction
> on type class instances.  The reference manual details this restriction
> and its rationale.  There is a simple workaround for it which should work
> in this case:
> 
> 	:- type list_like(X) ---> list_like(X).
> 	:- instance match(list(T), list_like(U)) <= match(T, U).

That works, but look at the consequences:

:- instance match(char, string).
:- instance match(string, string).
:- instance match(list(T), stream(Stream)) <= match(T, Stream).

Now we have match(char, string) and match(list(char), stream(string)). We
can't use them together, which defeats the purpose of the type class. If
everyone uses the type wrapper:

:- instance match(char, stream(string)).
:- instance match(string, stream(string)).
:- instance match(list(T), stream(Stream)) <= match(T, Stream).

This doesn't work either, as the third instance declaration strips off the
wrapper type. How about:

:- instance match(char, stream(string)).
:- instance match(string, stream(string)).
:- instance match(list(T), stream(Stream)) <= match(T, stream(Stream)).

Well, that's bogus isn't it.

> > :- instance match(list(char), string).		% error
> 
> In this case, the workaround is even simpler:
> 
> 	:- type char_list ---> char_list(list(char)).
> 	:- instance match(char_list, string).

:- type char_list == list(char).

Appears to work too. If a public equivalence type of this nature can be
accepted by the compiler, is there any reason why it couldn't accept the
first type directly? Does it relate to conflicts from instance
declarations like these:

:- instance foo(list(T)).
:- instance foo(list(char)).

> As it happens, this added verbosity has made the code much easier to maintain.
> The two typeclasses essentially represent the same data, but at two different
> levels of abstraction.  The `wrap' constructor makes explicit in the code the
> point at which we change from one level of abstraction to the other.  So, not
> only does the constructor help the compiler understand the program, it also
> helps the user do the same.

That's nice, but I don't believe that the same benefits will be reaped in
all code that could use multi-parameter type classes. Particularly in the
case I describe above, in which one instance declaration depends on others
*for the same type class*, the introduction of wrapper types seems to
destroy what I was setting out to create.

Pedantic afterword:

I could resolve the difficulties by overloading match (in a submodule
<sigh>) in the following way:

:- pred match(M, Stream, Stream) <= match(M, stream(Stream)).

But dammit, you can't have constraints on compound types.

Michael

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------