- Assigned
- Friday, Nov 9, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In this laboratory, you will use and define higher-order procedures.

Make sure that you understand what `map`

, `compose`

, `o`

, `left-section`

,
`right-section`

, and `apply`

are intended to do.

`map`

and `apply`

a. Use `apply`

and `map`

to sum the first elements of each list in a
list of lists of numbers. The result should be a number.

```
> (apply _____ (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12))))
23 ; 1 + 4 + 7 + 11
```

b. Use `apply`

and `map`

to sum the last elements of each list in a list
of lists of numbers. The result should be a number.

```
> (apply _____ (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12))))
31 ; 3 + 6 + 10 + 12
```

a. Here are four expressions to generate the successors of the squares of the first ten positive integers. Verify that each works correctly.

```
(define v1 (map increment (map square (map increment (iota 10)))))
(define v2 (map (lambda (i) (increment (square (increment i)))) (iota 10)))
(define v3 (map (compose increment (compose square increment)) (iota 10)))
(define v4 (map (o increment square increment) (iota 10)))
```

b. Which of the four definitions above you prefer? Why? Be prepared to discuss your reasons with the class.

Use `apply`

and `map`

to concisely define a procedure, ```
(dot-product
lst1 lst2)
```

, that takes as arguments two lists of numbers,
equal in length, and returns the sum of the products of corresponding
elements of the arguments:

```
> (dot-product (list 1 2 4 8) (list 11 5 7 3))
73
> (dot-product null null)
0
```

Note that we get the first result because (1 x 11) + (2 x 5) + (4 x 7) + (8 x 3) = 11 + 10 + 28 + 24 = 73 and the second because there are no products to add.

*Note:* You should not use recursion.

The procedure `(acronym strings)`

is intended to produce
an acronym from a list of strings. For example,

```
> (acronym (list "GNU" "Image" "Manipulation" "Program"))
"GIMP"
> (acronym (list "International" "Business" "Machinery"))
"IBM"
> (acronym (list "Grinnell" "Independent" "Musical" "Productions"))
"GIMP"
```

Write `acronym`

as concisely as possible. As a hint, you will want to use
`string-ref`

, `list->string`

, `map`

, and either `l-s`

or `r-s`

.

(Recall that `(string-ref string i)`

produces the * i*th
character in

`string`

`list->string`

takes a list of characters and
turns it into a string.)Without using `filter`

, write a procedure, ```
(list-remove lst
predicate)
```

, that takes a list and predicate as parameters
and removes all elements for which * predicate* holds.

For example,

```
> (list-remove (iota 10) odd?)
'(0 2 4 6 8)
> (define remove-whitespace (r-s list-remove char-whitespace?))
> (remove-whitespace (list #\a #\space #\b #\c))
(#\a #\b #\c)
> (list->string (remove-whitespace (string->list "Hello, my name is Dr. gigls")))
"Hello,mynameisDr.gigls"
```

Note: Although this problem can be solved using `map`

and `apply`

,
it is much more straightforward to solve using recursion.

It is often the case that we have situations in which we need more than
one predicate to hold. For example, since the `odd?`

predicate only
works with integers, it is often helpful to test whether a value is an
integer before testing whether it is odd.

```
> (odd? 3)
#t
> (odd? 4)
#f
> (odd? 3.5)
odd?: expects argument of type <integer>; given 3.5
> (define odd-integer? (lambda (val) (and (integer? val) (odd? val))))
> (odd-integer? 3.5)
#f
> (odd-integer? 3)
#t
> (odd-integer? 4)
#f
```

But if it’s common to combine predicates into a new predicate, we might
want to write a higher-order procedure that does that. For example,
we might write a procedure, `(both p1 p2)`

that takes two
predicates as parameters, and returns a new predicate that holds only
when both of its component predicates hold.

```
> (define odd-integer? (both integer? odd?))
> (odd-integer? 3)
#t
> (define one-element-list? (both pair? (o null? cdr)))
> (one-element-list? 2)
#f
> (one-element-list? null)
#f
> (one-element-list? (list 1))
#t
> (one-element-list? (cons 2 null))
#t
> (one-element-list? (cons 2 3))
#f
```

Write the `both`

procedure.

*Note:* You may know this predicate as `conjoin`

. Pretend that `conjoin`

does not exist.

a. Document and write a recursive procedure, `(tally predicate lst)`

, that
counts the number of values in `lst`

for which predicate holds.

b. Demonstrate the procedure by tallying the number of odd values in the list of the first twenty integers.

c. Demonstrate the procedure by tallying the number of multiples of three in the list of the first twenty integers.

You may choose to do these problems in any order.

a. Write `(either p1 p2)`

, a procedure which takes two
predicates as parameters and returns a predicate that holds when either
of those predicates holds.

b. Write a procedure, `(negate pred)`

, that returns `#t`

on the values for which * pred* returns

`#f`

, and returns `#f`

on the
values for which `pred`

```
> (define non-empty-list? (both list? (negate null?)))
> (non-empty-list? (list 1 2 3))
#t
> (non-empty-list? 32)
#f
> (non-empty-list? (cons 1 2))
#f
> (non-empty-list? null)
#f
```

Document and write a procedure, (make-tallier predicate), that builds a procedure that takes a list as a parameter and tallies the values in the list for which the predicate holds. For example

```
> (define count-odds (make-tallier odd?))
> (count-odds (list 1 2 3 4 5))
3
```

You can assume that `tally`

already exists for the purpose of this
problem.

Write a procedure, `(vector-transform! proc vec)`

, that replaces
each element of * vec* with the result of applying

`proc`

```
> (define vec (vector 1 2 3))
> vec
'#(1 2 3)
> (vector-transform! square vec)
> vec
'#(1 4 9)
```