Are Infinite Types (aka Recursive Types) not possible in F#?

Question

I was chatting with Sadek Drobi on twitter when be brought up that F# didn't seem to support Infinite Types. It turns out that in C# you can do something along these lines:

delegate RecDelegate<T> RecDelegate<T>(T x);

However, after some experimentation on both our parts, we determined that the same in F# seems impossible both implicit and explicitly.

Explicit:

type 'a specialF = 'a->specialF<'a>

error FS0191: This type definition involves an immediate cyclic reference through an abbreviation, struct field or inheritance relation.

Implicit:

let rec specialF (x: 'a) = specialF

Type mismatch. Expecting a 'b but given a 'a -> 'b. The resulting type would be infinite when unifying ''b' and ''a -> 'b'.

Of course, these are intentionally simple samples.

I was wondering if I am somehow mistaken. Perhaps I missed some type of necessary annotation?

Answer 1

type d<'T> = delegate of 'T -> d<'T>  //'
let del : d<int> = null
let anotherDel = del.Invoke(1).Invoke(2).Invoke(3)

I think you need a named type that is representable directly in CLI to break the recursion, so in F# this means you need an actual delegate type as well.

Answer 2

You can also do something like

type 'a RecType = RecType of ('a -> 'a RecType)

to create a named type through which to perform the recursion. Now this works:

let rec specialF = RecType (fun _ -> specialF)

Answer 3

Recursive record types should work as well.

type A = { A : A }
let rec a : A = { A = a }

I'd be interested in a practical application. Or even an impractical one :)