On this page:
3.15.1 A note on testing
3.15.2 Utility Functions
3.15.3 Primes
prime?/  fast
primes/  fast
3.15.4 Longest Common Subsequence

3.15 Laziness and Infinite Data

Develop the following functions and data structures in the Lazy Racket language.

3.15.1 A note on testing

There is no testing facility built in to the Lazy Racket language. So, you should add one for your file:
(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)))
For example,
(test (take-while odd? (list 1 3 4))
      (list 1 3))

3.15.2 Utility Functions


(take-while p l)  (listof any/c)

  p : (any/c . -> . boolean?)
  l : (listof any/c)
Returns the prefix of l such that for all elements p returns true. This is not filter.

For example, (take-while (lambda (n) (< n 5)) (list 1 2 3 4 5 1 2)) returns (list 1 2 3 4).


(build-infinite-list f)  (listof any/c)

  f : (exact-nonnegative-integer? . -> . any/c)
Lazily constructs the infinite list such that (list-ref (build-infinite-list f) i) returns (f i).

3.15.3 Primes


(prime? n)  boolean?

  n : exact-positive-integer?
Returns true if n is prime.

The list of all primes.

You may find filter, prime?, and build-infinite-list useful.


(prime?/fast n)  boolean

  n : exact-positive-integer?
Returns true if n is prime, but tests only prime factors from primes/fast.

The list of all primes constructed with prime?/fast.

3.15.4 Longest Common Subsequence

Lazily constructs a vector such that (vector-ref (vector-ref (build-table rows cols f) i) j) equals (f i j), when (< i rows) (< j cols).

You will find the following function helpful:

(define (build-vector num f)
  (apply vector (build-list num f)))


(lcs-length s1 s2)  exact-nonnegative-integer?

  s1 : string?
  s2 : string?
Computes the length of the longest common subsequence of two strings s1 and s2.

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.