Homework 6 Solutions

Solution Files

You can find the solutions in hw06.scm.

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

Code Writing Questions

Q1: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 10 Scheme Refresher.

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)

  (car (cdr s))
)

(define (caddr s)

  (car (cddr s))
)

Following the given example of cddr, defining cadr and caddr should be fairly straightforward.

Just for fun, if this were a Python linked list question instead, the solution might look something like this:

cadr = lambda l: l.rest.first
caddr = lambda l: l.rest.rest.first

Use Ok to unlock and test your code:

python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr

Q2: Ascending

Implement a procedure called ascending?, which takes a list of numbers lst and returns True if the numbers are in nondescending order, and False otherwise. Numbers are considered nondescending if each subsequent number is either larger or equal to the previous, that is:

1 2 3 3 4

Is nondescending, but:

1 2 3 3 2

Is not.

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

(define (ascending? lst)

  (if (or (null? lst) (null? (cdr lst)))
      true
      (and (<= (car lst) (car (cdr lst))) (ascending? (cdr lst))))
)

We approach this much like a standard Python linked list problem.

  • The base case is where lst has zero or one items. Trivially, this is in order.
  • Otherwise we check if the first element is in order -- that is, if it's smaller than the second element. If it's not, then the list is out of order. Otherwise, we check if the rest of lst is in order.

You should verify for yourself that a Python implementation of this for linked lists is similar.

Use Ok to unlock and test your code:

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

Q3: Interleave

Implement the function interleave, which takes a two lists lst1 and lst2 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 lst1 and lst2.)

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 lst1 lst2)

  (if (or (null? lst1) (null? lst2))
      (append lst1 lst2)
      (cons (car lst1)
            (cons (car lst2)
                  (interleave (cdr lst1) (cdr lst2)))))
)

Use Ok to unlock and test your code:

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

Q4: 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)

  (cond ((null? lst) '())
        ((func (car lst)) (cons (car lst) (my-filter func (cdr lst))))
        (else (my-filter func (cdr lst))))

)
Video walkthrough:

YouTube link

Use Ok to unlock and test your code:

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

Q5: 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)

  (if (null? lst) lst
    (cons (car lst)
      (no-repeats (my-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