[mercury-users] higher order types + type class constraints

[Fergus Henderson]

On 28-Nov-2000, Michael Day <mikeday at corplink.com.au> wrote:
> 
> How does one pass around higher order terms that have type class
> constraints?

You can't.  In fact you can't pass around polymorphic higher-order
terms at all.  Mercury does not directly support "first class polymorphism".

However, there is a work-around: you can achieve the same effect using
type classes and existential types.

> This is not correct:
> 
> :- pred foo(pred(C, C) <= something(C), other args ...).
> :- mode foo(pred(di, uo) is det, other args ...) is det.

Right.  That is almost the syntax that we'd use if we were to support
first class polymorphism; however, we'd use an explicit quantifier:

	:- pred foo(all [C] (pred(C, C) <= something(C)), other args ...).

> While this compiles, but doesn't work:
> 
> :- pred foo(pred(C, C), other args ...) <= something(C).
> :- mode foo(pred(di, uo) is det, other args ...) is det.
> 
> foo(P, others ...) :-
> 	create C0,
> 	P(C0, C)		% error here, expects type to be `C'

Yes, you get an error here, because `P' is monomorphic at this point;
the type `C' must be determined by the caller of `foo'.

> Any suggestions?

The work-around goes like this.
Define a typeclass with a single method whose type matches
the type of the higher-order pred term that you want to pass,
but with the typeclass parameter as an additional argument:

	:- typeclass my_poly_pred(T) where [
		(pred call_it(T, C, C) <= something(C)),
		(mode call_it(in, di, uo) is det)
	].

Then change your predicate which gets passed this higher-order term
so that it instead gets passed a value of this typeclass:

	:- pred foo(Pred, other args ...) <= my_poly_pred(Pred).
	:- mode foo(in, other args ...) is det.

	foo(P, others ...) :-
		call_it(P, C0, C).

Then, instead of calling `foo' as 

		foo(bar, ...)

you would define a dummy type called as `bar_t'
(or just `bar' if you prefer),

	:- type bar_t ---> bar_t.

make that type an instance of the typeclass you defined earlier,
and have the method call `bar':

	:- instance my_poly_pred(bar_t) where [
		call_it(_, C0, C) --> bar(C0, C)
	].

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