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

;;
;; Tail Recursions
;;

(defun fast-triangular (N)
  "Compute the N'th triangular number."
  (fast-triangular-aux N 1))

(defun fast-triangular-aux (N A)
  "Compute the product of A and the N'th triangular number."
  (if (= N 1)
      A
    (fast-triangular-aux (1- N) (+ N A))))

(defun fast-power (B E)
  "Raise B to the E'th power."
  (fast-power-aux B E 1))

(defun fast-power-aux (B E A)
  "Compute the product of A and the E'th power of B."
  (if (zerop E)
      A
    (fast-power-aux B (1- E) (* B A))))

(defun fast-list-length (L)
  "Compute the length of list L."
  (fast-list-length-aux L 0))

(defun fast-list-length-aux (L A)
  "Compute the sum of A and the length of list L."
  (if (null L)
      A
    (fast-list-length-aux (rest L) (1+ A))))

;;
;; Lambda Expressions
;;

(defun apply-func-list (L X)
  "Apply a list L of functions to object X."
  (if (null L)
      X
    (funcall (first L) (apply-func-list (rest L) X))))

;; 10 times the fourth element of the list (10 20 30 40 50)
(apply-func-list (list #'(lambda (N) (* 10 N)) #'fourth) '(10 20 30 40 50))

;; the third element of the second element in the list 
;; ((1 2) (3 4 5) (6))
(apply-func-list (list #'third #'second) '((1 2) (3 4 5) (6)))

;; the difference between 10 and the length of (a b c d e f)
(apply-func-list (list #'(lambda (N) (- 10 N)) #'list-length) '(a b c d e f))

;; a list containing a list containing the symbol 'blah
(apply-func-list (list #'list #'list) 'blah)

;;
;; Search Iteration
;;

(defun find-nonempty (L)
  "Given a list L of lists, return the leftmost nonempty member."
  (if (null L)
      nil
    (if (not (null (first L)))
	(first L)
      (find-nonempty (rest L)))))

(defun find-long-list (L)
  "Given a list L of lists, return the leftmost member with length at least 3."
  (find-if #'(lambda (X) (>= (list-length X) 3)) L))

(defun find-even-list (L)
  "Given a list L of lists, return the leftmost member with even length."
  (find-if #'(lambda (X) (evenp (list-length X))) L))

(defun find-divisible-by-three (L)
  "Given a list L of numbers, return the leftmost member that is divisible by 3."
  (find-if #'(lambda (X) (zerop (rem X 3))) L))

;;
;; Filter Iteration
;;

(defun list-remove-if (P L)
  "Return a list containing all elements of list L except for those satisfying predicate P."
  (if (null L)
      nil
    (if (funcall P (first L))
	(list-remove-if P (rest L))
      (cons (first L) (list-remove-if P (rest L))))))

(defun list-difference (L1 L2)
  "Compute the difference of lists L1 and L2."
  (remove-if #'(lambda (X) (member X L2)) L1))

;;
;; Functions Returning Multiple Values
;;

(defun list-min-max (L)
  "Given a list L of numbers, return two values, the minimum and the maximum members of L."
  (if (null L)
      (values nil nil)
    (list-min-max-aux (rest L) (first L) (first L))))

(defun list-min-max-aux (L MINIMUM MAXIMUM)
  "Given a list L of numbers, return (min LMIN MINIMUM) and (max LMAX MAXIMUM), where LMIN and LMAX are the minimum and maximum members of L respectively."
  (if (null L)
      (values MINIMUM MAXIMUM)
    (list-min-max-aux (rest L) 
		      (min (first L) MINIMUM) 
		      (max (first L) MAXIMUM))))