what does Cons do in this function?

Question

I'm confused as to what the Cons() function does, in the function definition for from.

Answer 1

What Stream represents is a lazy and potentially infinite list. Since SML is eager, this needs to be done in a slightly roundabout way.

Let's first look at how ordinary lists work:

datatype 'a list = [] | :: of 'a * 'a list

The cons consists of two parts:

• The first element in the list
• The rest of the list

In the lazy list, it's pretty similar.

datatype 'a Stream = Nil | Cons of 'a * (unit -> 'a Stream) 

Here the cons consists of the following:

• The first element in the list
• A function that produces the rest of the list when evaluated on ()

So, you can see that the principle is much the same, albeit a tad more difficult to work with.

Let's look at an example list:

fun succ n = Cons (n, fn () => succ (n+1))
val naturals = succ 0

What does this produce? Let's examine it.

naturals was defined to be succ 0, which in turn is defined to be Cons(0, fn () => succ 1). From this we can see that the first element in the list is 0.

Now let us go one step further. We evaluate fn () => succ 1, the second part of our Cons, on (), which produces succ 1, which in turn is Cons(1, fn () => succ 2). Now we can see that the second element in the list is 1.

If we repeat this process, we get that the list represents the infinite list [0, 1, 2, ...].

You can also see this by trying to do

val firstnats = take 10 naturals;

and seeing what you get.