;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                       CSE 505 HW1 sample solutions
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; 1.

;; recursively increment LOW until it exceeds HIGH
(define (range low high)
  (if (> low high) () (cons low (range (+ low 1) high))))


;; 2.

;; No, the above function is not tail-recursive, since it does work (i.e. 
;; cons) after the recursive call returns.

;; The tail recursive version is as follows:

;; range-aux is the local function that does the work
;; it was more natural here to recursively decrement HIGH until it
;; is less than LOW
;; RES stores the result being computed
(define (range-tr low high)
  (define (range-aux low high res)
    (if (< high low) res (range-aux low (- high 1) (cons high res))))
  (range-aux low high ()))


;; 3.

;; No, because the two recursive calls can't both be made tail
;; recursive; one has to be done and then the other, so one must come
;; after the other, violating the tail recursion restriction.

;; If an auxiliary data structure is allowed, however, a tail-
;; recursive version can be written by creating an explicit stack
;; (represented as a list) to replace the non-tail-recursive call.
;; Essentially, you have to keep around a list of those parts of the
;; tree which still need to be traversed.  When you've finished
;; traversing the current part, you start on the rest.

;; leaf predicate defined in the handout
(define (leaf? s) (not (or (pair? s) (null? s))))

;; sum-tree-aux is the helper function that does the work.
;; REST is essentially a list of parts of the tree that have yet to be
;; processed.  RES stores the sum being computed.
(define (sum-tree-tr tree)
  (define (sum-tree-aux tree rest result)
    (cond ((null? tree) result)
	  ((leaf? tree) (sum-tree-aux rest () (+ tree result)))
	  ((pair? tree) (sum-tree-aux (car tree) (cons (cdr tree) rest) result)
	   )))
  (sum-tree-aux tree () 0))


;; 4.

;; like REDUCE, but you have two paths to recur on 
(define (tree-reduce fun id leaf-val t)
  (cond ((null? t) id)
	((leaf? t) (leaf-val t))
	((pair? t) (fun (tree-reduce fun id leaf-val (car t))
			(tree-reduce fun id leaf-val (cdr t))))))


;; 5.
;; NOT REQUIRED


;; 6.

;; bind (3 4) to a name so it can be referenced several times
(let ((tmp '(3 4)))
  (list tmp (cdr tmp)))


;; 7.

;; a points to (list b 'bob)
;; b points to a cons cell (cons 'new <itself>)

             a--+
                |
                |
    _______     V_______      _______
   |   |   |--->|   |   |--->|   |   |---> nil
    -------      -------      -------
     |            |            |
     |            |            |
     V            |            V
     hi           |            bob
                  |
                  |
                  |  +---------------+
                  |  |               |
                  |  +--> _______    |
                  +----->|   |   |---+
             b----------> ------- 
                           |
                           |
                           V
                           new

;; 8.

Recursive programs often pass parts of their data structures as
arguments to recursive calls.  This is easier to do with lists
because one pointer to its first cons cell is sufficient.  For
arrays, one needs to pass the array itself (including its size) and
the index of the first element.

Also, lists are a recursive data structure, and recursive
algorithms are often easier to express in terms of recursive data
structures.