Module 6 Extra Materials

The Three Cases For Recursion With Two Lists

There are three cases to consider when dealing with two recursive data. In the lecture we illustrated it using two lists:

Case 1: along the ride.

Only perform recursion on one lists, the other list goes along the ride. This case happens if you just need to use the other list as a value, without destructing the other list (that is, perform recursion on it.)

Case 2: processing in lockstep.

This case is for when you have two lists of the same length and you are processing both values together. The contract should require the two function have the same length. If first list is empty, so is the second list.
That is why in the template we are destructing both lists together:

(define (lockstep-template list1 list2)
  (cond
    ;; The case where list1 and list2 are both empty
    [(empty? list1) ...] 
    [else (... (first list1) ... (first list2) ...
               (lockstep-template (rest list1) (rest list2)))]))

Case 3: processing at different rates.

This is slightly more complicated since there are four cases:

both lists are empty;
first list is empty and second one is not;
first list is not empty and second one is empty;
both lists are not empty.

Recall that in Module 4, when there is one list to perform recursion with, we apply the recursive application on the rest of the list. The rest of the list here represents the list that is one element fewer then the list we have now. This way we are working in a "smaller" instance of the same problem.

Therefore, if there is a smaller instance of the same problem, you should probably make use of recursion and assume you have the solution for smaller instances.

So in case 2, 3, 4 there are smaller instances of the same problem:

In case 2, we can still recurse on the second list;
In case 3, we can perform recursion on the first list.
In case 4, there are three choices of what this "smaller instances" is. Depending on the problem (or the cases in the problem), you might need to do some of them:
Destruct list1: use (first list1) and the smaller instance will involve (rest list1) and list2;
```
... (first list1) ... (twolist-template (rest list1) list2) ...
```
Destruct list2: use (first list2) and the smaller instance will involve (rest list2) and list1;
```
... (first list2) ... (twolist-template list1 (rest list2)) ...
```
Destruct both list1 and list2: use both (first list1) and (first list2) and the smaller instance will involve (rest list1) and (rest list2).
```
... (first list1) ... (first list2) ...
... (twolist-template (rest list1) (rest list2)) ...
```

That's why we have this gigantic template:

(define (twolist-template list1 list2)
  (cond
    [(and (empty? list1) (empty? list2)) ...]
    [(empty? list1) 
     (... (first list2) ... (twolist-template empty (rest list2)) ...)]
    [(empty? list2)
     (... (first list1) ... (twolist-template (rest list1) empty) ...)]
    [else 
     (... (first list1) ... (twolist-template (rest list1) list2) ...

      ... (first list2) ... (twolist-template list1 (rest list2)) ...

      ... (first list1) ... (first list2) ...
      ... (twolist-template (rest list1) (rest list2)) ...)
    ]))

`merge` simplified.

(define (merge list1 list2)
  (cond
    ;; The following line is not needed, since the (empty list1) case handles this case.
    ;; [(and (empty? list1) (empty? list2)) empty]
    [(empty? list1) list2]
    [(empty? list2) list1]
    [(< (first list1) (first list2)) (cons (first list1) (merge (rest list1) list2))]
    [else (cons (first list1) (merge (rest list1) list2))]))

Slide 36: Midpoints of pairs of point

Given two lists of points, we would like to find a list of midpoints between each pair of corresponding points.

Recall previously we have the following definition on the Point:

(define (make-point x y)
  (list x y))

(define (point-x p) (first p))
(define (point-y p) (second p))

The text "each pair of corresponding points" hinted that the two lists given always have the same length; this means we are in case 2 above and we will be using the lockstep template.

;; (all-midpts lop1 lop2) produces a list of midpoints from each pair of
;; corresponding points given in lop1 and lop2.
;; all-midpts: (listof Point) (listof Point) -> (listof Point)
;; Examples: Exercise
(define (all-midpts lop1 lop2)
  (cond
    [(empty? lop1) empty]
    [else ...]))

How do we compute the midpoint of two points?

Given two points $(x_1,y_1)$ and $(x_2,y_2)$ in a cartesian plane, the coordinate of the midpoint is the average of the coordinates of the two points, that is, $(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2})$ .

Here are a few illustrations:

;; midpt: Point Point -> Point
(define (midpt p1 p2)
  (make-point (/ (+ (point-x p1) (point-x p2)) 2)
              (/ (+ (point-y p1) (point-y p2)) 2)))

Now we can complete the implementation of all-midpts:

;; (all-midpts lop1 lop2) produces a list of midpoints from each pair of
;; corresponding points given in lop1 and lop2.
;; all-midpts: (listof Point) (listof Point) -> (listof Point)
;; Examples: Exercise
(define (all-midpts lop1 lop2)
  (cond
    [(empty? lop1) empty]
    [else (cons (midpt (first lop1) (first lop2))
                (all-midpts (rest lop1) (rest lop2)))]))