3.11 Laziness and Infinite Data
Develop the following functions and data structures in the Lazy Racket language.
3.11.1 A note on testing
(define print-only-errors #t) (define (test l r) (if (equal? l r) (if print-only-errors () (printf "Test Passed~n")) (printf "Test Failed.~nActual: ~S ~nExpected: ~S~n" l r)))
(test (take-while odd? (list 1 3 4)) (list 1 3))
3.11.2 Utility Functions
For example, (take-while (lambda (n) (< n 5)) (list 1 2 3 4 5 1 2)) returns (list 1 2 3 4).
procedure
(build-infinite-list f) → (listof any/c)
f : (exact-nonnegative-integer? . -> . any/c)
3.11.3 Primes
procedure
n : exact-positive-integer?
value
You may find filter, prime?, and build-infinite-list useful.
procedure
(prime?/fast n) → boolean
n : exact-positive-integer?
value
3.11.4 Longest Common Subsequence
procedure
(build-table rows cols f) → (vectorof (vectorof any/c))
rows : exact-positive-integer? cols : exact-positive-integer? f : (exact-nonnegative-integer? exact-nonnegative-integer? . -> . any/c)
You will find the following function helpful:
(define (build-vector num f) (apply vector (build-list num f)))
procedure
(lcs-length s1 s2) → exact-nonnegative-integer?
s1 : string? s2 : string?
You must use build-table to construct a table of the answer for sub-problem made from prefixes of s1 and s2 then synthesize the result from these intermediate points. You will not get credit if you do a computation twice.
You may find string-ref, char=?, apply, and max useful.
Warning: Many people errorneously implement the longest common substring. The longest common substring of Artist and Artsy is Art. The longest common subsequence of Artist and Artsy is Arts. You are implementing longest common subsequence.