;; Program designer Austin Guthals
;; Some of these are standard library functions with modifications
;; The rest are of my own creation



;; define a function to return the last element of list  
;;write the definition for rotate, such that 
;; (rotate '(a b c d)) it returns (b c d a)

;; simple recursion

;;write the definition for filter, such that
;; (filter boolean_function list) returns a  list with the elements 
;; satisfying the boolean_function.
;; (filter even? '(1 2 3 4 5 6)) returns (2 4 6)

;;write the definition for remove an element from a list
 ;; (remove 'a '( b s a d r a t))  returns (b s d r t)



;;;using let
;;(let ((x 4)
;;        (y 5))
;;        (+ x y))
;;factorial
 (define fact
    (lambda (n)
      (display "entering ") (display n)
      (let ((result (if (zero? n) 1
                        (* n (fact (- n 1))))))result)
            ))
 ;; filter
 (define (filter boolf ls)
    (cond ((null? ls ) '())
          (else (cons (boolf (car ls)) (filter boolf (cdr ls))))))
 
 (define (remove k ls)
  (cond ((null? ls) '())
        ((eq? (car ls) k) (remove k (cdr ls)))
        (else (cons (car ls) (remove k (cdr ls))))))
  
 
  
 ;; here is where my functions begin

 (define (nequal? ls1 ls2)
   (cond ((equal? ls1 ls2) #f)
         (else #t)))
 
 (define (membr? k ls)
   (cond ((null? ls) '())
         ((eq? k (car ls)) #t)
         (else (membr? k (cdr ls)))))
 
 (define (member? x lis)
   (cond ((list? (membr? x lis)) #f)
         (else #t)))
 
 (define (st? ls)
   (cond ((and (list? ls) (null? ls)) '())
         ((not (member? (car ls) (cdr ls))) (st? (cdr ls)))
         (else #f)))
 
 ;; Tests if list is a set
 ;; Sets are lists without repeats
 (define (set? lis)
   (cond ((list? (st? lis)) #t)
         (else #f)))
 
 ;; Tests if k is an element of set lis
 ;; If lis is not a set then #f will be returned by definition
 (define (element_in_set k lis)
   (cond ((and (set? lis) (member? k lis)) #t)
         (else #f)))
 
 
 ;; Tests if a set is a subset of another
 (define (sbst set1 set2)
   (cond ((and (null? set1) (set? set2)) '()) 
         ((element_in_set (car set1) set2) (sbst (cdr set1) set2))
         (else #f)))
 
(define (subset set1 set2)
   (cond ((list? (sbst set1 set2)) #t)
         (else #f)))

;; Returns union of two sets
;; If the 2 arguments are not set's then
;; the null set is returned.  
;; Note: The union of two null sets is a null set
;; Note: The union of two sets must be a set
;; Order is meaningless in a set

;; This function assumes set1 and set2 are valid sets

(define (set_cons set1 set2)
  (cond ((null? set1) set2)
        ((element_in_set (car set1) set2) (set_cons (cdr set1) set2))
        (else (set_cons (cdr set1) (cons (car set1) set2)))))
                 
(define (union set1 set2)
  (cond ((and (set? set1) (set? set2)) (set_cons set1 set2))
        (else '())))

;; A function that returns Intersection of two sets
;; '() is returned if one of the list's are not a valid set
(define (intersection set1 set2)
  (define r '())
  (cond ((and (set? set1) (set? set2)) (intr set1 set2 r))
        (else '())))
;; The other half of intersection function
(define (intr set1 set2 r)
   (cond ((null? set1) r) 
         ((element_in_set (car set1) set2) 
          (intr (cdr set1) set2 (cons (car set1) r)))
         (else (intr (cdr set1) set2 r))))


;; A function for the difference of two sets
;; notation is A - B
;; since scheme uses infix, I must also, the
;; call will be diff set1 set2
;; instead of - set1 set2 because
;; the - charecter is already used by the
;; math subtraction definintion
;; It is not good programming practice to
;; use function names that already exist.
(define (diff set1 set2)
  (cond ((and (set? set1) (set? set2)) (df set1 set2))
        (else '())))

(define (df set1 set2)
  (define r (intersection set1 set2))
  (cond ((null? r) set1)
        (else (df (remove (car r) set1) set2))))
      
;; Removes all succeding duplicates of elements

(define (remove_duplicates lis)
  (define r '())
  (cond ((set? lis) lis)
        ((eq? (car lis) (car (cdr lis))) (reverse (rmve_duplicates (remove (car lis) lis) (cons (car lis) r))))
        (else  (reverse (rmve_duplicates (cdr lis) (cons (car lis) r))))))

(define (rmve_duplicates ls r)
        (cond ((null? ls) r)
              ((null? (cdr ls)) (cons (car ls) r))
              ((not (eq? (car ls) (car (cdr ls)))) (rmve_duplicates (cdr ls) (cons (car ls) r)))
               (else  (rmve_duplicates (remove (car ls) ls) (cons (car ls) r)))))

;; Does not allow repeats

(define (no_repeats lis)
  (define r '())
  (cond ((set? lis) lis)
        ((eq? (car lis) (car (cdr lis))) (reverse (n_rpts (remove (car lis) lis) r)))
        (else  (reverse (n_rpts (cdr lis) (cons (car lis) r))))))

(define (n_rpts ls r)
        (cond ((null? ls) r)
              ((null? (cdr ls)) (cons (car ls) r))
              ((eq? (car ls) (car (cdr ls))) (n_rpts (remove (car ls) ls) r))
               (else  (n_rpts (cdr ls) (cons (car ls) r)))))

; Leave only one copy of repeated elements
(define (repeats ls)
  (define r (no_repeats ls))
  (define t (diff (remove_duplicates ls) r))
  (cond ((null? '()) t)))

; Count the occurances of each element
(define (count_occurrences lis)
  (define count 0)
  (define temp1 (remove_duplicates lis))
  (define temp2 '())
  (define r 0)
  (cond ((null? '()) (reverse (count_list_elements lis r temp2)))))
        
  (define (count_list_elements ls r t)
    (define q '())
    (cond ((null? ls) t)
          ((null? (cdr ls))
            (cons (cons (+ r 1) (cons (car ls) q)) t))
          ((eq? (car ls) (car (cdr ls))) 
           (count_list_elements (cdr ls) (+ r 1) t))
          (else 
           (count_list_elements (cdr ls) 0 (cons (cons (+ r 1) (cons (car ls) q)) t)))))