Negatively recursive data types
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?