Homework 8: Scheme

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, zip up your assignment and submit it through 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. 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

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 arguments
start: a number with which we start merging with
n: the number of natural numbers to merge
term: 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 helper lambda 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 the not 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