Negatively recursive data types

Olaf Chitil
Wed, 04 Jul 2001 21:43:06 +0100

Lars Henrik Mathiesen wrote:
> > From: Keith Wansbrough <>
> >
> > 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