; Scheme and the Art of Programming
; Chapter 3

; -- Exercise 3.1
; Define a procedure sum that finds the sum of the 
; components of an n-tuple.

(define (sum ntpl)
  (if (null? ntpl) 0 (+ (car ntpl) (sum (cdr ntpl)))))

(sum '(1 2 3 4 5))
; Value: 15

(sum '(6))
; Value: 6

(sum '())
; Value: 0


; -- Exercise 3.2
; Define a procedure pairwise-sum that takes two n-tuples 
; of the same length, ntpl-1 and ntpl-2, as arguments and 
; produces a new n-tuple whose components are the sum of 
; the corresponding componenets of ntpl-1 and ntpl-2.

(define (pairwise-sum ntpl-1 ntpl-2)
  (if (null? ntpl-1) '()
      (cons (+ (car ntpl-1) (car ntpl-2))
	    (pairwise-sum (cdr ntpl-1) (cdr ntpl-2)))))

(pairwise-sum '(1 3 2) '(4 -1 2))
; Value: (5 2 4)

(pairwise-sum '(3.2 1.5) '(6.0 -2.5))
; Value: (9.2 -1.0)

(pairwise-sum '(7) '(11))
; Value: (18)

(pairwise-sum '() '())
; Value: ()


; -- Exercise 3.3
; Define a procedure dot-product that takes two n-tuples 
; of the same length, multiplies the corresponding 
; components, and adds the resulting products.

(define (dot-product ntpl-1 ntpl-2)
  (if (null? ntpl-1) 0
      (+ (* (car ntpl-1) (car ntpl-2)) 
	 (dot-product (cdr ntpl-1) (cdr ntpl-2)))))

(dot-product '(3 4 -1) '(1 -2 -3))
; Value: -2

(dot-product '(0.003 0.035) '(8 2))
; Value: 0.094

(dot-product '(5.3e4) '(2.0e-3))
; Value: 106.0

(dot-product '() '())
; Value: 0


; -- Exercise 3.4
; Define a procedure mult-by-n that takes a number num 
; and an n-tuple ntpl as arguments each component of 
; ntpl by num.

(define (mult-by-n num ntpl)
  (if (null? ntpl) '() 
      (cons (* num (car ntpl)) (mult-by-n num (cdr ntpl)))))

(mult-by-n 3 '(1 2 3 4 5))
; Value: (3 6 9 12 15)

(mult-by-n 0 '(1 3 5 7 9 11))
; Value: (0 0 0 0 0 0)

(mult-by-n -7 '())
; Value: ()


; -- Exercise 3.5
; Define a procedure index that has two arguments, and item 
; a and a list of items ls, and returns the index of a in ls, 
; that is, the zero-based location of a in ls.  If the item 
; is not in the list, the procedure returns -1.

(define (index a ls) (index-aux a ls 0))
(define (index-aux a ls n)
  (cond
   ((null? ls) -1)
   ((equal? a (car ls)) n)
   (else (index-aux a (cdr ls) (+ n 1)))))

(index 3 '(1 2 3 4 5 6))
; Value: 2

(index 'so '(do re me fa so la ti do))
; Value: 4

(index 'a '(b c d e))
; Value: -1

(index 'cat '())
; Value: -1


; -- Exercise 3.6
; Define a procedure make-list that takes as arguments 
; a nonnegative integer num and an item a and returns a 
; list of num elements, each of which is a.

(define (make-list num a)
  (if (= num 0) '() (cons a (make-list (- num 1) a))))

(make-list 5 'no)
; Value: (no no no no no)

(make-list 1 'maybe)
; Value: (maybe)

(make-list 0 'yes)
; Value: ()

(length (make-list 7 'any))
; Value: 7

(all-same? (make-list 100 'any))
; Value: #t


; -- Exercise 3.7
; Define a procedure count-background that takes an item a 
; and a list of items ls as arguments and returns the number 
; of items in ls that are not equal to a.

(define (count-background a ls) (count-bg-aux a ls 0))
(define (count-bg-aux a ls count)
  (cond
   ((null? ls) count)
   ((not (eq? a (car ls))) (count-bg-aux a (cdr ls) (+ count 1)))
   (else (count-bg-aux a (cdr ls) count))))

(count-background 'blue '(red white blue yellow blue red))
; Value: 4

(count-background 'red '(white blue green))
; Value: 3

(count-background 'white '())
; Value: 0


; -- Exercise 3.8
; Define a procedure list-front that takes as arguments a list 
; of items ls and a nonnegative integer num and returns the 
; first num top-level items in ls.  If num is larger than the 
; number of top-level items in ls, an error is signaled.

(define (list-front ls num)
  (if (> num (length ls))
      (begin (display "Error: length exceeded") (newline))
      (list-front-helper ls num)))
(define (list-front-helper ls num)
  (if (= num 0)
      '()
      (cons (car ls) (list-front-helper (cdr ls) (- num 1)))))

(list-front '(a b c d e f g) 4)
; Value: (a b c d)

(list-front '(a b c) 4)
; Value: Error: Length exceeded

(list-front '(a b c d e f g) 0)
; Value: ()

(list-front '() 3)
; Value: Error: length exceeded


; -- Exercise 3.9
; Define a procedure wrapa that takes as arguments an item a 
; and a nonnegative integer num and wraps num sets of parens 
; around the item a.

(define (wrapa a num)
  (if (= num 0) a (cons (wrapa a (- num 1)) '())))

(wrapa 'gift 1)
; Value: (gift)

(wrapa 'sandwich 2)
; Value: ((sandwich))

(wrapa 'prisoner 5)
; Value: (((((prisoner)))))

(wrapa 'moon 0)
; Value: moon


; -- Exercise 3.10
; Define a predicate multiple? that takes as arguments two 
; integers m and n and returns #t if m is an integer multiple 
; of n.

(define (multiple? m n)
  (if (= n 0) #f (= (remainder m n) 0)))

(multiple? 7 2)
; Value: #f
(multiple? 9 3)
; Value: #t
(multiple? 5 0)
; Value: #f
(multiple? 0 20)
; Value: #t
(multiple? 17 1)
; Value: #t


; -- Exercise 3.11
; Write a procedure sum-of-odds that sums the first n odd 
; integers. 

(define (sum-of-odds n)
  (if (= n 0) 0
      (+ (- (* 2 n) 1) (sum-of-odds (- n 1)))))

(define (accum-sum-of-odds size)
  (if (= size 0) '()
      (cons (sum-of-odds size) (accum-sum-of-odds (- size 1)))))

(define (accum-squares size)
  (if (= size 0) '()
      (cons (* size size) (accum-squares (- size 1)))))

(equal? (accum-sum-of-odds 10) (accum-squares 10))
; Value: #t


; -- Exercise 3.12
; Define a procedure n-tuple->integer that converts a nonempty 
; n-tuple of digits into the number having those digits.

(define (n-tuple->integer ntpl)
  (if (null? ntpl) 0
      (+ (* (car ntpl) (** 10 (- (length ntpl) 1))) 
	 (n-tuple->integer (cdr ntpl)))))

(define (** base exp)
  (if (= exp 0) 1
      (* base (** base (- exp 1)))))

(n-tuple->integer '(3 1 4 6))
; Value: 3146

(n-tuple->integer '(0))
; Value: 0

(n-tuple->integer '())
; Value: 0

(+ (n-tuple->integer '(1 2 3)) (n-tuple->integer '(3 2 1)))
; Value: 444


; -- Exercise 3.13
; If ls is a list of length 1000, how much "cdring" in ls is 
; necessary in each of three programs for list-ref presented 
; in this section in order to find (list-ref ls 4)?