Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

what does Cons do in this function?

Tags:

sml

lazylist

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

enter image description here

like image 896
jfisk Avatar asked Feb 12 '12 05:02

jfisk


2 Answers

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.

like image 152
Sebastian Paaske Tørholm Avatar answered Sep 20 '22 10:09

Sebastian Paaske Tørholm


It's one of Stream's two constructors. See the second line of that screenshot -- that's all there is to Cons.

like image 23
Julian Fondren Avatar answered Sep 22 '22 10:09

Julian Fondren