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