Lab 06 - Exercise 6, Infinite List

Exercise 6 Review

1

get()

get() is the soul of Lazy! See more example from Main methods explanation from Exercise 6. Remember that get() is expensive!

2

equals()

In Lazy::equals evaluate both Lazy first before comparing them.

3

map()

Whenever you implement the map, flatMap, filter, combine, take note that the get() is expensive!

Wrong

public <U> Lazy<U> map(Transformer<? super T, ? extends U> f) {
    U result = f.transform(this.get());
    return Lazy.of(() -> result);
}
// No Longer Lazy because this.get() is expensive

Correct

Similarly, you can do the same thing on the flatMap, filter and combine. See more from Main methods explanation from Exercise 6.

Keys of being lazy

Core idea: Delay the evaluation as much as possible.

• Don’t invoke produce() anywhere other than when get() is called.

• Produce the value only once and cache it immediately. Subsequent calls of get() use the cached value directly.

• Don’t invoke get() directly. Compose the functions into a new Producer in map, flatMap, filter, combine and so on.

Infinite List

Motivation:

• In the natural world, many things are infinite.

• But computer data structure can only hold a finite number of data points.

• A need arises: How to efficiently represent an infinite set of values using a finite structure?

• Idea: It is relatively easy to capture the structure of an infinite set if its elements follow a certain pattern.

• We can produce the “next” element based on all previously evaluated elements.

Mathematical Context

The last sentence can be achieved by using recurrence relation.

A recurrance relation on a set $X$ is defined by $k$ initial terms $x_0,x_1,\cdots,x_{k-1}$ and a function $f:X^k\rightarrow X$ such that $f(x_i,x_{i+1},\cdots,x_{i+k-1})=x_{i+k}$.

List Creation

Use the above idea of recurrance relation, we can rewrite the Infinite list as$[\text{head}, \text{successive mapping}]$. This is the one of the key ideas in the Infinite List.

So, the basic field of our Infinite List will be

class InfiniteList<T> {
    private Producer<T> head; // A[k]
    private Producer<InfiniteList<T>> tail; // A[k + 1...]
}