Instructions

1. This is questions from several tests, so don’t panic about the length.

2. The real quiz is individual, so do this one on your own.

3. This practice quiz is open book. You can use

   1. The local mirror of A Functional Introduction Computer Science (FICS), linked from multiple labs or directly from

      https://www.cs.unb.ca/~bremner/teaching/cs2613/books/FICS/

   2. The local Racket documentation (run raco docs, or the drracket help menu).

   3. Other parts of the course web site

   4. Your own notes and work from previous labs and assignments.

Questions

Write a function steamroller that returns a list of the numbers, symbols and strings in a given list in order. In particular your function should pass the following tests.

(check-expect (steamroller empty) empty)
(check-expect (steamroller '(() ())) empty)
(check-expect (steamroller '((a) (b))) '(a b))
(check-expect (steamroller '(((a 1) (b 1)) ((c 2) (d 2) )))
              '(a 1 b 1 c 2 d 2))

Notice the behaviour in the last test is to completely flatten the list. Start with the following template for structural recursion on lists

(define (steamroller lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (steamroller (rest lst)) ...]))

Good solution

To get 7 marks (roughly a “B”), your solution must

• Pass the tests above.
• Be reasonably indented and use reasonable variable names.
• Have full test coverage.
• Use language “htdp/isl+” (Intermediate Student with lambda)
• Only use builtins from the following list
  • define, cond, if
  • list?, empty?, cons?
  • first, rest, empty, cons, list
  • foldr
  • append (but only for this part, not the next).

Full marks

For full marks

• Satisfy the conditions above, and
• Do not use the builtin function append (you may write your own function that does the same thing if you want).
• Add at least two good tests and explain what you are testing.

Merge sorted lists

Write a function merge-nums that merges two sorted lists of numbers. In particular your function should pass the following tests.

(check-expect (merge-nums '(1 3 5) '(2 4)) '(1 2 3 4 5))
(check-expect (merge-nums '(1 2 3) '(1 3 5)) '(1 1 2 3 3 5))

(check-expect (merge-nums '(2 4) '(1 3 5)) '(1 2 3 4 5))
(check-expect (merge-nums '(1 3 5) '(1 2 3)) '(1 1 2 3 3 5))

Good solution

To get 7 marks (roughly a “B”), your solution must

• Pass the tests above, and have full test coverage.

• Be reasonably indented and use reasonable variable names.

• Use language “htdp/isl+” (Intermediate Student with lambda)

• Only use builtins from the following list: cond, cons, cons?, define, else, empty?, first, if, rest, string<=?, <= .

Full marks

For full marks, satisfy the conditions above, and

• Write a function merge-with passing the following tests

(define (merge-strings lst1 lst2)
  (merge-with string<=? lst1 lst2))

(check-expect (merge-strings '("a" "goodbye" "hello") '("b" "c" "hello"))
              '("a" "b" "c" "goodbye" "hello" "hello"))

(check-expect (merge-strings '("absolve" "absolved")
                             '("aardvark" "bogey" "bogeyed"))
              '("aardvark" "absolve" "absolved" "bogey" "bogeyed"))

• Your merge-nums function should be a single call to merge-with (see the definition of merge-strings).
• Add at least one good test and explain what you are testing.

Matrix

Write a Racket function colsum that, given a matrix of numbers represented as a list of rows, outputs a list containing the sums of the columns of the matrix. For full marks, your solution must

• use the language “Intermediate Student with Lambda”, or #lang htdp/isl+,
• work for any matrix with at least one row and one column,
• have reasonable coding style, including indentation and naming,
• pass the following tests, and
• have complete coverage.
• use functional abstraction (like assignment 2) rather than explicit recursion

(check-expect (colsum '((1))) '(1))
(check-expect (colsum '((1 2))) '(1 2))
(check-expect (colsum '((1 2) (3 4))) '(4 6))
(check-expect (colsum '((1 2) (3 4) (5 6))) '(9 12))
(check-expect (colsum '((1 2 3) (4 5 6))) '(5 7 9))

(define size 17)
(check-expect (colsum
               (build-list size (lambda (j)
                                  (list j (+ j size) (+ j size size)))))
              '(136 425 714))