# Lab 13: Final Review

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

## Starter Files

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

## Submission

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
okpy.org.

- To receive credit for this lab, you must complete Questions 1-4 in lab13.py 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

## Scheme

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)
'YOUR-CODE-HERE
nil
(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))
double
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)
'YOUR-CODE-HERE
nil
(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`

## Generators

These questions are to be done in `lab13.py`

.

### Q3: Generators generator

Write the function `make_generators_generator`

, which takes a generator
function `g`

and defines a generator which yields generators. The `i`

th 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:
1
Next Generator:
1
2
Next Generator:
1
2
3
Next Generator:
1
2
3
4
Next Generator:
1
2
3
4
5
"""
"*** 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 []
return
"*** 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)
'YOUR-CODE-HERE
nil
(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)
'YOUR-CODE-HERE
nil
(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)
'YOUR-CODE-HERE
nil
(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`

## Streams

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)
'YOUR-CODE-HERE
(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`

## SQL

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;
0|0
0|1
0|2
0|3
0|4
```

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

```
CREATE TABLE pairs AS
SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";
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`