On 19-Feb-1999, S. Alexander Jacobson <[EMAIL PROTECTED]> wrote:
> Do existential types makes algebraic types obsolete?
> I mean there seems to be a large semantic overlap between the two
> concepts.
>
> For example, once you can implement lists with just the product type (,),
> why bother with algebraic types?
Algebraic types model a fixed set of alternatives.
Type classes (which is what you use in conjunction with
existential types) model an unbounded set of alternatives.
If, as is the case with lists, you know in advance the
fixed set of alternatives, then algebraic types work
much better. If, on the other hand, you don't know
the alternatives in advance, then using type classes
(and, where appropriate, existential types) makes more sense.
> Arguably Boolean is a natural algebraic type, but if we pattern
> match on typenames then we don't need the algebraic types here. e.g.
>
> > --Booleans w/o algebraic types
> > data True = True
> > data False = False
> > class Boolean where -- no methods required
> > instance Boolean True where -- trivial implentation
> > instance Boolean False where --trivial implementation
> > --(There is probably much better syntax for this)
>
> Pattern matching on type names would not be a violation of the type
> system, it would just be syntactic sugar...e.g. for booleans it would be
> equivalent to:
>
> > --Hack because there is no built in pattern matching on type names
> > instance TypeName True where
> > typeName x = "True"
> > instance TypeName False where
> > typeName x = "False"
> > --definition of if' in this framework
> > if' x y z = case (typeName x) of
> > "True" -> y
> > "False" -> z
The problem with this is that there is nothing to stop
someone defining `instance Boolean Int'. So this
doesn't really capture the programmer's intent as
well as the algebraic type does.
It's also going to be less efficient than algebraic types.
> Languages like C and Java do not seem to have an equivalent to algebraic
> types
True. Such alternatives have been proposed, however.
For C++, John Skaller proposed "variants", which were
algebraic types; you may be able to pull up the old
debates on comp.std.c++ using DejaNews.
And for Java, the designers of Pizza extended Java
with algebraic types.
> because they allow heterogenous lists.
I don't think that follows. Pizza for example certainly has an equivalent
to algebraic types but also allows heterogenous lists.
> Are there contexts where you need algebraic types because existential
> types won't do the job? Wouldn't everybody be happier if you could just
> pattern match on type names (someone else requested this in a recent
> thread)?
That might work OK *if* you had union types.
You can use type classes (such as `Boolean' in your example above)
as a poor man's version of union types, but they're really not
ideal in that role.
For an example of a language which explores this, see TEL,
which is the language that Gert Smolka designed for his PhD thesis.
(Gert Smolka is more widely known for the language Oz.)
> Or the most extreme version of this question, once you abandon algebraic
> types, do you need constructor names at all or can you just use
> position e.g.
>
> > data MyType a b = Int a b
> > myFunc (MyType x y z) = MyType (x+1) y z
> > data MyType2 a b = {field1::Int,field2::a,field3::b}
> > myFunc2 x = (field1 x+1,field2 x)
You sometimes need the constructor names to avoid ambiguity.
Consider what happens if you have two different
types that have the same fields:
data PolarCoord = MkPolar Float Float
data RectCoord = MkRect Float Float
class Coord t where ...
instance Coord PolarCoord where ...
instance Coord RectCoord where ...
--
Fergus Henderson <[EMAIL PROTECTED]> | "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh> | but source code lives forever"
PGP: finger [EMAIL PROTECTED] | -- leaked Microsoft memo.
