schemerackethtdp

Processing 2 lists simultaneously using append


I'm stuck on the question for Exercise 17.1.2 from HTDP. This is what I've got so far:

(define (cross alist1 alist2)
  (cond
    [(empty? alist1) empty]
    [else (append (list (first alist1)(first alist2))
                  (cons (first alist1)(list (first (rest alist2))))
                  (cross (rest alist1) alist2))]))

(cross '(a b c) '(1 2))
;correctly outputs (list 'a 1 'a 2 'b 1 'b 2 'c 1 'c 2)

This works for the test case, but when the second list has more than 2 elements, the function falls apart.

(cross '(a b c) '(1 2 3))
;outputs (list 'a 1 'a 2 'b 1 'b 2 'c 1 'c 2)

The problem seems to be the second line after the append, because it's only cons'ing up to two elements from the second list. How should I go about resolving this? Thanks for any insight. :)


Solution

  • It only works for two elements in list two because you only specified it to work for two elements in list two. We need to harness the power of abstraction.

    If we were working in imperative languages, then we'd use nested for-loops on this problem. You start on the first element of alist1 and match with all the elements of alist2. Then you move on to the second element of alist1 and match with all the elements of alist2. Since we're working in a functional language (Scheme) we'll use nested functions instead of nested for-loops.

    You want to write a function that takes 'a and '(1 2 3) and produces '(a 1 a 2 a 3) and then another function to call the first one with varying values of 'a. Relevant code that you should ignore if you don't want the solution spoiled for you below.

    (define (cross alist1 alist2)
     (cond
      ((null? alist1) '())
      (else 
       (append (innercross (car alist1) alist2)
               (cross (cdr alist1) alist2)))))
    
    (define (innercross a1 alist2)
     (cond
      ((null? alist2) '())
      (else
       (cons a1 (cons (car alist2) (innercross a1 (cdr alist2)))))))