# Homework 9 Solutions hw09.zip

## Solution Files

You can find the solutions in hw09.scm.

## 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: Ascending

Implement a procedure called `ascending?`, which takes a list of numbers `asc-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`.

Note: The question mark in `ascending?` is just part of the function name and has no special meaning in terms of Scheme syntax. It is a common practice in Scheme to name a function with a question mark at the end if the function returns a boolean value indicating whether or not a condition is satisfied. For instance, `ascending?` is a function that essentially asks "Is the argument in ascending order?", `null?` is a function that asks "Is the argument `nil`?", `even?` asks "Is the argument even?", etc.

``````(define (ascending? asc-lst)
(if (or (null? asc-lst) (null? (cdr asc-lst)))
#t
(and (<= (car asc-lst) (car (cdr asc-lst))) (ascending? (cdr asc-lst)))))``````

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

• The base case is where `asc-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 `asc-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``````

### Q2: My Filter

Write a procedure `my-filter`, which takes a predicate `pred` and a list `s`, 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 pred s)
(cond ((null? s) '())
((pred (car s)) (cons (car s) (my-filter pred (cdr s))))
(else (my-filter pred (cdr s))))
)``````
Video walkthrough:

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 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)))))
)
; Alternate Solution
(define (interleave lst1 lst2)
(cond
((null? lst1) lst2)
((null? lst2) lst1)
(else (cons (car lst1) (interleave lst2 (cdr lst1))))
))``````

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 `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``````

## Exam Practice

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

## Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.