(a) Recall that a lazy list is a useful structure for representing a long or even infinite list. A lazy list is represented in Racket with a cons cell, where the "car" contains a data item and the "cdr" contains a function which returns the rest of the lazy list. If the function returns #f, the list is empty. Write the following functions that create and manipulate lazy lists:
(b) A wide variety of techniques have been devised to compute prime numbers (numbers evenly divisible only by themselves and 1). One of the oldest techniques is the "Sieve of Eratosthenes." This technique is remarkably simple.
You start with the infinite list L = 2, 3, 4, 5, .... The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7, 9, .... The head of this list (3) is a prime. Moreover, if you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, .... Repeating the process, you repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples of the head value.
You are to write an function (primes) that computes a lazy list containing all prime numbers, starting at 2, using the "Sieve of Eratosthenes." To test your function, evaluate (first-n (primes) 10). You should get (2 3 5 7 11 13 17 19 23 29). Try (nth (primes) 20). You should get 71.
(Possibly useless hint: Create a recursive function (sieve lazy-list) that "sieves" the first item from the rest, returning a new lazy list. It uses filter-multiples, but adds an additional recursive operation.)
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called sieve.rkt.