:::warning
Announcements
- Help hours 3:45-5:15pm L037
- Quiz 2 Monday
- Progress reports sent out
- [Mid-semester survey: by tomorrow]()
- A6 reminder: try problems 1-4 by Sunday
:::

:::success
Agenda for today
- Thunks cont.
- Infinite sequences:
- motivation
- initial attempt
- Streams
:::

## Thunks

Recall from last time, let's edit `dbg_if` to use thunks in its signature, so that we don't evaluate both arguments before the body:

let dbg_if (c : bool) (t : unit -> 'a) (e : unit -> 'a) : 'a =

let dbg_if (c : bool) (t : unit -> 'a) (e : unit -> 'a) : 'a =
  print_endline (string_of_bool c);
  match c with
  | true -> t ()
  | false -> e ()

If the thunk is pure and there is no mutation, then when the body executes only affects performance + termination

With mutation and side effects, when things evaluate may affect the result!

More thunk examples:

(* Happens immediately *)
let f1 = print_endline "hello"
(* Does not happen immediately! Not until it is applied. *)
let f2 () = print_endline "hello"

(* We can apply the same thunk multiple times *)
let rec n_times_thunk f n = 
  if n <= 0 then "done"
  else (f () ; n_times_thunk f (n - 1)) ;;

let thunk_bad () = 1 / 0
(* thunk_bad is a function! Body will not have been evaluated *)

(* result stores the actual result of the body, but in this case *)
let result = thunk_bad ()

## Thunks and Performance

Delaying computation can help, hurt, or not change performance

- Help: if you never end up needing the result!
- Hurt: if you need the result more than once
- No change: if you need the result exactly once

It can be hard to predict how many times you will need a result!

We can use thunks to build other useful data structures.

# Infinite sequence motivation

Often want abstraction of infinite sequence of values (all natural numbers, data from a network, clicks from a user interface, ...).

We'll want do define these recursively. Consider defining an unbounded sequence of all 1s.
Just like we can have recursive functions, we can also have recursive lists, so let's try that first:[^1]

[^1]: Examples from [OCaml Programming: Correct + Efficient + Beautiful](https://cs3110.github.io/textbook).

let rec ones = 1 :: ones

We get:

val ones : int list = [1; <cycle>]

We could also have a pattern of alternating zeros and ones:

let rec a = 0 :: b and b = 1 :: a

val a : int list = [0; 1; <cycle>]
val b : int list = [1; 0; <cycle>]

Because these list definition define infinite, unbounded lists, the `utop` cannot print the entire list. But, because in memory we have a finite representation (since `cons` lists are fundamentally linked-lists, which can have cycles), we *can* still define lists like this.

Notably, these two prior examples are just repeating patterns. What if we want a stream that actually changes in more complex ways over time?

Let's try defining a list of each successive interger from some `n`:

(* the infinite list [n; n+1; n+2; ... ] *)
let rec from n = n :: from (n + 1)

When we try to use this to define the natural numbers, we get:

(* We want: [0; 1; 2; ... ] *)
let nats = from 0

What do we think will happen here?

Stack overflow during evaluation (looping recursion?).

This doesn't work! We don't have a cycle in the `cons` linked-list: we are trying to have an infinite list. There is no way to represent this in memory, so even trying to build it overflows the stack.

This is why we need thunks! We will use thunks to delay evaluation in a clever way, such that we can actually represent infinite lists even without cycles.

# Streams: an infinite sequence implementation

The core idea of a stream is to use a thunk to help us represent “the rest of the stream”.
These represent infinite lists, but with finite in-memory representations.

Note that while infinite lists/streams are a common programming concept, the language is less standardized than other things we've covered. For example, the OCaml textbook calls the same concept "sequences", not "streams", and uses a slightly different implementation. But the core idea is the same.

A stream is a sequence of data elements that are made available over time.

To define a stream, you need to know how to get the next item in the sequence, but you don’t need to be able to enumerate all items.

The *producer* and *consumer* collaborate, sort of like a 2 player game
- Producer knows how to create all values
- Consumer decides how many values to ask for

We will define a stream as a thunk that returns a pair containing:
- The “head of the stream” at that point
- A stream of the rest of the values

(* For CS251, we'll describe streams this way. Compared 
to other types we've seen, streams have less of a standard 
definition: people define them differently depending on the 
context.*)
type 'a stream = Stream of (unit -> 'a * 'a stream)

(* For example, the textbook uses a Cons-based definition *)

## Implementing streams

A stream is a thunk that returns a pair:
- `fst` is the “head of the stream” at that point
- `snd` is a stream of the rest of the values

Producer must be prepared to generate any number of elements!
- But how? Recursion, of course!
- The key “gotcha” is to thunk in just the right place

## Our first streams: ones and the natural numbers

(* "give me ones forever", but with our new stream type *)
let rec ones = Stream (fun () -> (1, ones))

(* more complex structure for non-repeating streams *)
let nats =
  (* Helper produces the pair *)
  let rec helper start =
    (start, Stream (fun () -> helper (start + 1)))
  in
  (* Call the helper with our actual initial value *)
  Stream (fun () -> helper 0)

This now works without a stack overflow!

val ones : int stream = Stream <fun>
val nats : int stream = Stream <fun>

## Using streams

We can *consume* the values from the start of the stream. For example, we can get just the first element/head with:

utop # let head = 
match ones with 
| Stream t -> fst (t ()) ;;
val head : int = 1

Or the let-match version:

utop # let Stream t = nats in fst (t ()) ;;
- : int = 0

We can also write a function to take the first `n` values of a stream.

(* 
A function that takes the first n elements of a stream 
s, returning them as a list in the same order. *)
let rec take n s = 
  if n = 0 then []
  else
    match s with
    | Stream t ->
      let (head, rest) = t () in
      head :: take (n-1) rest
      
      
(* We could also write this as this, using 
pattern matching in the argument itself *)
let rec take n (Stream t) = 
  if n = 0 then []
  else
    let (head, rest) = t () in
    head :: take (n-1) rest

# Group exercises

(* Write a function "take_under_10" that takes a stream of integers
and produces a list of numbers as long as the numbers are less than 10 *)

let rec take_under_10 (Stream s) =
  let (x, xs) = s () in
  if x < 10 then x :: take_under_10 xs
  else []

(* Write a stream for the powers of two *)
let powers_of_two =
  let rec go start = (start, 
      Stream (fun () -> go (2 * start))) in
  Stream (fun () -> go 1)