Lab 13: Final Review

Due at 11:59pm on Friday, 12/01/17.

Starter Files

Download Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.


By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on

  • To receive credit for this lab, you must complete Questions 1-4 in and lab13.scm and submit through OK.
  • Question 5-7 are considered extra practice. They can be found in the lab13_extra.scm and lab13_extra.sql files. It is recommended that you complete them on your own time.

Required Questions


These questions are to be done in lab13.scm.

Q1: Compose All

Implement compose-all, which takes a list of one-argument functions and returns a one-argument function that applies each function in that list in turn to its argument. For example, if func is the result of calling compose-all on a list of functions (f g h), then (func x) should be equivalent to the result of calling (h (g (f x))).

(define (compose-all funcs)
(lambda (x) (if (null? funcs) x ((compose-all (cdr funcs)) ((car funcs) x))))

Use Ok to test your code:

python3 ok -q compose-all

Q2: Deep Map

Write the function deep-map, which takes a function fn and a nested list s. A nested list is a list where each element is either a number or a list (e.g. (1 (2) 3) where 1, (2), and 3 are the elements). It returns a list with identical structure to s, but replacing each non-list element by the result of applying fn on it, even for elements within sub-lists. For example:

scm> (define (double x) (* 2 x))
scm> (deep-map double '(2 (3 4)))
(4 (6 8))

Assume that the input has no dotted (malformed) lists.

Hint: You can use the function list?, which checks if a value is a list.

(define (deep-map fn s)
(cond ((null? s) s) ((list? (car s)) (cons (deep-map fn (car s)) (deep-map fn (cdr s)))) (else (cons (fn (car s)) (deep-map fn (cdr s)))))

Use Ok to test your code:

python3 ok -q deep-map


These questions are to be done in

Q3: Generators generator

Write the function make_generators_generator, which takes a generator function g and defines a generator which yields generators. The ith generator yielded will generate items 1 through i yielded by the generator returned by g.

def make_generators_generator(g):
    """Generates all the "sub"-generators of the generator returned by
    the generator function g.

    >>> def ints_to(n):
    ...     for i in range(1, n + 1):
    ...          yield i
    >>> def ints_to_5():
    ...     for item in ints_to(5):
    ...         yield item
    >>> for gen in make_generators_generator(ints_to_5):
    ...     print("Next Generator:")
    ...     for item in gen:
    ...         print(item)
    Next Generator:
    Next Generator:
    Next Generator:
    Next Generator:
    Next Generator:
"*** YOUR CODE HERE ***"
def gen(i): for item in g(): if i <= 0: break yield item i -= 1 i = 1 for item in g(): yield gen(i) i += 1

Use Ok to test your code:

python3 ok -q make_generators_generator

Q4: Generate Permutations

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].

Implement permutations, a generator function that takes in a lst and outputs all permutations of lst, each as a list (see doctest for an example).

def permutations(lst):
    """Generates all permutations of sequence LST. Each permutation is a
    list of the elements in LST in a different order.

    The order of the permutations does not matter.

    >>> sorted(permutations([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> type(permutations([1, 2, 3]))
    <class 'generator'>
    >>> sorted(permutations((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(permutations("ab"))
    [['a', 'b'], ['b', 'a']]
    if not lst:
        yield []
"*** YOUR CODE HERE ***"
for perm in permutations(lst[1:]): for i in range(len(lst)): yield perm[:i] + [lst[0]] + perm[i:]

The order in which you generate permutations is irrelevant.

Hint: If you had the permutations of lst minus one element, how could you use that to generate the permutations of the full lst?

Use Ok to test your code:

python3 ok -q permutations

Optional Questions

More Scheme

This question is to be done in lab13_extra.scm.

Q5: Tally

Implement tally, which takes a list of names and returns a list of pairs, one pair for each unique name in names. Each pair should contain a name and the number of times that the name appeared in names. Each name should appear only once in the output, and the names should be ordered by when they first appear in names.

Hint: Use the eq? procedure to test if two names are the same.

(define (tally names)
(map (lambda (name) (cons name (count name names))) (unique names))

Hint: If you find the procedure getting too complicated, you may want to try implementing the count and unique helper procedures to use in your solution. You may also want to use map and filter in your solution.

; Using this helper procedure is optional. You are allowed to delete it.
(define (unique s)
(if (null? s) nil (cons (car s) (unique (filter (lambda (x) (not (eq? (car s) x))) (cdr s)))))
) ; Using this helper procedure is optional. You are allowed to delete it. (define (count name s)
(if (null? s) 0 (+ (if (eq? name (car s)) 1 0) (count name (cdr s))))

Use Ok to test your code:

python3 ok -q tally


This question is to be done in lab13_extra.scm.

Q6: Run-Length Encoding

Run-length encoding is a very simple data compression technique, whereby runs of data are compressed and stored as a single value. A run is defined to be a contiguous sequence of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of two-element lists:

(1 5), (6 4), (2 1), (5 3)

Notice that the first element of each list is the number of times a particular number appears in a run, and the second element is the number in the run.

We will extend this idea to (possibly infinite) streams. Write a function called rle that takes in a stream of data, and returns a corresponding stream of two-element lists, which represents the run-length encoded version of the stream. You do not have to consider compressing infinite runs.

(define (rle s)
(define (track-run elem st len) (cond ((null? st) (cons-stream (list elem len) nil)) ((= elem (car st)) (track-run elem (cdr-stream st) (+ len 1))) (else (cons-stream (list elem len) (rle st)))) ) (if (null? s) nil (track-run (car s) (cdr-stream s) 1))

Use Ok to test your code:

python3 ok -q rle


This question is to be done in lab13_extra.sql. Make sure you have your sqlite3.exe file in the folder!

Q7: Pairs

Let’s figure out all possible pairs of numbers between 0 and 42 that sum to 42 (the answer to Life, the Universe, and Everything)!

To do this we can build a pairs table that contains all pairs without duplicates. This means 2,3 appears but 3,2 doesn't. Then we can use a query to select from this pairs table to find the ones that sum to 42.

The first 5 rows should look something like this:

sqlite> SELECT * FROM pairs LIMIT 5;

Hint: You may want to first create a helper table containing all the possible values you might want to include in your pairs.

WITH nums(n) as ( SELECT 0 UNION SELECT n + 1 FROM nums WHERE n < 42 ) SELECT a.n AS x, b.n AS y FROM nums AS a, nums AS b WHERE a.n <= b.n;

Use Ok to test your code:

python3 ok -q pairs