Restricted data types

[John Hughes]

On 2/5/06, Jim Apple <jbapple+haskell-prime at gmail.com> wrote:

>> Have we considered Restricted Data Types?
>>
>> http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps
>  
>

Nice to see my old paper hasn't sunk without trace!

As Taral pointed out, though, Restricted Data Types have not been implemented, and they can't be seriously considered for Haskell' until they have been. They are a fairly major extension, requiring changes to the way context reduction works, and introducing many new constraints to contexts. That said, the problem they address comes up again and again and again, so I think it would be worth making a serious attempt to solve it--but not necessarily for Haskell'.

A few points.

Perhaps the biggest disadvantage of Restricted Data Types from an implementation point of view is the need to pass a potentially large number of dictionaries to overloaded monadic functions, which in most cases will never be used. For jhc, this would not be a problem, of course--so perhaps jhc is the best setting to try RDT's out in. For dictionary passing implementations, I suggested compiling two versions of each affected function, one fast version without the RDT dictionaries for the common case, and the other with them for the general case. It's not clear how many functions would be affected, or how much code size would grow as a result.

>From a language point of view, introducing well-formed-type constraints into contexts can make definitions overloaded that were formerly polymorphic, thus triggering the M-R and potentially causing type errors. But if the M-R were reformed, for example as Simon M suggested, so as not to distinguish between polymorphic and overloaded definitions, then this problem would go away. (Or rather, it would strike regardless of RDTs, so someone else would carry the blame!).

Finally, I wrote my paper before fundeps came on the scene. Some of the contortions I went through in my simulation of RDTs could be avoided with the help of fundeps. The alternative solution I discuss at the end--parameterising classes and functions over contexts--would also benefit frlom fundeps. A Collection class could be defined something like this:

	class Collection c cxt | c -> cxt where
	  empty :: cxt a => c a
	  member :: cxt a => a -> c a -> Bool
	  ...

I still think it's nicer to associate cxt with c at the type definition of c, rather than in instance definitions of potentially many classes, but this alternative should be considered. How it would relate to associated types I can't imagine--associated contexts?

Summary: it would be great to add RDTs to Haskell, but there's a lot of work to be done before they can be considered for the standard.

John