#|

Some more examples in Lisp.

|#



;; building up a list of answers while recursing over a list

(defun doubles (xs)
  "doubles each item of xs"
  (if (null xs) NIL
      (cons (* 2 (first xs)) (doubles (rest xs)))))

(defun mult5s (xs)
  "multiplies each value by five."
  (if (null xs) NIL
      (cons (* 5 (first xs)) (mult5s (rest xs)))))

(defun copies (xs)
  "duplicates each value in the list after itself"
  (if (null xs) NIL
      (cons (first xs) (cons (first xs) (copies (rest xs))))))

(defun ones-len (xs)
  "replacesw every item with a 1."
  (if (null xs) NIL
      (cons 1 (ones-len (rest xs)))))

;; folding a list down

(defun multiply (xs)
  (if (null xs) 1
      (* (first xs) (multiply (rest xs)))))

(defun max-value (xs)
  (cond ((null xs) NIL)
	((null (rest xs)) (first xs))
	(T (let (
		 (rest-best (max-value (rest xs)))
	         (here      (first xs)))
	     (if (null rest-best) here
		 (if (> here rest-best) here rest-best))))))

(defun keep-evens (xs)
  (if (null xs) NIL
      (if (evenp (first xs)) (cons (first xs) (keep-evens (rest xs)))
	  (keep-evens (rest xs)))))


;; recursion with helper function versions
(defun keep-odds-helper (ans xs)
  (if (null xs) ans
      (if (oddp (first xs)) (keep-odds-helper (append ans (list (first xs))) (rest xs))
	  (                  keep-odds-helper ans                            (rest xs)))))

(defun keep-odds (xs)
  (keep-odds-helper NIL xs))



(defun avg-helper (count sum xs)
  "tracks the number of items and the sum"
  (if (null xs) (cons count sum) ;; NOTE: THIS ISN'T REALLY A LIST... IT'S A PAIR!
      (avg-helper (+ 1 count) (+ sum (first xs)) (rest xs))))

(defun avg (xs)
  (let* (
	 (my-pair (avg-helper 0 0 xs))
	 (the-count (first my-pair)) ;; NOTE: NOT A LIST... 1nd value in the pair.
	 (the-sum (rest my-pair)))   ;; NOTE: NOT A LIST... 2nd value in the pair.
    (if (= 0 the-sum) NIL
	(/ the-sum the-count))))

(defun zipper (xs ys)
  (cond ((null xs) NIL)
	((null ys) NIL)
	(T (cons (cons (first xs) (first ys)) (zipper (rest xs) (rest ys))))))

;; insertion sort

(defun insert-one (v xs)
  "inserts one number in increasing order."
  (if (null xs) (cons v NIL)
      (if (> v (first xs)) (cons (first xs) (insert-one v (rest xs)))
	  (cons v xs))))

(defun insert-helper (ans todo-list)
  "insert everything from our todo-list into ans"
  (if (null todo-list) ans
      (let ((one-more-placed (insert-one (first todo-list) ans)))
	(insert-helper one-more-placed (rest todo-list)))))

(defun insertion-sort (xs)
  (insert-helper NIL xs))