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