;; 1

(define mymap
  (lambda (f l1 l2)
    (if (null? l1)
	'()
	(cons (f (car l1) (car l2))
	      (mymap f (cdr l1) (cdr l2))))))

;; 2

(define index
  (lambda (n l)
    (if (zero? n)
	(car l)
	(index (sub1 n) (cdr l)))))

;; 3

(define remove
  (lambda (n l)
    (if (zero? n)
	(cdr l)
	(cons (car l) (remove (sub1 n) (cdr l))))))

;; 4

(define insert
  (lambda (new n l)
    (if (zero? n)
	(cons new l)
	(cons (car l) (insert new (sub1 n) (cdr l))))))

;; 5

(define newQueue (lambda () '()))
(define enqueue (lambda (elem q) (reverse (cons elem (reverse q)))))
(define dequeue cdr)
(define next car)

;; 6

;; 7

(define quicksort
  (lambda (lst)
    (if (null? lst)
	'()
	(let ([partitions (partition lst (car lst))])
	  (append (quicksort (car partitions))
	    (append (cadr partitions) (quicksort (caddr partitions))))))))

(define partition
  (lambda (lst num)
    (let ([lessp (filter (lambda (x) (< x num)) lst)]
	  [eqp (filter (lambda (x) (= num x)) lst)]
	  [greaterp (filter (lambda (x) (> x num)) lst)])
      (list lessp eqp greaterp))))

(define filter
  (lambda (predicate lst)
    (if (null? lst)
	'()
	(if (predicate (car lst))
	    (cons (car lst) (filter predicate (cdr lst)))
	    (filter predicate (cdr lst))))))
	
;; 8

(define transf
  (lambda (exp)
    (cond
      [(symbol? exp) exp]
      [(eq? (car exp) 'lambda)
       `(lambda ,(cadr exp) ,(transf (caddr exp)))]
      [(eq? (car exp) 'let)
       (let* ([decls (cadr exp)]
	      [body (caddr exp)]
	      [vars (map car decls)]
	      [rhss (map cadr decls)])
	 `((lambda ,vars ,body) ,@rhss))]
      [else `(,(transf (car exp)) ,(transf (cadr exp)))])))