In this project you will be asked to implement a number of functions recursively. Note that most of these functions are built into DrRacket, however you should not use them in your solutions. In this project we are looking for elegant code, work on making your recursion as clear and simple as possible. Remember that we have a lot of recursion tools at our disposal: list recursion, numeric recursion, tail recursion, and letrec.
Throughout this project, you should use good programming techniques that we have discussed so far including
let and let*)For this assignment, create one single file titled recursion-practice.rkt. Include your answers to all parts in this single file. Your file should contain a header (see example below), and should clearly label the various parts and subproblems using comments. Make sure to organize the file so that it’s easy for another human (e.g. your professor,mentors, graders) to read it. Turn in your file on Gradescope, and attempt to fix any errors that appear from the autograder.
# lang racket
(require rackunit)
(require csc151)
; recursion-practice.rkt
; Author: Stu Dent
; Class: 151-02 Spring 02 2021
; Mini-Project 4, Parts 1-4
; Date: May 5, 2021
; Citations:
; XXX
; YYY
; Code here
Document and write the following pair of functions using recursive decomposition:
(list-and l) returns #t if all of the boolean values found in l are #t and #f otherwise.(list-or l) returns #t if any (i.e., at least one) of the boolean values found in l are #t and #f otherwise.Both functions require that l is a list of boolean values. In both cases, the empty list should return #t.
In addition to the implementation, write a rackunit test suite that verifies that list-and and list-or work correctly.
Consider the following erroneous implementation of a list reversal function which ought to return its input, but reversed.
This implementation attempts to use cons to add every element onto the end of the list sequentially:
(define bad-reverse
(lambda (l)
(if (null? l)
null
(let ([head (car l)]
[tail (cdr l)])
(cons head (bad-reverse tail))))))
Write a collection of test cases using rackunit that check the correctness of this function.
Make sure to cover both the base and recursive cases of the function.
You should have noted that bad-reverse is indeed bad!
In a comment, describe what the problem is and ultimately what bad-reverse actually does.
Now let’s build up to a correct implementation of list reversal.
First, document and write a recursive function (snoc x l) which behaves like (cons x l) but appends x onto the end of l rather than the front.
Write a rackunit test suite that verifies snoc is correctly implemented and ensure that you cover all relevant cases, e.g., base and recursive cases.
Document and write a function (list-reverse l) that returns l but reversed.
Use recursive decomposition to design list-reverse, keeping in mind that snoc is available for use.
Write a rackunit test suite that verifies that list-reverse is correct.
Document and implement a function (concat ll) using recursive decomposition that takes a list of lists ll as input and returns a single list that contains all of the elements drawn from the lists of ll in order.
For example:
> (concat (list (list 1 2) (list 3 4 5) (list 6 7) (list 8 9 10)))
'(1 2 3 4 5 6 7 8 9 10)
Write a rackunit test suite that verifies that concat is correct.
Implement a function (pairwise-swap l) using recursive decomposition that returns l but with each pair of adjacent elements swapped in position.
If the length of the list is odd, the last element is left in its original position:
For example:
> (pairwise-swap '(3 8 1 6 4 2 5))
'(8 3 6 1 2 4 5)
(Hint: assume that you had access to the front two elements of the list and try to design the recursive case of the function with this information.
If you restricted yourself to using car and cdr, what must be true of the list for this to be possible?)
Submissions that lack any of these characteristics will get an I.
[ ] File correctly named recursion-practice.rkt
[ ] File includes a header as instructed
[ ] Citations are included, including for past lab code done with a partner
[ ] File runs without error
[ ] Documentation is included for most procedures
Submissions that lack any of these characteristics will get an R.
[ ] 100% of tests are passed in all problems
[ ] Documentation is included for all procedures, and is mostly correct
[ ] Variable names are clear
[ ] In part 2b, an accurate description of the problem is given
[ ] Tests are included for all parts
Submissions that lack any of these characteristics will get an M.
[ ] Documentation is correct for all procedures
[ ] Code is elegant: recursion is completed in a clear and succinct way
[ ] Tests are included for all parts, and cover a wide range of edge cases