Assignment 14
Due Date Thursday 03/21 at 9pm
Purpose To practice working with list abstractions and lambda.
You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions. Failure to submit a .rkt file will result in a 0.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
Your code MUST conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
You must follow all the steps of the design recipe when completing this assignment.
Please be sure to look at the feedback for assignment 11 before submitting, as we will be grading you more harshly on things we have warned you about before.
You must submit this assignment with your partner. Please make sure you can submit with your partner before 5pm on Thursday or we cannot guarantee that you will be able to submit your homework before the deadline. If the course staff are unable to assist you after 5pm and this causes your homework to be late we will not grant an extension.
Encoding Booleans
Alonzo Church is the creator of lambda calculas and believed that all you need to create a programming language is lambda. He showed how to encode numbers as functions (think of the Repeaters from the last assignment) but he also showed how to encode Booleans as functions.
; A ChurchBoolean is a function [X X -> X] ; Which represents a boolean ; church-true : ChurchBoolean ; Returns the first argument (represents #true) (check-expect (church-true 3 4) 3) (check-expect (church-true 2 1) 2) (define (church-true x y) x) ; church-false : ChurchBoolean ; Returns the second argument (represents #false) (check-expect (church-false 3 4) 4) (check-expect (church-false 2 1) 1) (define (church-false x y) y)
Exercise 1 Design the function church->boolean which, given a ChurchBoolean produces the actual boolean it represents. This function will allow us to test further exercises.
Exercise 2 Design the function church-and which, given two ChurchBooleans produces the ChurchBoolean representation of #true if both ChurchBooleans represent #true. You should not use church->boolean or actual Booleans except in your check-expects.
Exercise 3 Design the function church-or which, given two ChurchBooleans produces the ChurchBoolean representation of #true if at least one of the ChurchBooleans represents #true. You should not use church->boolean or actual Booleans except in your check-expects.
Exercise 4 Design the function church-not which, given a ChurchBoolean produces the opposite ChurchBoolean. You should not use church->boolean or actual Booleans except in your check-expects.
Existing list abstractions
You MUST use existing abstractions where appropriate in the following exercises.
Exercise 5 Design the function parity-matrix which, given a natural number n, produces an nxn matrix (list of lists) of Boolean values. The entry in row i and column j should be #true if i+j is an even number. Otherwise it should be #false.
Exercise 6 Design the function cartesian-product which, given two lists, produces a list of all possible pairs of elements where the first element of the pair comes from the first list and the second element of the pair comes from the second list. So, for example (cartesian-product (list "a" "b" "c") (list 1 2)) should produce (list (list "a" 1) (list "a" 2) (list "b" 1) (list "b" 2) (list "c" 1) (list "c" 2)).
Exercise 7 As it turns out, many of the pre-defined abstractions we know and love can take more than one input list, so long as the list lengths are the same and the function given can take as many arguments as there are lists. Armed with this knowledge, as well as lambda, design a function hyphenate, which given two lists of strings (assumed to be of the same length), produces a list of strings, where each element is of the form "s1-s2", where "s1" is originally from the first given list and "s2" is originally from the second given list. Note this means the first element from the first list is paired with the first from the second, the second is paired with the second, etc (i.e., this is not the cartesian product).
(define-struct pet [name species age]) ; A Pet is a (make-pet String String Nat) ; - where name is the pet's name ; - species is the pet's species ; - and age is the pet's age (in years)
Exercise 8 Design the function same-pet-name? which takes two Pets and returns #true if the pets have the same name. NOTE: Since this function does not involve lists, you do not need to use a list abstraction to design it.
Exercise 9 Design the function any-same-pet-name? which takes a [List-of Pet] and returns #true if any pets in the list share a name.