;;;; Miscellaneous Recursive Functions
;;;;
;;;; File:         functions.lsp
;;;; Assignment:   1
;;;; Author:       <your name> (<your e-mail address>)

;; You MUST use pure LISP (no SETF's) AND RECURSION
;; (no DO's) to implement the following functions.

;; You should write the LISP rewrite equations
;; for the functions before you write the code.

;; You MUST indent your code in a proper readable
;; fashion.  Learn to use == and =% in vi.

;; The Fibonacci function.
;;
;;     f (0) ===> 0
;;     f (1) ===> 1
;;     f (n) ===> f(n-1) + f(n-2)   if n > 1
;;
;; RR: <replace this with your rewrite rules>
;;
;;
;;
(defun fibonacci (n)
  ) ; Replace this line with your code.



;; Function that copies an s-expression replacing each
;; atom other than NIL with either 'SYMBOL or 'NUMBER
;; according to the type of the atom.
;;
;; E.g.: (copy-types '(+ (x 8) (nil y (z)))) ===>
;;	      '(symbol (symbol number)
;;		       (nil symbol (symbol)))
;;
;; RR: <replace this with your rewrite rules>
;;
;;
;;
(defun copy-types (e)
  ) ; Replace this line with your code.



;; Function that takes two lists of atoms and returns
;; the order-preserving sublist of the first list that
;; contains all elements of the first list that are also
;; in the second list.  You must NOT use the COMMONLISP
;; intersection function.
;;
;; E.g.: (my-intersection '(1 2 3) '(2 3 4)) ===> '(2 3)
;;       (my-intersection '(1 2) '(3 4)) ===> '()
;;       (my-intersection '(x y) '(y x)) ===> '(x y)
;;       (my-intersection '(x y z w) '(y x)) ===> '(x y)
;;
;; RR: <replace this with your rewrite rules>
;;
;;
;;
(defun my-intersection (list1 list2)
  ) ; Replace this line with your code.



;; Function that returns true if and only if some
;; non-nil atom inside an s-expression (the first
;; argument) satisfies a predicate (the second
;; argument).
;;
;; E.g.: (look-into '(1 8 (2 4 (x)) 9) #'symbolp)
;;                           ===> t
;;       (look-into '(1 8 (2 4 (7)) 9) #'symbolp)
;;                           ===> nil
;;       (look-into '(5 8 (2 4 (3)) 9)
;;                  #'(lambda (n) (< n 3))) ===> t
;;       (look-into '(5 8 (7 4 (3)) 9)
;;                  #'(lambda (n) (< n 3))) ===> nil
;;
;; RR: <replace this with your rewrite rules>
;;
;;
;;
(defun look-into (list predicate)
  ) ; Replace this line with your code.