►Organization of Programming Languages (Fall 2016)
▼3 Assignments
►3.15 Laziness and Infinite Data
On this page:
3.15.1 A note on testing
3.15.2 Utility Functions
take-while
build-infinite-list
3.15.3 Primes
prime?
primes
prime?/  fast
primes/  fast
3.15.4 Longest Common Subsequence
build-table
lcs-length
    ← prev  up  next → 

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

procedure

(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).

procedure

(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

procedure

(prime? n) → boolean?

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

value

primes : (listof exact-positive-integer?)

The list of all primes.

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

procedure

(prime?/fast n) → boolean

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

value

primes/fast : (listof exact-positive-integer?)

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

3.15.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)
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)))

procedure

(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.

    ← prev  up  next →