Negatively recursive data types

[Olaf Chitil]

Lars Henrik Mathiesen wrote:
> 
> > From: Keith Wansbrough <Keith.Wansbrough@cl.cam.ac.uk>
> >
> > Hi... I'm currently looking at the semantics of recursive data types.
> > One thing that Haskell allows, but the semantics for it is very hairy,
> > is *negatively* recursive data types.  That is, data types where the
> > recursion occurs to the left of a function arrow.  For example:
> >
> > This example is not a very good one.  Does anyone have an example of a
> > useful data type involving negative recursion?

> > data Fix a = F (Fix a) -> a

You can find this and some related examples in

Erik Meijer and Graham Hutton. 
Bananas in space: Extending fold and unfold to exponential types. 
In Proceedings of the Seventh International Conference on Functional
Programming Languages and Computer Architecture (FPCA'95), pages
324-333. ACM Press, 1995.

The paper also discusses some hairy details of recursive data types ;-)

Olaf

-- 
OLAF CHITIL, 
 Dept. of Computer Science, University of York, York YO10 5DD, UK. 
 URL: http://www.cs.york.ac.uk/~olaf/
 Tel: +44 1904 434756; Fax: +44 1904 432767