;;;;;; 2.7
(define (make-interval a b)
  (cons a b))
(define (upper-bond x)
  (cdr x))
(define (lower-bond x)
  (car x))

;STk> (define a (make-interval 3 5))
;a
;STk> (define b (make-interval 10 11))
;b
;STk> (upper-bond a)
;5
;STk> (upper-bond b)
;11
;STk> (lower-bond a)
;3
;STk> (lower-bond b)
;10


;;;;;; 2.8
;the lower bond of a-b will be lower bond of a - upper bond of b
;the upper bond of a-b will be upper bond of a - lower bond of b
;using the make-interval procedure define in exercise 2.7
(define (sub-interval x y)  
  (make-interval (- (lower-bond x) (upper-bond y))
		 (- (upper-bond x) (lower-bond y))))

;STk> (define a (make-interval 3 5))
;a
;STk> (define b (make-interval 10 11))
;b
;STk> (sub-interval b a)
;(5 . 8)


;;;;;; 2.10
;define a procedure named spanzero? to check
(define (spanzero? x)
  (and (not (> (lower-bond x) 0)) (not (< (upper-bond x) 0))))

;now, define the modified div-interval
(define (div-interval x y)
  (if (spanzero? y)
      (print '(error! dividing a span zero interval.))
      (mul-interval x
		    (make-interval (/ 1.0 (upper-bond y))
				   (/ 1.0 (lower-bond y))))))

;use the book's version of mul-interval
(define (mul-interval x y)
  (let ((p1 (* (lower-bond x) (lower-bond y)))
	(p2 (* (lower-bond x) (upper-bond y)))
	(p3 (* (upper-bond x) (lower-bond y)))
	(p4 (* (upper-bond x) (upper-bond y))))
    (make-interval (min p1 p2 p3 p4)
		   (max p1 p2 p3 p4))))

;STk> (define a (make-interval 3 5))
;a
;STk> (define b (make-interval 10 11))
;b
;STk> (define c (make-interval -1 10))
;c
;STk> (div-interval b a)
;(2.0 . 3.66666666666667)
;STk> (div-interval b c)
;(error! dividing a span zero interval.)
	    

;;;;;; 2.12
;assuming (make-center-percent 20 5) means a interval (19 21)
;that is, center at 20, ratio is 5%
;make-interval, lower-bond, upper-bond defined as privious
(define (make-center-percent x y)
  (let ((z (* x y)))
    (make-interval (- x z) (+ x z))))
(define (center i)
  (/ (+ (lower-bond i) (upper-bond i)) 2))
(define (percent i)
  (let ((a (abs (center i)))
	(b (abs (- (upper-bond i) (center i)))))
    (if (= a 0)
	(print '(cannot be defind as center-percent notation))
	(* 100 (/ b a)))))

;STk> (define a (make-interval 3 5))
;a
;STk> (percent a)
;25.0
;STk> (center a)
;4


;;;;;; 2.20
(define (check-parity condition arg)
  (cond ((empty? arg) '())
	((condition (car arg)) (se (car arg) (check-parity condition (cdr arg))))
	(else (check-parity condition (cdr arg)))))
(define (same-parity a . rest)
  (if (even? a) (se a (check-parity even? rest))
      (se a (check-parity odd? rest))))

;STk> (same-parity 1 2 3 4 5 6)
;(1 3 5)
;STk> (same-parity 2 3 4 5 6 7 8 9)
;(2 4 6 8)
;STk> (same-parity 1)
;(1)


;;;;;; 2.22
(define (square x) (* x x))
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (cons (square (car things))
		    answer))))
  (iter items nil))

;the code above gives result like this
;STk> (square-list (list 1 2 3 4))
;(16 9 4 1)
;the reason is the (cons (square (car things)) answer), we are constructing the square of the
;first date in things with the answer, so 1 squared first, construct first, then 2, then 3,
;and finally, 4, so answer becomes 16 9 4 1

(define (square-list2 items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (cons answer
		    (square (car things))
		    ))))
  (iter items nil))

;this doesn't work either, but if we mean the order of numbers, it's in the right order
;here is the execution result
;STk> (square-list2 (list 1 2 3 4))
;((((() . 1) . 4) . 9) . 16)
;hopefully, it's in the order of 1 4 9 16, but the () and . give an unpleasure view.
;the reason is that cons is different from the list. when we (cons nil 1), the form
;is different from the form of list which is (cons 1 nil). Afterwards, construct something not
;list, such as (() . 1) with a number, say 4, it cannot form a list. Therefore, the answer is
;in the right order, but not a list

;one way to correct this bug is to use the primitive procedure append
(define (square-list3 items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things) (append answer (cons (square (car things)) nil))
	      )))
  (iter items nil))
;run-time result is given by
;STk> (square-list3 (list 1 2 3 4))
;(1 4 9 16)


;;;;;; 2.24
;STk> (list 1 (list 2 (list 3 4)))
;(1 (2 (3 4)))
;here is the box and pointer structure 
;_________    _________
;|  * | *---> | * | / |
;___|_____    __|______
;   |           |
;   |           |
;   V           V
;   1         _________    _________
;             | * | *----> | * | / |
;             __|______    __|______
;               |            |
;               |            |
;               V            V
;               2          _________    _________
;                          | * | *----> | * | / |
;                          __|______    __|______
;                            |            |
;                            |            |
;                            V            V
;                            3            4
;
;here is the tree structure
;       (1 (2 (3 4)))
;           /\
;          /  \
;         /    \
;        1   (2 (3 4))
;                /\
;               /  \
;              /    \
;             2    (3 4)
;                    /\
;                   /  \
;                  /    \
;                 3      4


;;;;;; 2.26
(define x (list 1 2 3))
(define y (list 4 5 6))

;STk> (append x y)
;(1 2 3 4 5 6)
;STk> (cons x y)
;((1 2 3) 4 5 6)
;STk> (list x y)
;((1 2 3) (4 5 6))
;append make a list of 1 2 3 4 5 6
;cons make a pair which car part is a list of 1 2 3, and cdr part is a list of 4 5 6
;list make a list which first data is a list of 1 2 3, and the sencond data is a list of 4 5 6
;we can also say that (car (list x y)) gives a list of 1 2 3 and (cadr (list x y)) gives
;a list of 4 5 6. Note it's differnet from the (cons x y)


;;;;;; 2.29
(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list length structure))

;define global constant a and b for the testing purpose
(define a (make-mobile (make-branch 4 5) (make-branch 3 (make-mobile (make-branch 3 2) (make-branch 1 2)))))
(define b (make-mobile (make-branch 4 5) (make-branch 5 (make-mobile (make-branch 2 2) (make-branch 2 2)))))

;a
(define (left-branch structure)
  (car structure))
(define (right-branch structure)
  (car (cdr structure)))
(define (branch-length x)
  (car x))
(define (branch-structure x)
  (car (cdr x)))

;STk> (left-branch a)
;(4 5)
;STk> (right-branch a)
;(3 ((3 2) (1 2)))
;STk> (branch-length (right-branch a))
;3
;STk> (branch-structure (right-branch a))
;((3 2) (1 2))

;b
(define (total-weight x)
  (if (pair? x)
      (+ (total-weight (branch-structure (left-branch x)))
	 (total-weight (branch-structure (right-branch x))))
      x))

;STk> (total-weight a)
;9
;STk> (total-weight b)
;9

;c
(define (balanced? x)
  (cond ((not (pair? x)) #t)
	(else
	 (let ((left_length (branch-length (left-branch x)))
	       (right_length (branch-length (right-branch x)))
	       (l (branch-structure (left-branch x)))
	       (r (branch-structure (right-branch x))))
	   (if (= (* left_length (total-weight l)) (* right_length (total-weight r)))
	       (and (balanced? l) (balanced? r))
	       #f)))))

;STk> (balanced? a)
;#f
;STk> (balanced? b)
;#t

;d
;adding the 2 at the end of procedure to mark that this is a
;different procedure from above
(define (make-mobile2 left right)
  (cons left right))
(define (make-branch2 length structure)
  (cons length structure))

;the only change need is the two selectors below
(define (right-branch2 structure)
  (cdr structure))
(define (branch-structure2 x)
  (cdr x))

;reason for doing so is that the structure of list and cons are different
;illustrated below

;STk> (car (cdr (list 1 2)))
;2
;STk> (cdr (cons 1 2))
;2
;STk> (cdr (list 1 2))
;(2)
;note: (2) is not the number 2, but a list contains 2 as a data
;STk> (car (cdr (cons 1 2)))
;*** Error:
;    car: wrong type of argument: 2
;Current eval stack:
;__________________
;  0    (car (cdr (cons 1 2)))


;;;;;; 2.30
(define (square x) (* x x))

;directly version
(define (square-tree1 tree)
  (cond ((null? tree) nil)
	((pair? tree) (cons (square-tree1 (car tree)) (square-tree1 (cdr tree))))
	(else (square tree))))

;STk> (square-tree1 
;      (list 1
;	    (list 2 (list 3 4) 5)
;	    (list 6 7)))
;(1 (4 (9 16) 25) (36 49))

;using map and recursion
(define (square-tree2 tree)
  (map (lambda (sub-tree)
	 (if (pair? sub-tree)
	     (square-tree2 sub-tree)
	     (square sub-tree)))
       tree))
  
;STk> (square-tree2 
;      (list 1
;	    (list 2 (list 3 4) 5)
;	    (list 6 7) 8 9 10))
;(1 (4 (9 16) 25) (36 49) 64 81 100)


;;;;;; 2.31
(define (square x) (* x x))

(define (tree-map proc sub-tree)
  (map (lambda (sub-tree)
	 (if (pair? sub-tree)
	     (tree-map proc sub-tree)
	     (proc sub-tree)))
       sub-tree))
(define (square-tree3 tree)
  (tree-map square tree))

;STk> (square-tree3
;      (list 1
;	    (list 2 (list 3 4) 5)
;	    (list 6 7)))
;(1 (4 (9 16) 25) (36 49))


;;;;;; 2.32
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
	(append rest (map2 (car s) rest)))))

;notes: name conflict with Exercise 2.30 map
;using map2 instead of map
(define (map2 item old)
  (if (null? (cdr old)) (list (cons item (car old)))
      (append (list (cons item (car old))) (map2 item (cdr old)))))

;STk> (subsets (list 1 2))
;(() (2) (1) (1 2))
;STk> (subsets (list 1 2 3))
;(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

;(map item old) is a procedure which add item to each list in the old.
;for example (map 1 (() (3) (2) (2 3))) should returens ((3) (1 3) (1 2) (1 2 3))
;this is obtained by sign the base case to be (null? (cdr old)), if true,
;for instance, (map 1 ((2))) will return ((1 2))
;if not, (map 1 ((2) (2 3))) will append ((1 2)) to (map 1 ((2 3)))
;notice the careful useage of (list <something>), this is necessary because the form of list of lists

;(subsets s) is a procedure which get the base case first, then go all the way back
;add the privious item in s to the sublist, then append it to the sublist to make a new sublist


;;;;;; 2.36
;book's version of accumulate in page 116
(define (accumulate op initial sequence)
  (if (null? sequence) initial
      (op (car sequence)
	  (accumulate op initial (cdr sequence)))))

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init (form_new_list seqs))
	    (accumulate-n op init (delete_first seqs)))))

(define (form_new_list seqs)
  (if (null? seqs)
      nil
      (cons (car (car seqs))
	    (form_new_list (cdr seqs)))))

(define (delete_first seqs)
  (if (null? seqs)
      nil
      (append (list (cdr (car seqs)))
	      (delete_first (cdr seqs)))))

;STk> (define abc (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
;abc
;STk> (form_new_list abc)
;(1 4 7 10)
;STk> (delete_first abc)
;((2 3) (5 6) (8 9) (11 12))
;STk> (accumulate-n + 0 abc)
;(22 26 30)


;;;;;; 2.54
;equal? is defined in our scheme, so use new_equal? to illustrate
(define (new_equal? arg1 arg2)
  (cond ((and (null? arg1) (null? arg2)) #t)
	((or (null? arg1) (null? arg2)) #f)
	((eq? (car arg1) (car arg2)) (new_equal? (cdr arg1) (cdr arg2)))
	(else #f)))

;STk> (new_equal? '(this is a list) '(this is a list))
;#t
;STk> (new_equal? '(this is a list) '(this (is a) list))
;#f
;STk> (new_equal? '(this is) '(this is a))
;#f