On 2/5/06, Jim Apple <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
