(define snoc
 ; TYPE (-> ((list T) T) (list T))
  (lambda (lst item)  
    (if (null? lst)
	(cons item lst)
	(cons (car lst)
	      (snoc (cdr lst) item)))))	  

(define reverse
    (lambda (ls)
	(if (null? ls)
	    '()
	    (snoc (reverse (cdr ls))
		  (car ls)))))

(define prod
  (lambda (lst)  
    ; REQUIRES: lst is not empty
    (if (null? (cdr lst))
	(car lst)
	(* (car lst)
	   (prod (cdr lst))))))

(define merge
  (lambda (sorted-ntpl1 sorted-ntpl2)
    (cond 
      ((null? sorted-ntpl1) sorted-ntpl2)
      ((null? sorted-ntpl2) sorted-ntpl1)
      ((< (car sorted-ntpl1)
	  (car sorted-ntpl2))
       (cons (car sorted-ntpl1) 
             (merge (cdr sorted-ntpl1)
		    sorted-ntpl2)))
      (else
       (cons (car sorted-ntpl2) 
	     (merge sorted-ntpl1
		    (cdr sorted-ntpl2))))
      )))

(define append
  (lambda (ls1 ls2)       
    (if (null? ls1) 
        ls2
        (cons (car ls1)
              (append (cdr ls1) ls2)))))

(define even-length? 
  (lambda (lst)
    (or (null? lst)
	(odd-length? (cdr lst)))))

(define odd-length? 
  (lambda (lst)
    (and (not (null? lst))
	 (even-length? (cdr lst)))))