;;; ========================================
;;;  CMPU-145, Spring 2013
;;;  Lab 5 Solutions
;;;  March 4, 2013
;;; ========================================

(load "asmt-helper.txt")

(header "Solutions" "Lab 5")


;;;  (A) Global variables
;;; ===========================

(problem "A:  Global variables")

;;  A few list-based natural numbers...
;; -------------------------------------------------

(define nn0 ())
(define nn1 '(1))
(define nn2 '(1 1))
(define nn3 '(1 1 1))
(define nn4 '(1 1 1 1))
(define nn5 '(1 1 1 1 1))

(tester 'nn0)
(tester 'nn1)
(tester 'nn2)
(tester 'nn3)


;;  (B) NN-SUCC
;; =========================================================
;;  The successor function for list-based natural numbers

(problem "B:  NN-SUCC")

;;;  NN-SUCC
;;; ------------------------------
;;;  INPUT: N, a natural number represented by a list of ones
;;;  OUTPUT:  The successor to N, also represented by a list of ones

(define nn-succ
  (lambda (n) 
    (cons 1 n)))

(tester '(nn-succ nn0))
(tester '(nn-succ nn1))
(tester '(nn-succ '(1 1 1 1 1)))


;;;  Converting from ordinary numbers to a list of ones
;;; ========================================================

(problem "C:  MAKE-NN")

;;;  MAKE-NN
;;; ------------------------------------
;;;  INPUT:  N, an ordinary natural number
;;;  OUTPUT:  The corresponding list of ones
;;;  EXAMPLE:  (make-nn 5) ==> (1 1 1 1 1)

(define make-nn
  (lambda (n)
    (if (zero? n)
        ;; Base Case:  Return "zero" (i.e., the empty-list)
        nn0
        ;; Recursive Case:  Return the "successor" of "n-1"
        ;; Notice the use of the previously defined NN-SUCC and MAKE-NN.
        (nn-succ (make-nn (- n 1))))))

(tester '(make-nn 5))
(tester '(make-nn 20))

;;;  (D) The NN-ZERO? function
;;; ===================================================

(problem "D: NN-ZERO?")

;;;  NN-ZERO?
;;; -------------------------------
;;;  INPUT:  A natural number represented by a list of ones
;;;  OUTPUT:  #t if that natural number is nn0 (i.e., ()).

(define nn-zero? null?)

(tester '(nn-zero? nn0))
(tester '(nn-zero? (make-nn 5)))
(tester '(nn-zero? ()))
(tester '(nn-zero? '(1 1 1 1)))


;;  (E) NN-PRED
;; --------------------------------
;;  The predecessor function for list-based natural numbers

(problem "E: The NN-PRED function")

;;;  NN-PRED
;;; -----------------------------------
;;;  INPUT:  NN, a natural number represented by a list of ones
;;;  OUTPUT:  The predecessor of NN, also rep'd by a list of ones

(define nn-pred rest)

(tester '(nn-pred '(1 1 1 1 1)))
(tester '(nn-pred '(1)))


;;;  (F) Addition of Natural Numbers
;;; =====================================================

(problem "F:  Addition of Natural Numbers")

;;;  NN-ADDN
;;; ---------------------------------
;;;  INPUTS:  X, Y, natural numbers represented by a list of ones
;;;  OUTPUT:  The natural number, X+Y, also rep'd by a list of ones
;;; Notice that it is defined in terms of the functions NN-ZERO?,
;;;  NN-SUCC and NN-PRED, which are defined above.

(define nn-addn
  (lambda (x y)
    (cond
      ;; Base Case:   Y = 0
      ((nn-zero? y)
       (printf "Rule 1: x = ~A~%" x)
       ;; Thus X+Y = Y
       x)
      ;; Recursive Case: Y = SUCC of some K
      (#t
       ;;   So, X + Y = X + SUCC(K) = SUCC (X + K)
       ;;   Where K is represented by (NN-PRED Y)
       (printf "Rule 2: x = ~A, y = ~A~%" x y)
       (nn-succ (nn-addn x (nn-pred y)))))))

(tester '(nn-addn '(1 1 1) '(1 1)))
(tester '(nn-addn nn5 nn4))