Activity: Scheme Recursion Practice (2)

Table of Contents

1 Activity structure

This is an activity not an assignment. That means it is not a graded assessment: you won't get formal feedback on it, but it is a great chance to practice with the ideas we've been talking about and it may also guide you through some new ideas. You'll work on it during class, usually with another students, or if you have to miss class, you'll complete it outside of class.

If you're working with someone, you should work in a paired programming style. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You'll tradeoff who is driving about every 10 minutes, and it's important that regardless of whose computer you're using, you take turns typing and controlling it - the owner of the computer should not be the only one who drives. Before you start coding for a new part of the activity, I strongly encourage you to sketch out your strategy with your partner. You might discuss possible approaches together, and write down some ideas on paper that will then help you when you begin coding.

At the end of class, you should make sure you turn your code in (even if you're not done), as that gives you access to my solutions, and to email the code to your partner (so they can turn it in to access my solutions).

2 Setup

If both you and your partner have computers with you with the tools for our class setup on it, decide whose computer you'll be using.

Them you'll do the activity in VS Code: download the starter code (below), unzip it, move it into the ProgrammingLanguages folder for our docker container, and then open that folder as a docker in VSCode.

Click here to download the starter code for this activity.

3 Tasks

Put all of your code for these tasks in main.scm.

3.1 Code reading warm-up

Here's some Scheme code: 

(define foo
        (lambda (item other lst)
                (cond ((null? lst) 
                           '())
                          ((equal? (car lst) item)
                            (cons other (foo item other (cdr lst))))
                          (else 
                                (cons (car lst)
                                      (foo item other (cdr lst)))))))

What would be a more descriptive name for this function? What would be the output if we did (foo 4 'new '(5 4 1))?

3.2 remove-first

Write a function remove-first that returns a list with the same items as the original except that the first occurrence of a particular item is no longer there. Here are some example inputs and expected outputs: 

(remove-first 3 '(1 2 3 6 3)) ;; Returns (1 2 6 3)
(remove-first 3 '(1 2 6)) ;; Returns (1 2 6)

You can assume that the second input is a list, not a number or other structure.

I haven't provided tests for this activity - instead, use it as a chance to practice testing your own code on a variety of inputs and outputs.

3.3 remove-all

Write a function remove-all that returns a list that is identical to the input list but without any occurrences of some specific item. Here are some example inputs and expected outputs: 

(remove-all 3 '(1 2 3 6 3)) ;; Returns (1 2 6)
(remove-all 3 '(1 2 6)) ;; Returns (1 2 6)

To write this function, start with your remove-first implementation and make only small changes to your code. As above, try your code on several test cases.

3.4 cons-each

Examine the function cons-each in the starter code. Try to identify the outputs for the following inputs without actually running the code: 

(cons-each 3 '())
(cons-each 3 '((1) (2)))
(cons-each 3 '(() (1) (2)))
(cons-each '(3) '((1) (2)))

Then, run the examples to check whether you're correct. Add a good comment to cons-each that describes what it does in English (e.g., a comment like "Returns the square of the input" would be a good form of comment, although not correct; a comment that said something like "if input is 0 then return 3 otherwise return 3 times the result of cons-each on the cdr of the original input" would not be a good form of comment).

4 Turning in activities

To turn in this activity, zip up the folder with your code, and upload that zip on Moodle. Additionally, email the zip to your partner so they can turn it in too. Even if you worked with a partner or you didn't finish, everyone should turn in the activity in order to gain access to my solutions.