I blew it! My example had a bad flaw. See below.
Date: Mon, 22 Feb 93 19:30:19 GMT
From: wadler <[EMAIL PROTECTED]>
Guy,
I agree that the report should be updated to express the restriction we
really have in mind. Simon: as editor, this is your bailiwick!
I also think its neat that you seem to have found a use for cyclic
unification. This is definitely an impetus to extend the language to
include cyclic types. (I don't expect we'll do this for a while
though. You might consider modifying the Glasgow Haskell compiler to
include this yourself -- it may not be too difficult.)
However, I am confused by some of your example. You want to use a data
structure like
data FooTree a = Leaf a | Node (FooTree (Wrapper a)) (FooTree (Wrapper a))
data Wrapper a = Annotation a Int
This seems to add an additional level of annotation at every
Node. Something zero nodes deep has zero annotations, something
five nodes deep has five annotations. Is this really what you
want?
Yes. I want to annotate every non-root item of the tree.
Again, this is only a stripped-down example of what I'm
really trying to do.
Because of the way type inference works in the Hindley-Milner system,
it is impossible to write a function that will act on values of the
type (FooTree a) as defined above.
Ooops! My example has a bug in it. What I meant to say was
data FooTree a = Leaf a | Node (Wrapper (FooTree a)) (Wrapper (FooTree a))
data Wrapper a = Annotation a Int
and so I want to be polymorphic over various tree types such as
data FooTree a = Leaf a | Node (Wrapper1 (FooTree a))
(Wrapper1 (FooTree a))
data FooTree a = Leaf a | Node (Wrapper2 (FooTree a))
(Wrapper2 (FooTree a))
data FooTree a = Leaf a | Node (Wrapper1 (Wrapper2 (FooTree a)))
(Wrapper1 (Wrapper2 (FooTree a)))
data FooTree a = Leaf a | Node (Wrapper3 (Wrapper2 (FooTree a)))
(Wrapper3 (Wrapper2 (FooTree a)))
and so on. Roughly, think of the type of "f" typically looking like
f :: WrapperA (WrapperB (... (WrapperZ (FooTree a)) ...)) -> FooTree a
and there are a whole bunch of different "f" functions of different types,
each intended to operate on trees with different sets of annotations.
I want treewalk to look very roughly like
treewalk f (Leaf x) = hackleaf x
treewalk f (Node p q) = hacknode (f p) (f q)
(actually it's much more complicated because f needs to process
annotations as well as extracting the subnode of type FooTree).
Many apologies for giving you a confusingly wrong example!
Thanks for taking me seriously.
--Guy
