;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-reader.ss" "lang")((modname 24.4.5) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor mixed-fraction #f #t none #f ())))
; Worked exercise 24.4.5

; A built-binary-natural is either
; 0,
; (S0 built-binary-natural), or
; (S1 built-binary-natural).

(define (S0 x) (* x 2)) ; for short
(define (S1 x) (add1 (* x 2))) ; for short
(define (half x) (quotient x 2))

; spams : built-binary-natural -> list-of-strings
(check-expect (spams 0) empty)
(check-expect (spams (S0 0)) empty) ; (S0 0) is still zero
(check-expect (spams (S1 0)) (list "spam"))
(check-expect (spams 1) (list "spam"))
(check-expect (spams (S0 (S1 0))) (list "spam" "spam"))
(check-expect (spams 2) (list "spam" "spam"))
(check-expect (spams (S0 (S1 (S1 0))))
              (list "spam" "spam" "spam" "spam" "spam" "spam"))
(check-expect (spams 6)
              (list "spam" "spam" "spam" "spam" "spam" "spam"))
(check-expect (spams (S1 (S1 (S1 0))))
              (list "spam" "spam" "spam" "spam" "spam" "spam" "spam"))
(check-expect (spams 7)
              (list "spam" "spam" "spam" "spam" "spam" "spam" "spam"))

(define (spams n)
  (cond [(zero? n) empty]
        [(even? n)
         ; n                      natural     (S0 (S1 (S1 0))), i.e. 6
         ; (half n)               natural     (S1 (S1 0)), i.e. 3
         ; (spams (half n))       string-list (list "spam" "spam" "spam")
         ; right answer           string-list (list "spam" "spam" "spam" "spam" "spam" "spam")
         (append (spams (half n)) (spams (half n)))
         ]
        [(odd? n)
         ; n                      natural     (S1 (S1 (S1 0))), i.e. 7
         ; (half n)               natural     (S1 (S1 0)), i.e. 3
         ; (spams (half n))       string-list (list "spam" "spam" "spam")
         ; right answer           string-list (list "spam" "spam" "spam" "spam" "spam" "spam" "spam")
         (cons "spam" (append (spams (half n)) (spams (half n))))
         ]))