ocaml - Infinite Lists / Streams in ReScript

Question

I can't seem to find the correct typing for an infinite list in ReScript.

I first tried:

type rec stream<'a> = ('a, () => ('a, stream<'a>))

Which was incorrect because ReScript thought the type was cyclic. So instead I tried:

type rec stream<'a> = ('a, Lazy.t<() => ('a, stream<'a>)>)

Which still gave me a type error.

Ultimately I am trying to get this piece of code to work but it fails due to the type signature being infinite.

let rec from: (int, Lazy.t<() => (int, Lazy.t<...>) = (x: int) => {
    (x, () => Lazy.from_fun(from(x+1)))
}

Answer 1

If your only objection to Sequence is the Nil case, you can define

type rec stream<'a> = { x:'a, next:() => stream<'a> }

The difference with your definition is that we are creating a new recursive type, rather than trying to define a recursive type expression.

EDIT:

The difference between using a tuple or a record is that tuples are structurally typed whereas records are nominally typed.

This changes everything in term of equality and identity.

In particular the original definition can be read as

type stream0<'a> = ('a, () => 'b ) as 'b

Then whenever one wants to compare a type stream0<'a> with a tuple type, it might be needed to expand this abbreviation an unbounded number of time.

For instance, this function is well-typed.

let f: stream0<int> => (int, ()=>(int,() => _)) = (x) => x

or this one:

let app_once = ((x,next)) => next ()

One important consequence here is that it is possible to use a stream0<'a> in a context where a finite stream was expected. In other words, there are many have many potential equality between a stream0<'a> and a finite version of stream0<'a>.

Contrarily, the record definition of stream<'a> create a new and distinct type constructor stream. Consequently, a stream<'a> can only ever be equal to stream<'a>. In other words, a function designed for a stream<'a>

let app_once  = {x;next} => next(())

cannot work with the type

type one_stream<'a> = { x:'a, next:() => ('a, ()) }

In practice, the recursive type of stream0<'a> and its many type equalities is more bothersome than useful, and such recursive types are disabled by default.