Haskell equivalent of -rectypes

Question

What is the GHC equivalent of OCaml's -rectypes for allowing recursive types? I don't see one in the documentation. Is it a hidden feature?

Answer 1

There isn't one unfortunately, all recursion must go through a data type. However, if you're willing to put up with a bit of headache you can still write recursive types pretty easily.

 newtype RecArr b a = RecArr {unArr :: RecArr b a -> b}

 unfold = unArr
 fold   = RecArr

Now we can fold and unfold our RecArr to unfold our recursion to our hearts content. This is a little painful because it's manual, but completely workable. As a demonstration, here's the y combinator written using fold and unfold.

 y f = (\x -> f (unfold x x)) $ fold (\x -> f (unfold x x))

 factorial f n = if n == 0 then 1 else n * f (n-1)

 main = print (y factorial 5) -- prints 120

Answer 2

There is none. All recursion has to go through nominal types. That is, you have to define a data type.