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 fulllst
?
Note that in the provided code, the
return
statement acts like araise StopIteration
. The point of this is so that the returned generator doesn't enter the rest of the body on any calls tonext
after the first if the input list is empty. Note that thisreturn
statement does not affect the fact that the function will still return a generator object because the body containsyield
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