;; PROBLEM 1

(define (demote-root tree ls)
  (if (null? ls)
      tree
      (let ((node-to-swap (list-ref (children tree) (car ls))))
	(make-tree (datum node-to-swap)
		   (demote-root-forest (children tree) (cdr ls) (car ls) (datum tree))))))

(define (demote-root-forest forest ls i new-datum)
  (if (= i 0)
      (cons (demote-root (make-tree new-datum (children (car forest))) ls)
	    (cdr forest))
      (cons (car forest) (demote-root-forest (cdr forest) ls (- i 1) new-datum))))


;; PROBLEM 2
#|

1. (1 3 3 7)

2. #f

|#

;; PROBLEM 3

#|
   +---+---+             +---+---+  +---+---+
-->| . |  -|------------>| . |  -|->| . | / |
   +-|-+---+             +-|-+---+  +-|-+---+
     v                     v          v
   +---+---+  +---+---+  +---+---+    4
   | . |  -|->| . | / |  | . | . |
   +-|-+---+  +-|-+---+  +-|-+-|-+
     v          v          v   v
     1          3          2   3

((1 3) (2 . 3) 4)

=====

   +---+---+
-->| . | / |
   +-|-+---+
     v
   +---+---+  +---+---+
   | . |  -|->| . | / |
   +-|-+---+  +-|-+---+
     v          v
     3          4

((3 4))

=====

     +---------------------+
     |                     |
     v                     |
   +---+---+  +---+---+  +-|-+---+  +---+---+
-->| . |  -|->| . |  -|->| . |  -|->| . | / |
   +-|-+---+  +-|-+---+  +---+---+  +-|-+---+
     v          v                     v
     1          2                     4

(1 2 (1 2 (1 2 [...]

=====

     +----------+
     |          |
     |          v
   +-|-+---+  +---+---+     +---+---+
-->| . |  -|->| . | . |     | . | / |
   +---+---+  +-|-+-|-+     +-|-+---+
                v   v         v
		2   5         3

((2 . 5) 2 . 5)

=====

   +---+---+  +---+---+  +---+---+
-->| . |  -|->| . |  -|->| . | / |
   +-|-+---+  +-|-+---+  +-|-+---+
     |          v          v
     |          2          3
     v
   +---+---+  +---+---+  +---+---+
   | . |  -|->| . |  -|->| . | / |
   +-|-+---+  +-|-+---+  +-|-+---+
     v          v          v
     a          d          c

((a d c) 2 3)
|#

;; PROBLEM 4

;; Normal order: 4
;; Applicative order: 3

#|
Normal order:
    (foo (* 2 2) (square 3))
    (+ (* 2 2) (* (square 3) (square 3)))
    (+ (* 2 2 (* (* 3 3) (* 3 3)))

Applicative order:
    (foo (* 2 2) (square 3))
    (foo (* 2 2) (* 3 3))
    (foo 4 9)
    (+ 4 (* 9 9)) 
|# 

;; Problem 5
#|
There are two types of numbers that we can call foo with, even and odd numbers.
In the even case, we immediately call mystery with that even number.
When x is even in mystery, we make two recursive calls: (mystery (- x 1)) and (mystery (- x 2)).
The first thing to notice is that (mystery (- x 1)) takes O(n) time, since the new x is now odd.
(mystery (- x 2)) means that we need to call (mystery (- x 1)) and (mystery (- x 2)) again, since
x is even again.
Thus, each time mystery sees an even number, a runtime of n/2 is required (for the call to 
(mystery (- x 1))), n/2 times (since there are n/2 recursive even calls).  Thus,
mystery is O(n^2 /4) = O(n^2)

In the odd case, we add one to n, which means mystery is called with an even number, which
results in O(n^2) as previously described.
|#

;; PROBLEM 6

(define (sent-fn fn ls-of-sents)
  (map (lambda (sent) (every fn sent)) ls-of-sents))

;; It's important to make sure that you use map and then every; swapping them around or using
;; one instead of the other would be a data abstraction violation.

;; PROBLEM 7

(define (make-nested parens end-with)
  (if (= parens 0)
      end-with
      (lambda () (make-nested (- parens 1) end-with))))

;; PROBLEM 8

(define-class (set-of-numbers)
  (instance-vars (nums '()))
  (method (add n)
    (if (not (member n nums))
	(set! nums (cons n nums))))
  (method (remove n)
    (set! nums (remove n nums)))
  (method (remove-all set)
    (for-each
      (lambda (n) (ask self 'remove n))
      (ask set 'nums))))

;; PROBLEM 9

(define (deep-car? elem ls)
  (define (helper ls elem flag)
    (cond ((null? ls) #f)
	  ((and (equal? (car ls) elem) flag) #t)
	  ((list? (car ls)) (or (helper (car ls) elem #t)
				(helper (cdr ls) elem #f)))
	  (else (helper (cdr ls) elem #f))))
  (helper ls elem #t))

;; PROBLEM 10

;; We recommend using envdraw on the inst machines to determine the
;; answer to this question.
;; To review environment diagrams, check out the rules posted online:
;; http://www-inst.eecs.berkeley.edu/~cs61a/su10/reading/EnvDiagramRules.pdf


;; PROBLEM 11

(define (list-rotate! n ls)
  (if (= n 0)
      ls
      (let ((next (cdr ls)))
	(set-cdr! (last-pair ls) ls)
	(set-cdr! ls '())
	(list-rotate! (- n 1) next))))
	     

;; PROBLEM 12
#|
> (f 2)
(3 6 (2 4) (1 4))

> (g 1)
(4 5 (3 5 4) (2 5 4))

> (f 2)
(5 6 (4 3 5 7) (1 7))

> (g 1)
(6 5 (5 4 3 8 7) (2 8 7))
|#

;; PROBLEM 13
#|
1. (if (= 2 2) 3 4) will still return 3. Note that in MCEval, true has been redefined to
false, but the true? and false? predicates use the STk version of true and false. This
means that the new MCEval bindings of true to be false won't actually break all that much;
for instance, this if statement still returns the correct value.

2a. We would modify apply, since we want to change how environments are extended. (Extending
    environments is done inside apply).

 b. There were a number of ways that you could accomplish this; we chose to modify
    extend-environment.

 c. (define (extend-environment vars vals base-env)
      (if (null? vars) ; Use the base environment, don't make a new frame
          base-env
          [Rest of the old extend-environment]))

 d. The reason this doesn't work is because of the way we decide whether or not a frame will
    be empty. Specifically, we say a frame will be empty when the procedure we are applying
    takes no arguments. However, this doesn't mean the frame will NEVER contain variables.
    Take the following code:
      
        > (define (foo) (define bar 3))
        foo
       
        > bar
        3

    In normal mc-eval, this snippet of code would cause an error. The binding of bar should
    go in the frame created when we call foo; however, since foo takes no arguments, we will
    never create a frame, and the binding goes in the global environment instead.