CMPU-145, Spring 2013
Asmt. 3
Due:  Thursday, March 7 @ 5:00 p.m.

For this assignment, you will implement some functions related
to partitions, equivalence relations and invertible functions.

1.  Define a function, called RELATIVES, that takes two inputs:
        X, an item from the domain of some relation, and
        LIST-O-PAIRS, a list of pairs representing a relation.
    It should return as its output a list of all the items, Y,
    such that (X,Y) is in the LIST-O-PAIRS (i.e., all Ys that
    are related to X according to the given relation).

    Here are some examples:

      > (relatives 2 '((1 1) (1 2) (2 5) (3 8) (2 4) (2 9) (3 6)))
      (5 4 9)
      > (relatives 2 '((1 1) (2 2) (3 2) (2 4) (1 6)))
      (2 4)

    In the first case, (5 4 9) is output because (2 5), (2 4) and (2 9) 
    are in the relation (i.e., 5, 4 and 9 are the elements that are
    related to 2 in this relation).  In the second case, (2 4) is
    output because (2 2) and (2 4) are in the relation.  Notice that 3
    is not included in the output, even though (3 2) is in the
    relation, because we are only interested in Y values for which (2 Y) 
    is in the relation.

2.  Suppose R is an equivalence relation over some set A.  In class,
    we proved that R determines a corresponding partition of A.  The
    subsets of the partition are determined as follows:

        For each x in A, let Bx = { y | (x,y) is in R }
	(i.e., for each x, let Bx be the "relatives" of x according to R).

    Recall that some of the Bx sets may be equal to one another;
    but that's okay.  

    Define a function, called EQUIV-RELN->PARTITION that takes one
    input, LIST-O-PAIRS, representing a relation over some set A.
    (You may assume that the input relation is an equivalence relation.)
    The output should be the PARTITION determined by the input
    equivalence relation.

        HINT:  Construct the sets Bx using MAP and RELATIVES.
               
        HINT:  See the DOMAIN and REMOVE-DUPES functions 
               attached to the end of these instructions.

        HINT:  If you SORT each subset of the partition, 
               then removing duplicate subsets will be easier.

    Here are some examples:

      > (equiv-reln->partition '((1 1) (1 2) (2 2) (3 3) (2 1)))
      ((3) (1 2))
      > (equiv-reln->partition '((1 1) (3 3) (2 2)))
      ((1) (3) (2))
      > (equiv-reln->partition '((1 2) (1 3) (2 2) (2 3) (3 3)
                                       (1 1) (3 1) (3 2) (2 1)))
      ((1 2 3))

3.  Define a function, called INJECTIVE?, that takes a list-of-pairs
    as its only input.  You may assume that that list-of-pairs is
    a function.  INJECTIVE? should return #t if the input list-of-pairs
    is one-to-one (i.e., injective), as illustrated below:

      > (injective? '((1 a) (2 b) (3 c)))
      #t
      > (injective? '((1 a) (2 b) (3 c) (4 b) (5 e)))
      #f
       

----------------------------------------
 
  ==> Before proceeding, make sure that your code is properly 
      indented and adequately commented!

  ==> Make sure that each function has a CONTRACT (i.e., comments
      that specify the name of the function, its inputs and 
      its output).  Also, make sure that there is a blank line
      between the contract and the function definition!

  ==> Make sure that you do not have long lines of text that
      "wrap around" to the next line!

  ==> Make sure that you have a thorough suite of TESTER expressions
      for each function.  (It is not sufficient to simply include
      the test cases given in these instructions.)
 
  When your functions are working as desired, save your defintions
  file.  Then hit the RUN button one last time.  Then save your
  interactions AS TEXT!!

  Use the ENSCRIPT command to print out your definitions and 
  interactions files.  For example, if your file is named myfile.txt,
  then you should execute the following command in a Terminal window:

     enscript -2jr myfile.txt

  The "-2jr" part specifies double-sided printing, landscape mode, with
  a border.

  Submit a directory containing your definitions and interactions
  files.  The submit directory should also include the "asmt-helper.txt"
  file---but you should *NOT* print out that file!


----------------------------------------------------------
               Some helpful functions
----------------------------------------------------------


;;;  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))))