[mercury-users] Scott Types in Mercury

[Julien Fischer]

On Fri, 25 Apr 2008, Jonathan Morgan wrote:

> In Functional Programming we were looking at Scott types, and Bernie
> mentioned that they were not typable in Haskell (Scott types are
> largely trying to represent ADTs as functions).
>
> I tried to type this in Mercury using existential typing, so that the
> type of the output was completely separate from the type of the list
> (since we want to be able to write functions that take a list and
> return any arbitrary type).  You would like to be able to write
> functions like length below, which allow you to act on the list.
>
> :- type list(A) --->
> 	some[B]
> 	list(
> 		func(B, func(A, list(A)) = B) = B
> 	).
>
> :- func nil = list(A).
> nil = list((func(Nil, _Cons) = Nil)).
>
> :- func cons(A, list(A)) = list(A).
> cons(X, Xs) = list(L) :-
> 	L = (func(_Nil, Cons) = Cons(X, Xs)).
>
> :- func length(list(A)) = int.
> length(list(L)) = L(0, func(_, Rest) = 1 + length(Rest)).
>
> When I try doing this, I get the following errors, referring to the
> typeinfos being free in nil and cons (presumably because I haven't
> given any context from which the type of B can be decided).  Is it
> possible to type these types in Mercury?  If so, what am I doing
> wrong?

For the problem with the type_infos see section 11.3 of the
reference manual,  When "construct(ing) a value using an existentially
quantified functor, you must prepend `new ' onto the functor name".

So, in the above:

 	nil = 'new list'((func(Nil, _Cons) = Nil)).

Likewise, for cons/2. 
(Of course, you'll still get warnings about unresolved polymorphism
in the above code.)

Cheers,
Julien.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------