Wed, 3 Nov 1999 21:27:10 -0800 (PST), Ronald J. Legere <[EMAIL PROTECTED]> pisze:
> Second, I have to ask again about Existential types. These beasties
> I just cant figure out. Why are they usefull???
They allow putting together values containing components of different
types, when the components of variant types are to be manipulated by
external code without knowing what type it is in a particular instance.
Let's say we are designing a text editor. Each window has a pipeline
of transformers which maps on the fly the raw buffer contents
into the text to be displayed in the window. Transformers do syntax
highlighting, display control characters and tabs, translate character
sets, highlight regions, fold long lines, map color descriptions like
"a comment" into actual color values etc.
Some of the transformers maintain a state down through the buffer.
E.g. syntax highlighting of a line depends on whether a comment
started a few lines above. Most transformers are stateless however. The
problem is how to efficiently have always up-to-date transformed window
contents. We don't want to begin scanning syntax from the beginning
of the buffer at each buffer operation. Sometimes we have to replace
a transformer with a different one, e.g. when the highlighted region
changes - then all the later transformers need to be called again,
because they will operate on the completely changed text. But they
need to recalculate everything from the beginning of the buffer only
when they do have a state through the buffer.
My idea for a type of a single stateful transformer is (in Haskell
with the extension of existentially qualified types):
data Transformer = forall state. Eq state => Transformer
(state -> [Tokens] -> (state, [Tokens]))
state -- Initial state.
That is, for some type of its state it provides a function transforming
a single line, yielding also a state for the next line. ([Tokens]
are ordinary characters or special sequences which can encode various
formatting, not important here.) A transformer will transform only
one line at a time and must explicitly encode a state, because it
will be called for various lines in arbitrary order and the states
will be compared to check whether it needs to be called again when
something changes.
A window maintains a cache of states of each transformer at
the beginning of each line, so they may be restarted from any
position. When the buffer contents change, the transformers are
checked whether they produce the same state for the line following
the changed place as before the change. If so, they will not need to
be called again for the following lines.
How to do it without existentials? Every transformer would have
to represent its state in a fixed type, probably a String, to be
compared with a previous version by the controlling code and parsed
again by that transformer for the next line. Parsing and unparsing
is unnecessary with existentials: the state is an arbitrary type
with equality, fixed for a transformer, but different for different
transformers.
> > class State a where
> > value :: a-> Int
>
> > data STREAM = (State a) => Stream a (a -> a)
>
> Ok, so fine, but cant I instead of the above
> define a STREAM as (for example)
>
> > type STREAM = (STREAM, Int)
A recursive type synonym? This declaration is invalid, but can be
fixed by using a datatype.
> > makeSTREAM :: (State a) => a -> (a->a) -> STREAM
> > makeSTREAM start next = (makeSTREAM (next start) next, value start)
Right, in this case it can be done without existentials, because the
result is isomorphic to infinite [Int], so various types can be hidden
inside the computation producing an Int. It's not the best example.
That is what I meant by "when the components of variant types are to
be manipulated by external code without knowing what type it is in
a particular instance" in the first sentence. Here the manipulation
is trivial: the value of unknown type is always passed to the second
function and nothing else is done with it, so it may be hidden inside
the result of the function being also applied to `value', which has
then a known type. In my example it is not so trivial: the states
are stored in some lists, compared to one another and passed to a
function together with a different line contents than the previous
time, so it is not sufficient to package the state in the result of
the function (of a known type). A transformer is not isomorphic to
a list of lines, because it can be restarted in the middle with a
different line contents but the same state.
--
__("< Marcin Kowalczyk * [EMAIL PROTECTED] http://qrczak.ids.net.pl/
\__/ GCS/M d- s+:-- a22 C+++>+++$ UL++>++++$ P+++ L++>++++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP->+ t
QRCZAK 5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-
