[mercury-users] Higher-order types using typeclasses

[Mark Brown]

On 16-Mar-2007, Ondrej Bojar <bojar at csse.unimelb.edu.au> wrote:
> Hi,
> 
> I would like to abstract over container implementation when I am already 
> abstracting over the element type.
> 
> If successful, I would be able to implement:
> 
> :- pred my_sample_predicate(ContainerOfX::in, X::out, ...)
>        <= (container(ContainerOfX, X)) is ...
> 
> The container typeclass defines required operations on the container:
> 
> :- typeclass container(Cont, Elem) <= (Cont->Elem) where [
>         pred get_a_member(Elem::out, Cont::in, Cont::out) is nondet,
>         func count(Cont) = int
>    ].
> 
> And I would instantiate the typeclass for various containers:
> 
> :- instance container(bag(X), X) where [
>      pred(get_a_member/3) is bag_nondet_member,
>      func(count/1) is bag_count
>    ].
> 
> However, the intended instantiation is not possible:
> 
> t_drop_fr_reins.m:492: Error: types in instance declarations must be 
> functors wi
> th distinct variables as arguments: container(bag(_1), _1).
> 
> Are there any fundamental reasons for the restriction?

No.  The main requirement is that any proof that a sequence of types
is in a typeclass must be unique -- there must not be more than one way
to construct the dictionary that satisfies a given typeclass constraint.

The current restrictions on typeclass instances are sufficient to ensure
this uniqueness, but they aren't necessary.  In theory it is possible to
allow variables as instance arguments, and to allow variables to occur
more than once in the arguments, as long as no two instances overlap
(that is, no two sequences of instance arguments for a typeclass
can be unified).

When Mercury's typeclass system was implemented this wasn't understood
so well, and as a result the restrictions are built fairly deeply into
the implementation.  If we had a better understanding of CHRs and
constraint programming at the time, we would probably have done it
differently.  :-(

> Is there a way to overcome the restriction in the current Mercury 
> implementation?

It would be a lot of work.  But it is in our longer term plans to
relax the restrictions on typeclass instances.

Cheers,
Mark.

--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------