# Streams

A *stream* is an infinite list. Sometimes these are also called sequences, delayed lists,
or lazy lists. We can try to define a stream by analogy to how we can define (finite)
lists. Recall that definition:

```
type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
```

We could try to convert that into a definition for streams:

```
(* doesn't actually work *)
type 'a stream =
| Cons of 'a * 'a stream
```

Note that we got rid of the `Nil`

constructor, because the empty list is finite,
but we want only infinite lists.

The problem with that definition is that it's really no better than the built-in
list in OCaml, in that we still can't define `nats`

:

```
# let rec from n = Cons (n, from (n+1));;
# let nats = from 0;;
Stack overflow during evaluation (looping recursion?).
```

As before, that definition attempts to go off and compute the entire infinite sequence of naturals.

What we need is a way to *pause* evaluation, so that at any point in time,
only a finite approximation to the infinite sequence has been computed. Fortunately,
we already know how to do that!

Consider the following definitions:

```
# let f1 = failwith "oops";;
Exception: Failure "oops".
# let f2 = fun x -> failwith "oops";;
val f2 : 'a -> 'b = <fun>
# f2 ();;
Exception: Failure "oops".
```

The definition of `f1`

immediately raises an exception, whereas the definition of `f2`

does not. Why? Because `f2`

wraps the `failwith`

inside an anonymous function.
Recall that, according to the dynamic semantics of OCaml, **functions are already
values**. So no computation is done inside the body of the function until it is applied.
That's why `f2 ()`

raises an exception.

We can use this property of evaluation—that functions delay evaluation—to
our advantage in defining streams: let's wrap the tail of a stream inside a function.
Since it doesn't really matter what argument that function takes, we might as well
let it be unit. A function that is used just to delay computation, and in
particular one that takes unit as input, is called a *thunk*.

```
(* An ['a stream] is an infinite list of values of type ['a].
* AF: [Cons (x, f)] is the stream whose head is [x] and tail is [f()].
* RI: none.
*)
type 'a stream =
Cons of 'a * (unit -> 'a stream)
```

This definition turns out to work quite well. We can define `nats`

, at last:

```
# let rec from n = Cons (n, fun () -> from (n+1));;
val from : int -> int stream = <fun>
# let nats = from 0;;
val nats : int stream = Cons (0, <fun>)
```

We do not get an infinite loop or a stack overflow. The evaluation of `nats`

has
paused. Only the first element of it, `0`

, has been computed. The remaining elements
will not be computed until they are requested. To do that, we can define functions
to access parts of a stream, similarly to how we can access parts of a list:

```
(* [hd s] is the head of [s] *)
let hd (Cons (h, _)) = h
(* [tl s] is the tail of [s] *)
let tl (Cons (_, tf)) = tf ()
(* [take n s] is the list of the first [n] elements of [s] *)
let rec take n s =
if n=0 then []
else hd s :: take (n-1) (tl s)
(* [drop n s] is all but the first [n] elements of [s] *)
let rec drop n s =
if n = 0 then s
else drop (n-1) (tl s)
```

It is informative to observe the types of those functions:

```
val hd : 'a stream -> 'a
val tl : 'a stream -> 'a stream
val take : int -> 'a stream -> 'a list
val drop : int -> 'a stream -> 'a stream
```

Note how, in the definition of `tl`

, we must apply the function `tf`

to `()`

to obtain
the tail of the stream. That is, we must *force* the thunk to evaluate at that point,
rather than continue to delay its computation.

We can use `take`

to observe a finite prefix of a stream. For example:

```
# take 10 nats;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
```