Lazy Evaluation

Prev: Some Familiar Data Structures in a Functional Setting Next: Fundamentals of Amortization

Prev: Some Familiar Data Structures in a Functional Setting Next: Fundamentals of Amortization

4.1 $-Notation

Exercises

Exercise 4.1

Use the fact that force ($e) is equivalent to e to show that these two definitions of drop are equivalent.

4.2 Streams

Exercises

Exercise 4.2

Implement insertion sort on streams. Show that extracting the first $k$ elements of sort xs takes only $O(n\cdot k)$ time, where $n$ is the length of xs, rather than $O(n^2)$ time, as might be expected of insertion sort.

4.3 Chapter Notes