Homework 8: Scheme
Due by 11:59pm on Friday, November 12
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 with python3 ok
--submit
. 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 okpy.org. 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. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.
Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.
You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code through Ok though!
Scheme Editor
As you're writing your code, you can debug using the Scheme Editor. In your scheme
folder you will find a new editor. To run this editor, run python3 editor
. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 and you should see it.
Make sure to run python3 ok
in a separate tab or window so that the editor keeps running.
If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!
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.
Q1: My Filter
Write a procedure my-filter
, which takes a predicate func
and a list lst
, and
returns a new list containing only elements of the list that satisfy the
predicate. The output should contain the elements in the same order that they
appeared in the original list.
Note: Make sure that you are not just calling the built-in filter
function in Scheme - we are asking you to re-implement this!
(define (my-filter func lst)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Q2: Interleave
Implement the function interleave
, which takes a two lists s1
and s2
as
arguments. interleave
should return a new list that interleaves the elements
of the two lists. (In other words, the resulting list should contain elements
alternating between s1
and s2
.)
If one of the input lists to interleave
is shorter than the other, then
interleave
should alternate elements from both lists until one list has no
more elements, and then the remaining elements from the longer list should be
added to the end of the new list.
(define (interleave s1 s2)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q interleave -u
python3 ok -q interleave
Q3: Accumulate
Fill in the definition for the procedure accumulate
, which merges the first
n
natural numbers (ie. 1 to n, inclusive) according to the following parameters:
merger
: a function of two argumentsstart
: a number with which we start merging withn
: the number of natural numbers to mergeterm
: a function of one argument that computes the nth term of a sequence
For example, we can find the product of all the numbers from 1 to 5 by
using the multiplication operator as the merger
, and starting our
product at 1:
scm> (define (identity x) x)
scm> (accumulate * 1 5 identity) ; 1 * 1 * 2 * 3 * 4 * 5
120
We can also find the sum of the squares of the same numbers by using the
addition operator as the merger
and square
as the term
:
scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square) ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
scm> (accumulate + 5 5 square) ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60
You may assume that the merger
will always be commutative: i.e. the order
of arguments do not matter.
Hint: You may find it useful to refer to the recursive implementation of
accumulate
we implemented in Python in HW 2.
(define (accumulate merger start n term)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q accumulate -u
python3 ok -q accumulate
Q4: No Repeats
Implement no-repeats
, which takes a list of numbers lst
as input and returns
a list that has all of the unique elements of lst
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: How can you make the first time you see an element in the input list be the first and only time you see the element in the resulting list you return?
Hint: You may find it helpful to use the
my-filter
procedure with a helperlambda
function to use as a filter. To test if two numbers are equal, use the=
procedure. To test if two numbers are not equal, use thenot
procedure in combination with=.
(define (no-repeats lst)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q no_repeats -u
python3 ok -q no_repeats