;;; ==========================
;;;  CMPU-145, Spring 2013
;;;  Asmt. 3 Solutions
;;; ==========================

;;;  Note:  The REMOVE-DUPES and DOMAIN functions were
;;;         provided in the assignment instructions.

;;;  REMOVE-DUPES
;;; ----------------------------
;;;  INPUT:  LISTY, a list of stuff
;;;  OUTPUT:  A list that contains all elements of LISTY, but
;;;           without any duplicates

(define remove-dupes
  (lambda (listy)
    (cond
      ;; Base Case:  LISTY is empty
      ((null? listy)
       ;; No duplicates in the empty list!
       listy)
      ;; Recursive Case 1:  (first listy) is a duplicate
      ((member (first listy) (rest listy))
       ;; So, ignore (first listy) and just remove all
       ;; the duplicates from the rest of the list
       (remove-dupes (rest listy)))
      ;; Recursive Case 2:  (first listy) is NOT a duplicate
      (#t
       ;; So cons it onto whatever the recursive function call
       ;; returns
       (cons (first listy)
             (remove-dupes (rest listy)))))))
       
;;;  DOMAIN
;;; ---------------------------------
;;;  INPUT: LIST-O-PAIRS, a list of pairs representing
;;;            a relation over some set A
;;;  OUTPUT:  A list representing the domain of that relation
;;;             (with no duplicates)

(define domain
  (lambda (list-o-pairs)
    ;; Let MAP do most of the work
    (remove-dupes (map first list-o-pairs))))

;;; ----------------------
;;;  PROBLEM 1
;;; ----------------------

;;;  RELATIVES
;;; -------------------------------------
;;;  INPUT:  A, an element from the domain of a relation
;;;          LIST-O-PAIRS, a relation represented as a list of pairs
;;;  OUTPUT:  A list of the items that are related to A according
;;;           to the given relation (i.e., a list of all Ys such that
;;;           the pair (A Y) is in the relation).

(define relatives
  (lambda (a list-o-pairs)
    (cond
      ;; Base Case:  LIST-O-PAIRS is empty
      ((null? list-o-pairs)
       ;; There are no relatives in the empty relation
       ())
      ;; Recursive Case 1:  A is the first element of the first pair
      ;;   in the relation
      ((eq? a (first (first list-o-pairs)))
       ;; Then the second element of the first pair is a relative of A
       (cons (second (first list-o-pairs))
             (relatives a (rest list-o-pairs))))
      ;; Recursive Case 2:  A is NOT the first element of the first pair
      ;;   in the relation
      (#t
       ;; Thus that pair can be ignored
       (relatives a (rest list-o-pairs))))))

;;;  RELATIVES-ALT
;;; --------------------------------
;;;  An alternative implementation of RELATIVES

(define relatives-alt
  (lambda (a lop)
    ;; The following FILTER expression filters out any #f items 
    ;; contained in the list returned by the MAP expression
    (filter (lambda (y) y)
            ;; The MAP expression walks through the list of pairs
            (map (lambda (pare)
                   ;; If the first element of the pare is A...
                   (if (= (first pare) a)
                       ;; Then keep the second element of the pare...
                       (second pare)
                       ;; Otherwise, return #f
                       #f))
                 lop))))

;;; ----------------------
;;;  PROBLEM 2
;;; ----------------------

;;;  EQUIV-RELN->PARTITION
;;; -----------------------------------------
;;;  INPUT:  LIST-O-PAIRS, a list of pairs representing an equivalence relation
;;;             over some set A
;;;  OUTPUT:  The corresponding partition of A (as a list of lists)

(define equiv-reln->partition
  (lambda (list-o-pairs)
    ;; Remove duplicate lists from the "partition"
    (remove-dupes 
     ;; This MAP expression SORTS all of the subsets created by the
     ;; inner MAP to facilitate the removal of any duplicate subsets (lists)
     (map (lambda (subbie)
            (sort subbie <))
          ;; The following MAP expression constructs a list of the
          ;; sets Bx, as described in the instructions.
          ;; Note that some of the Bx subsets may be the same
          (map (lambda (a) (relatives a list-o-pairs))
               (domain list-o-pairs))))))
  

;;; ----------------------
;;;  PROBLEM 3
;;; ----------------------

;;;  INJECTIVE?
;;; ---------------------------------------------
;;;  INPUT:  LOP, a list of pairs, representing a function from some A to B
;;;  OUTPUT:  #t if that function is one-to-one (i.e., injective); #f otherwise

(define injective?
  (lambda (lop)
    (let* (;; INVERSE-RELN: the inverse of the LOP relation
           (inverse-reln (map reverse lop))
           ;; RANGE-LOP:  the range of the LOP relation = the domain of its inverse
           (range-lop (domain inverse-reln)))
      (null?
       ;; The FILTER expression gets rid of any 1s in the list computed by
       ;; the MAP expression.  If the function is injective, then the list
       ;; returned by the MAP expression will be only 1s; thus, after the filter
       ;; operation, the list will be empty. 
       (filter (lambda (x) (not (= x 1)))
               ;; The following MAP expression walks through the list of RANGE values
               (map (lambda (b) 
                      ;; For each B in the range of the relation, it uses RELATIVES
                      ;; to fetch all of the As such that (A B) is in the relation
                      ;; (i.e., (B A) is in the inverse relation).
                      ;; The LENGTH function computes the NUMBER of relatives for
                      ;; each B.  (We hope the number is 1!!!)
                      (length (remove-dupes 
                               (relatives b inverse-reln))))
                    range-lop))))))