Lab: List recursion, revisited

Assigned
Monday, Oct 15, 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 continue to explore the use of recursion, focusing primarily on patterns of recursion.

Preparation

a. Do the normal lab setup. That is

  • Start DrRacket.
  • Make sure that the csc151 package is up to date.
  • Add (require csc151) to the top of the definitions pane.

b. Remember that old zip code file? Let’s load it again.

(define zips (filter (conjoin (o real? cadr) 
                              (o real? caddr))
                     (read-csv-file "/home/username/Desktop/us-zip-codes.csv")))

Exercises

Exercise 1: Finding the smallest number

How can we find the smallest value in the list of real numbers? As you’ve seen, (min val1 val2) computes the smallest of val1 ... val2. We want to generalize this procedure to work with a list of values. You know that (reduce min lst) will find the smallest value in a list. But what if we didn’t have reduce (or, more precisely, what if we wanted to better understand how one might implement reduce)?

Write (smallest vals), a recursive procedure that computes the smallest value in a list of real numbers

To be as general as possible, your implementation of smallest should handle negative as well as positive numbers.

> (smallest (list 1 2 3 4))
1
> (smallest (list 1 10 5 6.333 0))
0
> (smallest (list -5 -10 -1 -99))
-99

Exercise 2: Joining lists

You may recall that the procedure append takes as parameters two lists, and joins the two lists together. Let’s generalize that procedure so that it works with more than two lists.

a. Write a recursive procedure, lists-join, that, given a nonempty list of lists as a parameter, joins the member lists together using append.

> (list (list 1 2 3))
'((1 2 3))
> (lists-join (list (list 1 2 3)))
'(1 2 3)
> (list (list 1 2 3) (list 10 11 12))
'((1 2 3) (10 11 12))
> (lists-join (list (list 1 2 3) (list 10 11 12)))
'(1 2 3 10 11 12)
> (list (list 1 2 3) (list 10 11 12) (list 20 21))
'((1 2 3) (10 11 12) (20 21))
> (lists-join (list (list 1 2 3) (list 10 11 12) (list 20 21)))
'(1 2 3 10 11 12 20 21)
> (list null (list 1 2 3))
'(() (1 2 3))
> (lists-join (list null (list 1 2 3)))
'(1 2 3)
> (list (list 1 2 3) null)
'((1 2 3) ())
> (lists-join (list (list 1 2 3) null))
'(1 2 3)
> (lists-join (list null (list 1 2 3) null null null null (list 100 99 98) null))
'(1 2 3 100 99 98)

Note: At first glance, it may be puzzling to work with a list of lists. However, you can disassemble that list just as you do any other list: the car of a list-of-lists is a list, the cdr of a list-of-lists is a list-of-lists, but with the first list removed.

Hint: Think about when you have a base case, what you do in the base case, and what to do with the result of the recursive case. (Remember, append is generally used to join two lists.)

b. Use lists-join to join a variety of lists, including those in the examples above.

Exercise 3: Reducing lists

Here are possible answers for exercises 1 and 2.

(define smallest
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (min (car lst) (smallest (cdr lst))))))

(define lists-join
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (append (car lst) (lists-join (cdr lst))))))

You’ll notice that both do a similar thing: They take a two-parameter procedure (min or append) and generalize it to a list of values. The process of repeatedly applying a two-parameter procedure so as to process a list is often called reducing the list using the procedure. (Some call this process folding the list using the procedure.)

You’ll also notice that they both lists-join and smallest use similar code. When we identify a common structure for similar procedures, it can be helpful to generalize and then to explore that generalization. You will do so in this exercise.

a. Sketch a template of the common parts of lists-join and smallest, with generic names like REDUCE-BY-FUN and FUN for the parts that vary.

b. Identify one or two other procedures from the reading that follow the same pattern.

c. Using your template, write a procedure, (largest lst), that finds the largest value in a list.

d. Using your template, write a procedure, (southernmost zips), that finds the southernmost city in a list of cities organized by zip code.

Hint: You may find it useful to write a utility procedure, (more-southern city1 city2), that finds the more southern of two cities.

e. Using your template, write a procedure, (longest-string strings), that finds the longest string in a list of strings. (If multiple strings are equally longest, you can choose any.)

Exercise 4: Checking for oddness

You may recall that in the reading we explored ways to build predicates that apply to lists by starting with predicates that apply to individual values. Here are slight variations of the templates we developed for those predicates.

(define all-PRED?
  (lambda (lst)
    (or (null? lst)
        (and (PRED? (car lst))
             (all-PRED? (cdr lst))))))

(define any-PRED?
  (lambda (lst)
    (and (not (null? lst))
         (or (PRED? (car lst))
             (any-PRED? (cdr lst))))))

Let’s try writing a few such procedures.

a. Using the template, write a procedure, (all-odd? ints), that, given a list of integers, determines if all of them are odd.

> (all-odd? (list 1 3 5))
#t
> (all-odd? (list))
#t
> (all-odd? (list 1 2 3 4 5))
#f
> (all-odd? (list 1.5 2 3))
. . odd?: contract violation
  expected: integer
  given: 1.5

b. Using the appropriate template, write a procedure, (any-odd? ints), that, given a list of integers, determines if any of them are odd.

> (any-odd? (list 1 3 5))
#t
> (any-odd? (list))
#f
> (any-odd? (list 2 4 6 7))
#t
> (any-odd? (list 1.5 2 3))
. . odd?: contract violation
  expected: integer
  given: 1.5

Exercise 5: Improving our sense of oddness

You’ll note that both any-odd? and all-odd? crash with an error message if given a non-integer.

Rewrite any-odd? so that it always returns #t if one or more of the elements in the list are odd, even if some of the elements in the list are not integers (and perhaps not even numbers).

> (any-odd? (list 1.5 2 3))
#t
> (any-odd? (list 1.5 2.5 3.5))
#f
> (any-odd? (list "hello" "goodbye" 3 8 9))
#t
> (any-odd? (list 2 (list 1)))
#f

Exercise 6: Looking for a needle

Using the any-PRED? template, write a procedure, (contains-needle? haystack), that takes a list as input and returns true only when the symbol 'needle appears somewhere in that list.

> (contains-needle? null)
#f
> (contains-needle? (iota 100))
#f
> (contains-needle? (list 1 "hello" 'needle (list 'and 'thread)))
#t
> (contains-needle? (append (make-list 1000 "hay")
                            (list 'needle)
                            (make-list 1000 "more hay")))
#t
> (contains-needle? (append (make-list 1000 "hay")
                            (list "needle")
                            (make-list 1000 "more hay")))
#f

Exercise 7: Checking for membership

It is often useful to ask whether a list contains a particular item. In fact, the standard Scheme procedure member and the CSC151 predicate member? both do this. Let’s write our own predicate, (list-contains? vals val) that holds only when val appears in vals.

We know that

  • val does not appear in the empty list.
  • val appears in a non-empty list, vals, if val is the car of vals
  • val appears in a non-empty list, vals, if val appears in the cdr of vals.

a. Translate this description into Scheme. That is, write list-contains?.

b. We can use list-contains? to define the following not-so-interesting procedure.

(define small-primes 
  (list 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 51 53 59 61 67 71))
(define small-prime? (section list-contains? small-primes <>))

Explain what this procedure does.

c. What result do you expect from the following expressions?

> (map small-prime? (iota 20))
> (map small-prime? small-primes)
> (map small-prime? (map square (iota 10)))

d. Check your answers experimentally.

For those With extra time

Extra 1: Closest to zero

Using your “reduce” recursive template, write a procedure, (closest-to-zero lst), that, given a list of positive and negative numbers, finds the number in the list closest to zero.

Extra 2: Not-quite reduction

We’ve seen how to reduce a list using addition or subtraction. But what if we just want to computing something new from pairs of numbers in a list.

a. Write a procedure, (difference-between lst), that takes a list of numbers as input and produces a list of the differences between each number and it’s successor in the list. The resulting list should have one fewer element than the original list.

> (difference-between (list 1 7))
'(-6)
> (difference-between (list 7 1))
'(6)
> (difference-between (list 7 1 7))
'(6 -6)
> (difference-between (list 7 1 7 2 6))
'(6 -6 5 -4)

b. Write a procedure (average-with-neighbor lst), that takes a list of numbers as input and produces a list of the average of each number and its successor.

> (average-with-neighbor (list 1 7))
'(4)
> (average-with-neighbor (list 7 1))
'(4)
> (average-with-neighbor (list 7 1 7))
'(4 4)
> (average-with-neighbor (list 7 1 7 2 6))
'(4 4 9/2 4)
> (average-with-neighbor (list 1 9 4 -2 8))
'(5 13/2 1 3)