Homework 10 - Fall 2021

Principles of Programming Languages — Homework 10

Due by class time Tuesday, October 26

Reading

Review the code examples from class this week.

Tester Program

To use the auto-tester program for this assignment, download the files hw10-tester.scm and auto-tester.scm and put them in the same folder as your Scheme file. Then put (require "hw10-tester.scm") at the top of your Scheme file. To test a function individually, type (test: function_name) at the DrRacket prompt. To see the details of a particular test case, type (test: function_name case_number). Or just type (test:) to test all of your functions at once.

Exercises

In class, we wrote the function all?, which takes a one-argument predicate function pred? and a list ls, and returns true if all of the elements of ls satisfy the predicate. (A predicate function is just a function that always returns either true or false.) Write a similar function (any? pred? ls) that returns true if at least one of the elements of ls satisfies the predicate, or false otherwise. For example:
```
(any? (lambda (x) (even? x)) '(1 3 5 6 7))  → #t
(any? (lambda (x) (even? x)) '(1 3 5))  → #f
(any? (lambda (x) (symbol? x)) '(2 b or not 2 b))  → #t
(any? (lambda (x) (number? x)) '(a b c d e))  → #f
```

Write a function (filter pred? ls) that takes a one-argument predicate function and a list and returns a new list containing just those elements that satisfy the predicate. For example:

(filter (lambda (x) (even? x)) '(1 2 3 4 5 6 7 8))  → (2 4 6 8)
(filter (lambda (x) (odd? x)) '(1 2 3 4 5 6 7 8))  → (1 3 5 7)
(filter (lambda (x) (symbol? x)) '(a 1 and a 2 and a 3))  → (a and a and a)
(filter (lambda (x) (not (symbol? x))) '(a 1 and a 2 and a 3))  → (1 2 3)

Complete the definition of times-all in terms of map, by filling in the blank below. This function takes a number n and a list of numbers nums and multiplies each number in the list by n, returning a new list of the results. You do not need to write map itself, since it already exists in Scheme.
```
(define times-all
  (lambda (n nums)
    (map (lambda (x) ______ ) nums)))

(times-all 10 '(1 2 3 4 5))  → (10 20 30 40 50)
(times-all 0 '(9 9 9))  → (0 0 0)
(times-all 2 '(25))  → (50)
```

Complete the definition of pair-up in terms of map, by filling in the blank below. This function pairs element with each item in ls and returns a list of the pairs, as shown below.

(define pair-up
  (lambda (element ls)
    (map (lambda (x) ______ ) ls)))

(pair-up 'apple '(1 2 3 4))  → ((apple 1) (apple 2) (apple 3) (apple 4))
(pair-up 0 '(zero))  → ((0 zero))
(pair-up 'hi '(ho ho ho))  → ((hi ho) (hi ho) (hi ho))

Complete the definition of prefix in terms of map, by filling in the blank below. This function takes an element and a list of lists, and returns a new list with the element added to the front of each inner list, as shown below.

(define prefix
  (lambda (element ls)
    (map (lambda (x) ______ ) ls)))

(prefix 0 '((0 0) (0 1) (1 0) (1 1)))  → ((0 0 0) (0 0 1) (0 1 0) (0 1 1))
(prefix 1 '((0 0) (0 1) (1 0) (1 1)))  → ((1 0 0) (1 0 1) (1 1 0) (1 1 1))
(prefix 'a '((one) (two) (three)))  → ((a one) (a two) (a three))

Complete the definition of swap in terms of map, by filling in the blank below. This function swaps all occurrences of sym1 and sym2 within a list of symbols ls. Hint: use a cond inside the lambda expression.

(define swap
  (lambda (sym1 sym2 ls)
    (map (lambda (s) ______ ) ls)))

(swap 'red 'blue '(red fish blue fish red fish))  → (blue fish red fish blue fish)
(swap 'o 'i '(l o l l i p o p))  → (l i l l o p i p)
(swap 'spam 'ham '(green eggs and ham))  → (green eggs and spam)

A rectangular matrix of elements can be represented as a list of lists, where each inner list is one row of the matrix. For example: ((1 2) (3 4)) would be a 2 × 2 matrix, and ((1 2 3) (4 5 6) (7 8 9)) would be a 3 × 3 matrix. Complete the definition of matrix-map in terms of map, by filling in the blank below. This function takes a one-argument function f and a matrix as input, and returns a new matrix consisting of f applied to the elements of matrix.
```
(define matrix-map
  (lambda (f matrix)
    (map (lambda (x) _____ ) matrix)))

(matrix-map (lambda (n) (* n n)) '((1 2) (3 4)))  → ((1 4) (9 16))
(matrix-map (lambda (n) (+ n 1)) '((1 2 3) (4 5 6) (7 8 9)))  → ((2 3 4) (5 6 7) (8 9 10))
(matrix-map (lambda (n) (- n)) '((10 20) (30 40) (50 60) (70 80)))  → ((-10 -20) (-30 -40) (-50 -60) (-70 -80))
```
Write the function (binary n), which generates a list of all binary patterns of length n, in proper counting order. To generate all patterns of length n, first recursively generate all shorter patterns of length n-1, and then add a 0 to the front of each shorter pattern (hint: see prefix). In the same way, add a 1 to the front of each shorter pattern, and then combine the results. There is exactly one binary pattern of length 0, namely (), so binary should return this pattern in a list by itself when n is 0.
```
(binary 2)  → ((0 0) (0 1) (1 0) (1 1))
(binary 3)  → ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))
(binary 0)  → (())
```

Turning in Your Homework

Save all of your function definitions in a single Scheme file called assign10.scm and submit it using the Homework Upload Site. Make sure to include your name and the assignment number in a comment at the top of your file.
If you have questions about anything, don't hesitate to ask!