;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname 06two-lists-lockstep) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; DEMO: Working with two lists: the general case

#|
    In the general case of working with two lists at possibly different
    rates, the template may take two forms, each with its own advantages.
    The nested form often helps discover when the full generality of the
    template is not needed, and it can lead to simpler code.  But when
    the full generality *is* needed, I generally find the flat form
    easier to read.  To a degree at least, these are matters of taste.
|#

; nested template: three `cond` forms, one list per question
(define (nested-two-lists-template xs ys)
  (cond [(empty? xs)
            (cond [(empty? ys) ...]
                  [(cons? ys)
                       (... (first ys) ... (rest ys) ...)])]
        [(cons? xs)
            (cond [(empty? ys)
                       (... (first xs) ... (rest xs) ...)]
                  [(cons? ys)
                       (... (first ys) ... (rest ys) ... ys ...
                            (first xs) ... (rest xs) ... xs ...)])]))

; flat template: one `cond` forms, two lists per question
(define (flat-two-lists-template xs ys)
  (cond [(and (empty? xs) (empty? ys)) ...]
        [(and (empty? xs) (cons? ys))
                       (... (first ys) ... (rest ys) ...)]
        [(and (cons? xs) (empty? ys))
                       (... (first xs) ... (rest xs) ...)]
        [(and (cons? xs) (cons? ys))
                       (... (first ys) ... (rest ys) ... ys ...
                            (first xs) ... (rest xs) ... xs ...)]))

;; merge : list-of-numbers list-of-numbers -> list-of-numbers
;; given two lists in decreasing order, produce a single list
;;   combining all the numbers in both lists, the result also
;;   to be in decreasing order
(define (merge-template xs ys)
  ...)
(check-expect (merge '(7 2 1) '(9 4 3)) '(9 7 4 3 2 1))
(check-expect (merge empty  '(2 1))  '(2 1))
(check-expect (merge '(2 1) empty)    '(2 1))
(check-expect (merge empty empty) empty)


(define (merge xs ys)
  (cond [(empty? xs)
            (cond [(empty? ys) ...]
                  [(cons? ys)
                       (... (first ys) ... (rest ys) ...)])]
        [(cons? xs)
            (cond [(empty? ys)
                       (... (first xs) ... (rest xs) ...)]
                  [(cons? ys)
                       (... (first ys) ... (rest ys) ... ys ...
                            (first xs) ... (rest xs) ... xs ...)])]))