# Negatively recursive data types

**Keith Wansbrough
**
Keith.Wansbrough@cl.cam.ac.uk

*Wed, 04 Jul 2001 18:27:05 +0100*

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:
data Neg a b = MkNeg (a -> Neg a b -> b)
Here (Neg a b) occurs to the left of the function arrow. Some members
of this data type might be:
n1, n2 :: Neg Int [Int]
n1 = MkNeg (\ x _ -> [x])
n2 = MkNeg (\ x (MkNeg f) -> x : f (x+1) n1)
This example is not a very good one. Does anyone have an example of a
useful data type involving negative recursion?
Thanks.
--KW 8-)