Negatively recursive data types

Keith Wansbrough
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?


--KW 8-)