Tony Davie writes
> All this talk of existential types seems to have crept in from somewhere.
> I certainly don't have earlier messages from the haskell e-mail distributions.
> Was this stuff on news or what? If so, could it be copied to e-mail as not
> all of us get news.
No, this stuff seems to have come out of thin air, as much as I know.
But let me try to give some background information here.
I think the first posting in the thread was Evan's were he argued that
existential types were needed to model polymorphic stream IO. But
existential types have also applications beyond stream IO. In a
nutshell, they allow us to "lift" Haskell's type classes to the level
of types. This allows us to model some of the features associated with
object-oriented programming, such as inheritance, heterogeneous data
structures, and extensible systems.
OOP often means *extending* a given system, and arguably the ease this
can be done with is OOP's biggest strength. Traditional software
development extends programs "at the top", by building on a function or
subroutine library. In OOP one can also extend "at the bottom" by
constructing new components while reusing the central control part.
This is sometimes called "inverted programming".
As an example, consider the classical case of a window handler. This
would consist of a central control part to manage inputs and outputs
and to dispatch events; and user-defined extensions for the behavior
of the individual windows. It is important that the central control
does not fix the type of admissible windows, at least not completely,
because that would restrict extensibility.
Now, type classes seem to be just the ticket for this kind of
development. We could declare a class
class Win w where
display : w -> DisplayList
handle_input: w -> Event -> w
...
and could declare as many instances of Win as we like with instance
declarations. This almost works, except for the fact that we can not
form a data structure of windows. Remember, Win is a type-class,
not a type. Thus, it seems a window handler cannot maintain a list of
all windows on a screen (In fact it can, but it requires very
contorted programming).
Existential types are one way to solve the problem. In extended
Haskell-syntax, we would write:
data Window = Window (Win a => a)
Note that this is *illegal* in standard Haskell, since the type
variable 'a' does not occur on the LHS of the declaration. Now,
the data constructor Window has type
Window :: Win a => a -> Window
i.e. it accepts anything in class Win and returns a Window. Hence
various instances of Win can all be combined in a single list, e.g.:
[Window textwin, Window graphwin, ... ]
On the other hand, if we destructure a Window as in
case w of
Window x -> x
the variable x is of type
x :: exists a . Win a => a -- this is not source-level syntax
That is, we know it is *some* instance of Win, but we do not know
which. Still, since we know it is an instance of Win, we can apply
Win's methods to it. You see the similarity to OOP here.
Mark Sheldon has pointed out to me that similar effects can be
achieved using first class modules with static dependent types.
-- Martin
