; Question 1
; For the tail recursive version, the coefficients should be in the order of
; highest to lowest power of x.

(define (eval-poly x coeff)
  (define (eval-poly-helper acc coeff)
    (if (null? coeff) acc
        (eval-poly-helper (+ (* acc x) (car coeff)) (cdr coeff))
    )
  )
  (eval-poly-helper 0 coeff)
)


; Question 2

; Part a

; Identity function

(define (identity x) x)


; tree-fold
; op is the function to apply recursively to internal nodes.
; leaf-op is the function to apply to leaf nodes.
; id is the value to return for empty sub-trees.

(define (tree-fold op leaf-op id tree)
  (define (tree-fold-helper tree)
    (cond ((null? tree) id)
          ((pair? tree) (op (tree-fold-helper (car tree))
                            (tree-fold-helper (cdr tree))))
          (else (leaf-op tree))
    )
  )
  (tree-fold-helper tree)
)


; Part b

(define (flatten tree) (tree-fold append list '() tree))

(define (sum-tree tree) (tree-fold + identity 0 tree))


; Question 3

; Compose function

(define (compose f g) (lambda (x) (f (g x))))


; Binary tree abstract data type constructor and selectors

(define make-tree list)
(define (empty-tree) '())
(define empty-tree? null?)

(define tree-data car)
(define tree-left-child cadr)
(define tree-right-child caddr)


; Symbol and value selectors

(define make-data list)
(define data-symbol car)
(define data-symbol-as-string (compose symbol->string car))
(define data-value cadr)


; Symbol table operations

(define not-found-symbol 'symbol-not-found)

; The following are redundant but will help us to modify the program if the
; underlying binary tree data structure is changed.

(define table-data tree-data)
(define empty-table? empty-tree?)
(define make-table make-tree)

(define table-left-child tree-left-child)
(define table-right-child tree-right-child)


; search abstracts the structure of lookup and contains, making them easy to
; express succinctly.

(define (search table sym not-found found-func)
  (let ((sym-as-string (symbol->string sym)))

    (define (search-helper table)
      (if (empty-table? table) not-found

          (let* ((data (table-data table))
                 (string (data-symbol-as-string data)))

                (cond ((string<? string sym-as-string)
                        (search-helper (table-left-child table)))
                      ; sym would be found in the left sub-tree

                      ((string>? string sym-as-string)
                        (search-helper (table-right-child table)))
                      ; sym would be found in the right sub-tree

                      (else (found-func data))
                      ; sym has been found
                )
          )
      )
    )
  (search-helper table)
  )
)


; lookup

(define (lookup table sym) (search table sym 'symbol-not-found data-value))


; insert
; If the symbol is already in the table, the existing value associated with it
; gets replaced by the new value.

(define (insert table sym value)
  (let ((sym-as-string (symbol->string sym)))

    (define (insert-helper table)
      (if (empty-table? table)
          (make-table (make-data sym value) (emptytable) (emptytable))

          (let* ((data (table-data table))
                 (left-child (table-left-child table))
                 (right-child (table-right-child table))
                 (string (data-symbol-as-string data)))

                (cond ((string<? string sym-as-string)
                       (make-table data (insert-helper left-child) right-child))

                      ((string>? string sym-as-string)
                       (make-table data left-child (insert-helper right-child)))

                      (else (make-table (make-data sym value) left-child
                             right-child))
                )
          )
      )
    )
  (insert-helper table)
  )
)


; contains

(define (contains table sym) (search table sym #f (lambda (x) #t)))


; emptytable

(define (emptytable) (empty-tree))