Homework 8: Scheme Lists

hw08.zip

Due by 11:59pm on Thursday, November 14

Instructions

Download hw08.zip. Inside the archive, you will find a file called hw08.scm, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.

The 61A Scheme interpreter is included in each Scheme assignment. To start it, type python3 scheme in a terminal. To load a Scheme file called f.scm, type python3 scheme -i f.scm. To exit the Scheme interpreter, type (exit).

Scheme Editor

All Scheme assignments include a web-based editor that makes it easy to run ok tests and visualize environments. Type python3 editor in a terminal, and the editor will open in a browser window (at http://127.0.0.1:31415/). Whatever changes you make here will also save to the original file on your computer! To stop running the editor and return to the command line, type Ctrl-C in the terminal where you started the editor.

The Run button loads the current assignment's .scm file and opens a Scheme interpreter, allowing you to try evaluating different Scheme expressions.

The Test button runs all ok tests for the assignment. Click View Case for a failed test, then click Debug to step through its evaluation.

Recommended VS Code Extensions

If you choose to use VS Code as your text editor (instead of the web-based editor), install the vscode-scheme extension so that parentheses are highlighted.

Before:

After:

In addition, the 61a-bot (installation instructions) VS Code extension is available for Scheme homeworks. The bot is also integrated into ok.

Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Q1: Ascending

Implement a procedure called ascending?, which takes a list of numbers s and returns True if the numbers are in non-descending order, and False otherwise.

A list of numbers is non-descending if each element after the first is greater than or equal to the previous element. For example...

(1 2 3 3 4) is non-descending.
(1 2 3 3 2) is not.

Hint: The built-in null? procedure returns whether its argument is nil.

Note: The question mark in ascending? is just part of the procedure name and has no special meaning in terms of Scheme syntax. It is a common practice in Scheme to name procedures with a question mark at the end if it returns a boolean value.

(define (ascending? s)
  'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

python3 ok -q ascending -u
python3 ok -q ascending

Q2: My Filter

Write a procedure my-filter, which takes in a one-argument predicate function pred and a list s, and returns a new list containing only elements in list s that satisfy the predicate. The returned list should contain the elements in the same order that they appeared in the original list s.

For example, (my-filter even? '(1 2 3 4 5)) should return (2 4) because only 2 and 4 are even.

Note: You are not allowed to use the Scheme built-in filter function in this question - we are asking you to re-implement this!

(define (my-filter pred s)
  'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

python3 ok -q filter -u
python3 ok -q filter

Q3: Interleave

Implement the function interleave, which takes two lists lst1 and lst2 as arguments, and returns a new list that alternates elements from both lists, starting with lst1.

If one of the input lists is shorter than the other, interleave should include elements from both lists until the shorter list is exhausted, then append the remaining elements of the longer list to the end. If either lst1 or lst2 is empty, the function should simply return the other non-empty list.

For example:

(interleave '(1 2 3) '(4 5 6)) should return (1 4 2 5 3 6).
(interleave '(7 8 9 10) '(11 12)) should return (7 11 8 12 9 10).

(define (interleave lst1 lst2)
'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

python3 ok -q interleave -u
python3 ok -q interleave

Q4: No Repeats

Implement no-repeats, which takes a list of numbers s. It returns a list that has all of the unique elements of s in the order that they first appear, but no repeats.

For example, (no-repeats (list 5 4 5 4 2 2)) evaluates to (5 4 2).

Hint: You may find it helpful to use filter with a lambda procedure to filter out repeats. To test if two numbers a and b are not equal, use (not (= a b)).

(define (no-repeats s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q no_repeats

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading the .scm file to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

Exam Practice

The following are some Scheme List exam problems from previous semesters that you may find useful as additional exam practice.