Problem Set 3: Data abstractions, and higher order procedures

[jdantonio]

Part 3.1: Cons and Lists

Lec.5.2.1: Practice with Cons

Indicate the value of each of the following expressions. If evaluating the expression will cause an error, type "e".

1. (car (cons (+ 1 2) (- 3 4)))
2. (cdr 6)
3. (cdr (car (cons (cons 1 2) (cons 3 4))))
4. (cdr (cdr (cons (cons 1 2) (cons 3 4))))
5. (pair? #t)
6. (pair? (car (cons 1 2)))
7. (pair? (cons (+ 1 2) (car (cons 3 4))))

Lec.5.3.1: Practice with Lists

Indicate the value of each of the following expressions. Assume that we have already evaluated the form

(define thing (cons (cons 1 nil) (cons 2 (cons 3 nil))))

If evaluating the expression will cause an error, type "e".

1. (cons 1 nil)
2. (cons 1 (cons 2 nil))
3. thing
4. (car thing)
5. (cdr thing)
6. (car (car thing))
7. (car (car (car thing)))
8. (car (cdr (cdr thing)))

Problem Lec.5.3.2: More Practice with Lists

Due date: 2/18, 9am

Assume that we have already evaluated the form

(define thing (cons (cons (cons 1 nil) nil)
                    (cons (cons 2 (cons 3 (cons 4 nil)))
                          (cons 2
                               (cons 3 nil)))))

Write expressions using only car, cdr, and thing whose values are the list structures given below.

1. (1)
2. 1
3. (2 3)
4. (3)

Problem Lec.5.3.3: Functions on Lists

Part 1: Making a list

What expressions would you have to evaluate in order for x, y, z, and w to have the following values?

x => (())
y => (1 2 3)
z => (1 2 (3))
w => (1 (2 3) ((4)))

Use cons, nil, and integers. Please don't use list.

Note that there is a right paren over to the right of the input field.

1. (define x __________ )
2. (define y __________ )
3. (define z __________ )
4. (define w __________ )

Part 2: Some procedures on lists?

Given the values of x, y, z, and w defined above, what are the values of the following expressions?

(We know you could just type these expressions into Scheme and get the values. But please think them through! You won't have a Scheme interpreter available during quizzes!)

Here are the values again:

x => (())
y => (1 2 3)
z => (1 2 (3))
w => (1 (2 3) ((4)))

1. (length x)
2. (length y)
3. (length w)
4. (list-ref w 2)
5. (append x y)
6. (cons x y)
7. (append y w)
8. (cons y w)
9. (append y y)
10. (length (append y y))
11. (cons y y)
12. (length (cons y y))
13. (append z z)
14. (length (append z z))

Lec.5.4.1: Putting out a contract on rationals

For each of the following options (which you should treat as independent), mark the box if the procedures +rat, *rat and other procedures on rationals would still work correctly, without any further changes to the code shown in the lecture.

(define make-rat cons)
(define numer car)
(define denom cdr)

(define make-rat list)
(define numer car)
(define denom cdr)

(define (make-rat n d) (cons d n))
(define numer cdr)
(define denom car)

(define (make-rat n d) 
  (lambda (x) (if (= x 0) n d)))
(define (numer rat) (rat 0))
(define (denom rat) (rat 1))

PS.3.1.1: Is it in my list?

Write a procedure (contains? lst elt) that returns #t if elt is contained (at the top level) in lst, and #f otherwise. You should use equal? to compare items. Here are some examples:

(contains? (list 1 2 3) 3) => #t
(contains? (list 1 2 3) 4) => #f
(contains? (list 1 (list 2) 3) 2) => #f

(define contains?
  (lambda (lst elt) your_code_here))

PS.3.1.2: Too much of a good thing

Write a procedure (remove-duplicates lst) that returns a list containing the elements of lst, but with duplicates removed. You may assume that the input is a list of integers. For example:

(remove-duplicates (list 1 2 3 1 2 3)) => (1 2 3)
(remove-duplicates (list 1 1 1 1 1 1)) => (1)
(remove-duplicates (list 1 1 1 2 2 2)) => (1 2)

Keep the last of the duplicated elements.

(define remove-duplicates
  (lambda (lst) your_code_here))

PS.3.1.3: United we stand

Write a procedure (union lst1 lst2) that takes two lists of integers (containing no duplicates) and returns a list containing one instance of every integer that is in either list. Here are some examples:

(union (list 1 2 3) (list 5 3 2 1)) => (1 2 3 5)
(union (list 1 2 3) (list 5 4 1)) => (1 2 3 4 5)
(union (list 3 2 1) (list 9 10)) => (3 2 1 9 10)

Don't assume anything about the order of the input lists, and don't worry about the order of the elements your output list matches the order in the examples. You may, but are not required to, use contains? and/or remove-duplicates.

(define union
  (lambda (lst1 lst2) your_code_here))

PS.3.1.4: Subset?

Write a procedure (subset? lst1 lst2) that returns #t if the elements of lst1 are a subset of the elements of lst2. You may assume that the elements are all integers, and that no element appears more than once in a set. Here are some examples:

(subset? (list 1 2 3) (list 5 3 2 1)) => #t
(subset? (list 1 2 3) (list 5 4 1)) => #f

The elements are arranged in the lists in no particular order. Note that if you have already defined contains? in the previous problem, you may use it here.

(define subset?
  (lambda (lst1 lst2) your_code_here))

PS.3.1.5: What do we have in common?

Write a procedure (intersection lst1 lst2) that takes two lists of integers (containing no duplicates) and returns a list containing one instance of every integer that is in both lists. Here are some examples:

(intersection (list 1 2 3) (list 5 3 2 1)) => (1 2 3)
(intersection (list 1 2 3) (list 5 4 1)) => (1) 
(intersection (list 3 2 1) (list 9 10)) => ()

Don't assume anything about the order of the input lists, and don't worry about the order of the elements your output list matches the order in the examples.

(define intersection
  (lambda (lst1 lst2) your_code_here))

PS.3.1.6: Every other one

Write a procedure (every-other lst) that takes a list as argument and returns a new list, containing the 0th, 2nd, 4th, etc. elements of the initial list. These elements should appear in the same order that they did in the original list. Here are some examples:

(every-other (list 1 2 3 4 5)) => (1 3 5)
(every-other (list 2 1 3 6)) => (2 3)

(define every-other
  (lambda (lst) your_code_here))

Part 3.2: Higher Order Procedures

Lec.6.1.1: Types of Expressions

Indicate the type of each of the following expressions. Use the symbols "->" to denote "maps to", for example, the procedure square has type "number->number". Use the following terms to describe primitive types of data: number, boolean, string.

1. 6
2. (lambda (x) (+ x 1))
3. "6"
4. (> 3 4)
5. ((lambda (x) (* x 2)) 4)
6. (lambda (a b) (+ a (if b 1 0)))

Lec.6.2.1: Types of Procedures

Indicate the type of each of the following procedures.Use the symbols "->" to denote "maps to", for example, the procedure square has type "number->number". Use the following terms to describe primitive types of data: number, boolean, string.

1. (define (test bar n) (if (bar n) n (test bar (+ n 2))))
2. (define (test foo bar n) (if (bar n) #t (test foo bar (+ n (foo n)))))
3. (define (test foo bar n) (if (bar n) (+ 1 (foo n)) (test foo bar (+ n 3))))

Lec.6.3.1: Higher-Order Types

Indicate the type of each of the following expressions. (If the expression defines a procedure, then indicate the type of the procedure so defined.)

1. (lambda (x) (lambda (y) (+ x y)))
2. (lambda (p) (+ 1 (p 3)))
3. (lambda (x y comp) (if (comp x y) (+ x 1) (+ y 1)))

Lec.6.4.1: Accumulating maps and filters

Part 1: Strings to numbers

Suppose you are given a list of strings. Complete the following definition so that applying this procedure to such a list would result in a list of the lengths of each of the strings in the input. Note that string-length will measure the length of a string. (In general, remember that you can look up Scheme procedures in the online reference manual.) For example:

(lengths (list "I" "really" "like" "6.001")) => (1 6 4 5)

Use map, filter, or fold-right (with the definitions given in lecture) to do this. Please don't write a procedure that involves a recursive application of itself to walk down the input list.

(define lengths (lambda (lst) your_code_here))

Part 2: Strings to one number

Suppose you are given a list of strings. Complete the following definition so that applying this procedure to such a list would result in a sum of the lengths of each of the strings in the input. For example:

(total-length (list "I" "really" "like" "6.001")) => 16

Use map, filter, or fold-right (with the definitions given in lecture) to do this. Please don't write a procedure that involves a recursive application of itself to walk down the input list.

(define total-length
  (lambda (lst) your_code_here))

Part 3: Strings but not numbers

Now suppose that you are given a list consisting of either strings or numbers. Complete the following definition so that applying this procedure to such a list would result in the total length of the strings in the list, but not the numbers. (Note that predicates for checkings types, such as number? or string? may be helpful.) For example:

(string-em-up (list "I" "really" "like" 6.001)) => 11

Use map, filter, or fold-right (with the definitions given in lecture) to do this. Please don't write a procedure that involves a recursive application of itself to walk down the input list.

(define string-em-up
  (lambda (lst) your_code_here))

Lec.6.5.1: Make a Multiplier

Write a procedure (make-multiplier x), of type number->(number->number), that returns a procedure that takes an argument and multiplies that argument by x. So

((make-multiplier 3) 4) => 12

and

(define mult6 (make-multiplier 6))
(mult6 2) => 12
(mult6 3) => 18

(define make-multiplier
  (lambda (x) your_code_here))

Lec.6.6.1: Higher order expressions

Remember that compose is defined as:

(define (compose f g)
  (lambda (x) (f (g x))))

For each of the following expressions, if it is valid, indicate its value (if the value is a procedure, simply indicate "procedure"; if the value is unspecified, then indicate "unspecified"); if it is not valid, indicate "error". You may abbreviate "error", "procedure" and "unspecified" by their first letters, "e", "p" and "u" respectively.

1. ((compose square (lambda (x) (+ x 2))) 3)

2. ((compose (lambda (x) (+ x 2)) square) 3)

((compose (lambda (prd) (if prd "correct" "wrong"))
         (lambda (x) (> x 3)))
         4)

((compose (lambda (x) (> x 3))
         (lambda (prd) (if prd "correct" "wrong")))
         4)

1. (lambda (x) (lambda (y) (x y)))
2. ((lambda (x) (lambda (y) (x y))) square)

PS.3.2.1: Types with Variables

Indicate the type of each of the following expressions. If you need type variables, use A,B,C, etc., starting with A as the leftmost variable.

1. (lambda (x y) x)
2. (lambda (p) (p 3))
3. (lambda (p x) (p x))
4. (lambda (x y comp) (if (comp x y) x y))
5. (for simplicity, assume x and y are of the same type)

PS.3.2.2: Recursive count-true

Write a recursive (not iterative) procedure, (count-true pred lower upper), of type (number->boolean),number,number->number, that returns the number of integers in the range lower..upper (inclusive) for which predicate pred applied to that number is true.

(define count-true
  (lambda (pred lower upper) your_code_here))

PS.3.2.3: Iterative count-true

Write an iterative procedure, (count-true pred lower upper), of type (number->boolean),number,number->number, that returns the number of integers in the range lower..upper (inclusive) for which predicate pred applied to that number is true. Note that you can type multiple defines into the code box below.

(define count-true
  (lambda (pred lower upper) your_code_here))

PS.3.2.4: Recursive accumulate-interval

Write a recursive procedure, (accumulate-interval op init lower upper), of type

(number,number->number),number,number,number->number

that combines all of the elements in the interval lower upper by successive applications of op, starting with value init. So

(accumulate-interval + 0 2 4) 

would be equivalent to

2 + 3 + 4 + 0 = 9

and

(accumulate-interval * 1 2 5) 

would be equivalent to

2 * 3 * 4 * 5 * 1 = 120

(define accumulate-interval
  (lambda (op init lower upper) your_code_here))

PS.3.2.5: f and g

Suppose the following have been defined:

(define f (lambda (m b)
            (lambda (x) (+ (* m x) b))))
(define g (f 3 2))

For each of the following expressions, indicate the result of evaluating it. Possible answers are: a numeric value, the word "procedure" followed by a space and an integer indicating the number of arguments the procedure takes, or "error".
We're matching your answer directly against the answer string, so please don't include extra spaces.

1. f
2. g
3. (* (f 3 2) 7)
4. (g 6)
5. (f 6)
6. ((f 4 7) 5)

PS.3.2.6: Repeatedly Apply

Write a procedure (repeatedly-apply p n), of type (A->A),number->(A->A), that returns a procedure that takes a single argument and applies p to it n times. So, for example,

((repeatedly-apply inc 10) 2) => 12

You may assume the following function has been defined (you don't have to use it, but it can contribute to a pretty solution.)

(define compose (lambda (f g) (lambda (x) (f (g x)))))

(define repeatedly-apply
  (lambda (p n) your_code_here))

PS.3.2.7: Currying

Currying (named after the logician Haskell Curry) is the operation of taking a procedure of multiple arguments and turning it into a higher-order procedure. So a basic version of plus is defined

(define plus (lambda (a b) (+ a b)))

and used (plus 2 3). A curried version of plus has type number->(number->number), and is defined

(define plus-c (lambda (a)
         (lambda (b)
           (+ a b))))  ,

and used

((plus-c 2) 3).

Write your own higher-order procedure, (curry p), of type (A,B->C)->(A->(B->C)), that takes a binary procedure and curries it. So, for example,

(((curry plus) 2) 3) => 5.

(define curry (lambda (p) your_code_here))

Part 3.3: Optional Problems

PS.3.3.1: Who you callin' odd?

Write a procedure (mix-it-up lst) that takes a list as input, and returns a new list, with the property that for each element of argument list that is odd, it doubles the element, and for each element that is even, it halves the element. You may assume that odd? exists as a predicate. Here are some examples:

(mix-it-up (list 1 2 3 4 5)) => (2 1 6 2 10)
(mix-it-up (list 2 4 6 8)) => (1 2 3 4)

(define mix-it-up (lambda (lst) your_code_here))

PS.3.3.2: Recursive accumulate-filtered-interval

Write a procedure, (accumulate-filtered-interval filter op init lower upper), of type (number->boolean),(number,number->number),number,number,number->number that accumulates values as in accumulate-interval, but only those for which the filter predicate returns #t.

(define accumulate-filtered-interval
  (lambda (filter op init lower upper)
    your_code_here))

PS.3.3.3: Counting Truth, Again

Write a new definition of count-true that just makes a single call to accumulate-filtered-interval.

(define count-true
  (lambda (pred lower upper) your_code_here))

[jdantonio]

Required Exercises

• PS.3.2.2: Recursive count-true
• PS.3.2.3: Iterative count-true
• PS.3.3.1: Who you callin' odd?