;;;
;;; solution1.lisp: Solution for selected exercises in LISP tutorial 1
;;; Philip W. L. Fong
;;; SFU CMPT 310 (2001-1)
;;;

;;
;; Control Structures: Recursions and Conditionals
;;

(defun triangular (N)
  "Compute the N'th triangular number."
  (if (= N 1)
      1
    (+ N (triangular (- N 1)))))

(defun power (B E)
  "Raise B to the E'th power."
  (if (zerop E)
      1
    (* B (power B (- E 1)))))

;;
;; Multiple Recursions
;;

(defun binomial (N R)
  "Compute binomial coefficient B(N, R)."
  (if (or (zerop R) (= N R))
      1
    (+ (binomial (- N 1) (- R 1)) 
       (binomial (- N 1) R))))

;;
;; Programming with Lists
;;

(defun sum (L)
  "Compute the sum of all members in a list L of numbers."
  (if (null L)
      0
    (+ (first L) (sum (rest L)))))

;;
;; Example: nth
;;

(defun list-last (L)
  "Return the last cons structure in a list L."
  (if (null L)
      nil
    (if (null (rest L))
	L
      (list-last (rest L)))))

;;
;; Example: append
;;

(defun list-butlast (L)
  "Return L with last element removed."
  (cond
   ((null L) nil)
   ((null (rest L)) nil)
   (t (cons (first L) (list-butlast (rest L))))))

;;
;; Using Lists as Sets
;;

(defun list-union (L1 L2)
  "Return a list containing elements belonging to either L1 or L2."
  (cond
   ((null L1) L2)
   ((list-member (first L1) L2)
    (list-union (rest L1) L2))
   (t (cons (first L1) (list-union (rest L1) L2)))))

(defun list-difference (L1 L2)
  "Return a list containing elements belonging to L1 but not L2."
  (cond
   ((null L1) nil)
   ((list-member (first L1) L2)
    (list-difference (rest L1) L2))
   (t (cons (first L1) (list-difference (rest L1) L2)))))