Introduction to Functional Programming — Homework 8

Due by 11:59pm Wednesday, March 31

Reading

Programming Exercises

  1. In class this week, we wrote the function make-verifier, which creates predicate functions to test for specific types of self-verifying numbers, such as ISBN and credit card numbers. Money order ID numbers are also self-verifying. To check if a number is a valid money order ID, we simply add up all of the digits of the number, except for the digit in position 1 (the rightmost digit). Instead, for the rightmost digit, we add the negation of that digit. If the resulting sum is divisible by 9, the number is a valid money order ID.

    Use make-verifier to define the function valid-money-order? in the same way that we defined functions to test for valid ISBN, UPC, and credit card numbers. Then use your function to determine which of the following two numbers is a valid money order ID: 48077469777 or 48077462766.

  2. We also wrote a few other functions in class, including map-both and sum. Using map-both as a helper, define the function zip (from Lab 5), which takes two lists of equal length and returns a new list of lists with the corresponding elements paired up, as shown below: 

    (zip '() '())  =>  ()
(zip '(a) '(b))  =>  ((a b))
(zip '(one two) '(fish fish))  =>  ((one fish) (two fish))
(zip '(1 2 3 4) '(a b c d))  =>  ((1 a) (2 b) (3 c) (4 d))

  3. Using map-both and sum as helpers, define the function dot-product, which takes two lists of numbers of equal length as input, multiplies the numbers at corresponding positions in the lists together, and adds up the results. For example, to compute the dot-product of the lists (4 3 2 1) and (10 20 30 40), we would compute the value:

    (4 × 10) + (3 × 20) + (2 × 30) + (1 × 40)   =   40 + 60 + 60 + 40   =   200

    (dot-product '(4 3 2 1) '(10 20 30 40))  =>  200
(dot-product '(2 2 2) '(3 3 3))  =>  18
(dot-product '() '())  =>  0

  4. Write the function weird-sqrt, which takes a number n as input and returns its square root, except if n equals 0, in which case weird-sqrt should return the list (you have won a million dollars!). For example: 

    (weird-sqrt 25)  =>  5
(weird-sqrt 49)  =>  7
(weird-sqrt 0)  =>  (you have won a million dollars!)

  5. Write the function make-weird, which takes three values as input: a one-argument function called f, a value called special-input, and another value called special-output, and returns a new function that behaves exactly like the function f, except when given special-input as input, in which case it should return the value special-output. For example, we could use make-weird to define weird-sqrt as shown below: 

    (define weird-sqrt (make-weird sqrt 0 '(you have won a million dollars!))
(weird-sqrt 25)  =>  5
(weird-sqrt 0)  =>  (you have won a million dollars!)

(define weird-double (make-weird (lambda (x) (* 2 x)) 50 999))
(weird-double 3)  =>  6
(weird-double 10)  =>  20
(weird-double 50)  =>  999

(define weird-car (make-weird car '() 'oops))
(car '(1 2 3))  =>  1
(car '(y z)))  =>  y
(car '())  =>  oops

Optional Challenge Problems (Extra Credit)

  1. Write the function (compose-all list-of-functions), which takes a list of one-argument functions and returns a new one-argument function representing their composition. If the list is empty, the "do nothing" identity function (lambda (x) x) should be returned. Hint: use compose as a helper and think recursively. Examples:

    ((compose-all (list sqrt abs car)) '(-36 49 2)) => 6
((compose-all (list car cdr)) '(a b c d e f)) => b
((compose-all (list car cdr cdr cdr)) '(a b c d e f)) => d
((compose-all (list car)) '(a b c d)) => a
((compose-all (list list list list)) 'crazy) => (((crazy)))
((compose-all '()) 42) => 42

  2. The file recursive-arithmetic.scm contains the code for the binary representation of numbers that we developed in class. This code uses the helper functions get-last, remove-last, and add-to-end to keep the binary digits in standard order, with the least-significant digit at the rightmost position of the list. But this approach is very inefficient, since get-last, remove-last, and add-to-end reverse their input list once or twice every time they are called. Rewrite add1 and sub1 using car, cdr, and cons in place of get-last, remove-last, and add-to-end, so that binary digits are added and removed from the front of the list instead of the end.

    This changes the representation of numbers (the binary digits are now stored in reverse order), but does it break the rest of the code? In other words, do we need to modify any other definitions in the code besides add1 and sub1 in order for the arithmetic operations, and the conversion functions num-to-rep and rep-to-num, to work correctly with our new representation of numbers? If so, make the necessary modifications to the code. If not, explain why not in a brief comment in your file.

Turning in Your Homework