wiki:Tutorial8

more from HtDP

The only way to become a writer is to write, not read or copy-paste.

So, just take a assignment and write the code. The trick is - choice the right textbook. HtDP should come first, then SICP could be completed much more quickly. After that PAIP or AIMA are not that scary.

; merge - merge two sorted lists of numbers
 
; It consumes two lists of numbers, sorted in ascending order. It produces a single sorted list of numbers that contains all the numbers on both inputs lists (and nothing else). A number occurs in the output as many times as it occurs on the two input lists together.

; [Number] -> [Number] -> [Number]
; (define (merge xs ys) '())  ; stub

; describe expected behavior first!
(and
  (equal? (merge (list 1 3 5 7 9) (list 0 2 4 6 8)) (list 0 1 2 3 4 5 6 7 8 9))
  (equal? (merge (list 1 8 8 11 12) (list 2 3 4 8 13 14)) (list 1 2 3 4 8 8 8 11 12 13 14)))


; templates:
;
; 1. conditions and selectors for compound data - lists
;
; (define (merge xs ys)
;    (cond ((null? xs) ...)
;          ((null? ys) ...)
;          (... (car xs) ... (cdr xs))
;          (... (car ys) ... (cdr ys))

; 2 describe all possible states

; (define (merge xs ys)
;    (cond ((and (null? xs) (null? ys)) ...)     ; both are empty
;          ((and (null? xs) (pair? ys)) ...)     ; only first is empty
;          ((and (null? ys) (pair? xs)) ...)     ; only second is empty
;          (else ...)                            ; (and (pair? xs) (pair ys))
;

; 3. adding recursion
;
; When both list are empty return the empty list. This is the base case.
; When only one of the lists is empty, just continue to traverse the other.
;
; (define (merge xs ys)
;    (cond ((and (null? xs) (null? ys)) '())
;          ((and (null? ys) (pair? xs)) (cons (car xs) (merge (cdr xs) ys)))
;          ((and (null? xs) (pair? ys)) (cons (car ys) (merge xs (cdr ys))))
;          (else ...)))

; 4. when both lists have elements,
;
; If the first list has the lesser element then shift it 

(define (merge xs ys)
   (cond ((and (null? xs) (null? ys)) '())
         ((and (null? ys) (pair? xs)) (cons (car xs) (merge (cdr xs) ys)))
         ((and (null? xs) (pair? ys)) (cons (car ys) (merge xs (cdr ys))))
         (else (if (< (car xs) (car ys)) 
                   (cons (car xs) (merge (cdr xs) ys))
                   (cons (car ys) (merge xs (cdr ys)))))))

; pretty straightforward, pretty ugly

; expectations checking
(and
  (equal? (merge (list 1 3 5 7 9) (list 0 2 4 6 8)) (list 0 1 2 3 4 5 6 7 8 9))
  (equal? (merge (list 1 8 8 11 12) (list 2 3 4 8 13 14)) (list 1 2 3 4 8 8 8 11 12 13 14)))

; simplify the logic - removing redundant if

(define (merge xs ys)
    (cond ((and (null? xs) (null? ys)) '())
          ((and (null? ys) (pair? xs)) (cons (car xs) (merge (cdr xs) ys)))
          ((and (null? xs) (pair? ys)) (cons (car ys) (merge xs (cdr ys))))
          ((< (car xs) (car ys))       (cons (car xs) (merge (cdr xs) ys))
          (else                        (cons (car ys) (merge xs (cdr ys)))))))

; still very ugly

; simplify the logic - removing useless traversals

; When one of the lists is empty it is no use to produce new copy of the other
; just return the original one.

(define (merge xs ys)
   (cond ((null? xs) ys)
         ((null? ys) xs)
         ((< (car xs) (car ys)) (cons (car xs) (merge (cdr xs) ys)))
         (else                  (cons (car ys) (merge xs (cdr ys))))))

; now it makes sense

; checking expectations
(and
  (equal? (merge (list 1 3 5 7 9) (list 0 2 4 6 8)) (list 0 1 2 3 4 5 6 7 8 9))
  (equal? (merge (list 1 8 8 11 12) (list 2 3 4 8 13 14)) (list 1 2 3 4 8 8 8 11 12 13 14)))

Last modified 7 years ago Last modified on Jul 20, 2013, 9:57:52 AM
Note: See TracWiki for help on using the wiki.