Solution Files

You can find the solutions in hw07.scm.

Scheme Editor

How to launch

In your hw07 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.

Features

The hw07.scm file should already be open. You can edit this file and then run Run to run the code and get an interactive terminal or Test to run the ok tests.

Environments will help you diagram your code, and Debug works with environments so you can see where you are in it. We encourage you to try out all these features.

Reformat is incredibly useful for determining whether you have parenthesis based bugs in your code. You should be able to see after formatting if your code looks weird where the issue is.

By default, the interpreter uses Lisp-style formatting, where the parens are all put on the end of the last line

(define (f x)
    (if (> x 0)
        x
        (- x)))

However, if you would prefer the close parens to be on their own lines as so

(define (f x)
    (if (> x 0)
        x
        (- x)
    )
)

you can go to Settings and select the second option.

Required Questions

Scheme Lists

Q1: Filter Lst

Write a procedure filter-lst, which takes a predicate fn 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 (filter-lst fn lst)
  (cond ((null? lst) '())
        ((fn (car lst)) (cons (car lst) (filter-lst fn (cdr lst))))
        (else (filter-lst fn (cdr lst))))
)

;;; Tests
(define (even? x)
  (= (modulo x 2) 0))
(filter-lst even? '(0 1 1 2 3 5 8))
; expect (0 2 8)

Use Ok to unlock and test your code:

python3 ok -q filter_lst -u
python3 ok -q filter_lst

Q2: Interleave

Implement the function interleave, which takes a two lists as arguments. interleave will return a new list that interleaves the elements of the two lists. Refer to the tests for sample input/output.

(define (interleave first second)
  (if (or (null? first) (null? second))
      (append first second)
      (cons (car first)
            (cons (car second)
                  (interleave (cdr first) (cdr second)))))
)

(interleave (list 1 3 5) (list 2 4 6))
; expect (1 2 3 4 5 6)

(interleave (list 1 3 5) nil)
; expect (1 3 5)

(interleave (list 1 3 5) (list 2 4))
; expect (1 2 3 4 5)

Use Ok to test your code:

python3 ok -q interleave

Q3: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

1. combiner: a function of two arguments
2. start: a number with which to start combining
3. n: the number of natural numbers to combine
4. 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 combiner, 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 combiner 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 combiner will always be commutative: i.e. the order of arguments do not matter.

(define (accumulate combiner start n term)
  (if (= n 0)
    start
    (accumulate combiner (combiner (term n) start) (- n 1) term))
)

Use Ok to test your code:

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).

Hints: 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 =. You may find it helpful to use the filter-lst procedure with a helper lambda function to use as a filter.

(define (no-repeats lst)
  (if (null? lst) lst
    (cons (car lst)
      (no-repeats (filter (lambda (x) (not (= (car lst) x))) (cdr lst)))))
)

Use Ok to unlock and test your code:

python3 ok -q no_repeats -u
python3 ok -q no_repeats