Negatively recursive data types
Wed, 04 Jul 2001 21:43:06 +0100
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 ;-)
Dept. of Computer Science, University of York, York YO10 5DD, UK.
Tel: +44 1904 434756; Fax: +44 1904 432767