# Lab 13: Final Review

*Due at 11:59pm on Friday, 04/27/2018.*

## 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-3 in lab13.py and lab13.scm and submit through OK.
- Question 4-8 are considered
**extra practice**. They can be found in the lab13_extra.py and lab13_extra.scm files. It is recommended that you complete them on your own time.

# Required Questions

## Scheme

For a quick refresher on Scheme, see Lab 09.

This question is 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)))`

.

```
scm> (define (square x) (* x x))
square
scm> (define (add-one x) (+ x 1))
add-one
scm> (define (double x) (* x 2))
double
scm> (define composed (compose-all (list double square add-one)))
composed
scm> (composed 1)
5
scm> (composed 2)
17
```

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

## Tail Recursion

For a quick refresher on tail recursion, see Discussion 8.

This question is to be done in

`lab13.scm`

.

### Q2: Replicate

Write a tail-recursive function that returns a list with `x`

repeated `n`

times.

```
scm> (tail-replicate 3 10)
(3 3 3 3 3 3 3 3 3 3)
scm> (tail-replicate 5 0)
()
scm> (tail-replicate 100 5)
(100 100 100 100 100)
```

```
(define (tail-replicate x n)
'YOUR-CODE-HERE
(define (helper n so-far)
(if (= n 0) so-far
(helper (- n 1) (cons x so-far))))
(helper n '()))
```

Use Ok to test your code:

`python3 ok -q tail-replicate`

## Generators

For a quick refresher on generators, see Lab 11.

This question is to be done in

`lab13.py`

.

### Q3: 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).
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`

?

Note that in the provided code, the

`return`

statement acts like a`raise StopIteration`

. The point of this is so that the returned generator doesn't enter the rest of the body on any calls to`next`

after the first if the input list is empty. Note that this`return`

statement does not affect the fact that the function will still return a generator object because the body contains`yield`

statements.

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

Use Ok to test your code:

`python3 ok -q permutations`

# Optional Questions

## Streams

For a quick refresher on streams, see Discussion 9.

This question is to be done in

`lab13_extra.scm`

.

### Q4: 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 in a run, and the second element is the number of of times that number appears in the run.

We will extend this idea to 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.

```
scm> (define s (cons-stream 1 (cons-stream 1 (cons-stream 2 nil))))
s
scm> (define encoding (rle s))
encoding
scm> (car encoding) ; Run of number 1 of length 2
(1 2)
scm> (car (cdr-stream encoding)) ; Run of number 2 of length 1
(2 1)
scm> (stream-to-list (rle (list-to-stream '(1 1 2 2 2 3)))) ; See functions at bottom of lab13.scm
((1 2) (2 3) (3 1))
```

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

## More Tail Recursion

This question is to be done in

`lab13_extra.scm`

.

### Q5: Insert

Write a tail-recursive function that inserts a number `n`

into a non-empty
sorted list of numbers, `s`

.

Hint:Use the built-in Scheme function`append`

to concatenate two lists together.`scm> (append '(1 2) '(3 4)) (1 2 3 4) scm> (append '(2 4 6) '()) (2 4 6) scm> (append '() '(5 3 1)) (5 3 1)`

```
scm> (insert 1 '(2))
(1 2)
scm> (insert 5 '(2 4 6 8))
(2 4 5 6 8)
scm> (insert 1000 '(1 2 3 4 5 6))
(1 2 3 4 5 6 1000)
```

```
(define (insert n s)
'YOUR-CODE-HERE
(define (insert-help s so-far)
(cond ((null? s) (append so-far (cons n s)))
((< n (car s)) (append so-far (cons n s)))
(else (insert-help (cdr s) (append so-far (list (car s)))))))
(insert-help s nil))
```

Use Ok to test your code:

`python3 ok -q insert`

The Ok tests for this problem don't check whether your solution is tail-recursive! In order to check your understanding, you can run some manual tests with large input such as the following to ensure that your function use a constant number of frames:

`scm> (define big-list (tail-replicate 3 1000)) big-list scm> (define result (insert 4 big-list)) result scm> (define expected (append big-list (list 4))) expected scm> (equal? result expected) True`

## More Scheme

These questions are to be done in

`lab13_extra.scm`

.

### Q6: 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`

### Q7: 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.

```
scm> (tally '(james jen jemin john))
((james . 1) (jen . 1) (jemin . 1) (john . 1))
scm> (tally '(billy billy bob billy bob billy bob))
((billy . 4) (bob . 3))
scm> (tally '())
()
```

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

```
; Implementing and using these helper procedures is optional. You are allowed
; to delete them.
(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))))))
(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`

## More Generators

This question is to be done in

`lab13_extra.py`

.

### Q8: Generators generator

Write the generator function `make_generators_generator`

, which takes a
zero-argument generator function `g`

and returns a generator that yields
generators. For each element `e`

yielded by the generator object returned by
calling `g`

, a new generator object is yielded that will generate items 1
through `e`

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