How to define an infinite recursive object which is defined through discriminated union?

Question

Suppose I define this variant type

type Sequence = 
 | Seq of type-1 * Sequence

And let's suppose in Repl I want to some how encode the sequence using this, then how can I do it? For example, Suppose I want to encode the sequence (1,2,3,4,...) with the above.

Answer 1

There's a cool way to do this using lazy values:

type Sequence<'T> =
 | (::) of 'T * Lazy<Sequence<'T>>

You can define an infinite sequence of ones like this:

// 1, 1, 1, ...
let rec ones = 1 :: lazy ones

To get to the natural numbers, you'll also need addition:

type Sequence<'T when 'T : (static member (+) : 'T * 'T -> 'T)> =
 | (::) of 'T * Lazy<Sequence<'T>>
 static member inline (+)(seqF, seqG) =
 let rec loop (f : 'T :: fs) (g : 'T :: gs) =
 (f + g) :: lazy (loop fs.Value gs.Value)
 loop seqF seqG

Then the sequence of naturals is just:

// 1, 2, 3, ...
let rec naturals = ones + (0 :: lazy naturals)

This seems like magic, but it works because:

 1, 1, 1, 1, 1, 1, ...
 0, 1, 2, 3, 4, 5, ...
+-----------------------
 1, 2, 3, 4, 5, 6, ...

You can print out as many values as you want like this:

let take n seq =
 let rec loop n (f :: fs) =
 if n <= 0 then []
 else List.Cons(f, fs.Value |> loop (n-1))
 loop n seq
printfn "%A" <| take 10 naturals // [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

I wrote more about this here.

Answer 2

Given your definition cannot be usefully instantiated (you need the rest of the infinite sequence to create the first element[1]) that definition is not useful.

Something like:

type Sequence = 
 | Seq of type-1 * (Sequence option)

would avoid this problem.

However both type-1 list and type-1 seq have inbuilt language and library support and allow multiple approaches to instanctiation of instances (notably including Seq.initInfinite) either would be a better choice.

---

[1] A recursive approach starts looking OK, but there is no way to provide a base case...