Lab 3 Instructions
CMPU 145, Spring 2019
If you want to, you may work in pairs for this lab. Every individual
must write the code and submit the lab separately. Please indicate,
at the top of your definitions file, who you worked with, if you worked
with another person.
But before you begin, let's review some helpful details together:
Preface: a review of "map" and "andmap"
---------------------------------------
We've seen that Racket's MAP function can make problems easier, without
needing to define a recursive function. MAP takes two inputs: a function
and a list of potential inputs for the function. It applies the function
to each element in the list and returns a list of the results, e.g.,
> (map even? '(1 2 3 4))
'(#f #t #f #t)
> (map (lambda (x) (* x x))
'(1 2 3 4))
'(1 4 9 16)
We've also seen andmap in a recent lab related lecture. ANDMAP applies
a predicate to each item of a list. ANDMAP will return a boolean value.
That is, if the result of applying a predicate to any of the items in
the list is false, then ANDMAP will return #f. Otherwise it will
return #t. We also saw that DrRacket will employ short-circuiting when
applying the predicate. Examples:
> (andmap even? '(2 4 6 8))
#t
> (andmap even? '(2 4 7 3 0))
#f
> (andmap odd? '(1 3 7 9 5 -3))
#t
> (andmap odd? '(1 3 7 8 5 -3))
#f
Our main goal is to write a function that determines if a given relation,
defined by a list representing that relation, is an equivalence
relation. As we know, there are three components, or helper functions,
that will help us with that determination.
A) reflexive?
---------------------
The first function is super easy, especially with these hints.
The base case pseudo-code:
For a relation to be reflexive, it can be empty, "or..."
Remember, the output must be #t or #f and we know of a couple of
basic operators/functions that can do the job for us.
The recursive case pseudo code:
... the pair (A A) must be in the relation for all A's in SET-A
i.e. the list (i.e. pair) that is recursively generated from the first element in SET-A
must also exist in RELN. The diy-member? function sill tell us if this is so.
But: What does it mean in terms of code for "all As" in SET-A?
You will have to create an appropriate set of tester test cases.
I am instructing the coaches to make sure there are necessary and
sufficient test cases to test the reflexive? function.
What is the minimum right number of test cases? Is it > 1? > 2? More?
What does the input look like? RELN is a list of lists and SET-A
is a single list.
Note: member? exists in DrRacket, but an error occurred trying to use
the existing function. A diy-member? that does the heavy lifting is
included.
B) symmetric?
---------------------
Define a function, called SYMMETRIC?, that takes as its only input a list
of pairs representing a binary relation. It should return as its output a
boolean value (i.e., #t or #f) indicating whether the given relation is
symmetric, similar to reflexive?. A sample:
> (symmetric? '((1 2) (3 3) (2 1)))
#t
> (symmetric? '((1 2) (3 4) (2 1) (4 5) (4 3)))
#f
Notes:
- Lab 2's INVERSE function is closely related (!) to this function.
- ANDMAP provides a simple way to code this function, but you are not bound
to using it. Still it is rather simple, given that the diy-member? function
can be used in a similar way that it was used for the reflexive? function.
- What should the code return if (a,b) is a pair such that a = b?
C) Transitive?
----------------------
Define a function called TRANSITIVE? that takes a list of PAIRS as its
only input. That list of pairs represents a binary relation. The
TRANSITIVE? function should return #t if that binary relation is transitive,
as illustrated below.
> (transitive? '((1 2) (2 3) (1 3)))
#t
> (transitive? '((1 3) (1 2) (2 3)))
#t
> (transitive? '((1 2) (2 3)))
#f
> (transitive? '((1 1) (1 2) (2 1) (2 2) (3 3)))
#t
> (transitive? '((1 2) (3 3) (2 2) (2 1) (1 1)))
#t
> (transitive? '((2 3) (3 3) (1 2) (1 1)))
#f
Suggested Approach:
1. Let a let guide you towards getting your A,B,C,D.
2. Pseudo-code that restates the definition of a transitive
relation:
For each pair (A,B) in R,
For each pair (C,D) in R,
Either B is not equal to C
OR the pair (A,D) is in R.
Notice that the overall structure of this is:
For each pair (A,B) in R,
SOME-PROPERTY-HOLDS
where "SOME-PROPERTY-HOLDS" is a place-holder for all the
rest of the stuff.
Since R is a list of pairs, "AND___" we want to walk through
that list of pairs verifying that a certain property holds,
there is a pretty good function described in the preface
that does this!
So, if PAIRS is a list of pairs representing the relation,
all you need to do is come up with a function that checks
whether SOME-PROPERTY-HOLDS for any given pair (A,B).
But... SOME-PROPERTY-HOLDS has the following form:
For each pair (C,D) in R,
SOME-OTHER-PROPERTY-HOLDS!
This, too, can be dealt with using ANDMAP to walk through the
list of pairs, (C,D). You just need to figure out the
function that checks whether "SOME-OTHER-PROPERTY-HOLDS". But
that's just the bit about "Either B is not equal to C, OR the
pair (A,D) is in R" in the pseudo-code above.
Problem: Equiv-Reln?
----------------------
Define a function, called EQUIV-RELN?, that takes two inputs:
RELN, a list of pairs representing a relation over some set A, and
SET-A, a list representing the set A.
It should return #t if that relation is an equivalence relation.
This problem is super easy given all of the helper functions above.
> (equiv-reln? '((1 1) (2 2) (3 1)) '(1 2 3))
#f
> (equiv-reln? '((1 1) (1 2) (2 1) (2 2) (3 3)) '(1 2 3))
#t
----
A real test should use TESTER expressions that thoroughly tests you code.
When you are done, ask a coach to come over to check your work.
Apparently, there was a flaw in the way I've been setting up submissions for the
submit145 command. Try submitting the directory containing your definitions
and interactions files using the submit145 command as follows it might
actually work!
submit145 lab3 my-lab3-directory