Use the following commands to download and unpack the distribution code:

$ wget https://amirkamil.github.io/homework/hw3/starter-files.tar.gz $ tar xzf starter-files.tar.gz

You may work alone or with a partner. Please see the syllabus for partnership rules. As a reminder, you may not share any part of your solution outside of your partnership. This includes code, test cases, and written solutions.

This assignment has several restrictions to ensure that you get the intended practice with the relevant abstractions and patterns. Please pay close attention to the requirements when writing your solutions.

You may **not** use the `functools` or `itertools` modules
anywhere in this assignment.

*Decorators and memoization.*Memoization is an optimization in recursive algorithms that have repeated computations, where the arguments and result of a function call are stored when a function is first called with that set of arguments. Then if the function is called again with the same arguments, the stored value is looked up and returned rather than being recomputed.For this problem, implement a

`memoize`decorator in Python that takes in a function and returns a version that performs memoization. The decorator should work on functions that take in any number of non-keyword arguments. You may assume that all arguments are hashable.*Hint*: We recommend using a dictionary to store previously computed values, and variable argument lists to handle functions with any number of parameters.def memoize(func): """Return a version of func that memoizes computation. Returns a function that computes the same result as func, but if a given set of arguments has already been seen before, returns the previously computed result instead of repeating the computation. Assumes func is a pure function (i.e. has no side affects), and that all arguments to func are hashable. >>> @memoize ... def sum_to_n(n): ... return 1 if n == 1 else n + sum_to_n(n - 1) >>> try: ... sum_to_n(300) ... sum_to_n(600) ... sum_to_n(900) ... sum_to_n(1200) ... except RecursionError: ... print('recursion limit exceeded') 45150 180300 405450 720600 >>> @memoize ... def sum_k_to_n(k, n): ... return k if n == k else n + sum_k_to_n(k, n - 1) >>> try: ... sum_k_to_n(2, 300) ... sum_k_to_n(2, 600) ... sum_k_to_n(2, 900) ... sum_k_to_n(2, 1200) ... except RecursionError: ... print('recursion limit exceeded') 45149 180299 405449 720599 """ # add your code below

*Chain.*Recall that the`compose()`higher-order function takes in two single-parameter functions as arguments and returns the composition of the two functions. Thus,`compose(f, g)(x)`computes`f(g(x))`.The following is a definition of

`compose()`in Python:def compose(f, g): return lambda x: f(g(x))

Composition can be generalized to function chains, so that

`chain(f, g, h)(x)`computes`f(g(h(x)))`,`chain(f, g, h, k)(x)`computes`f(g(h(k(x))))`, and so on. Implement the variadic`chain()`function in Python.def chain(*funcs): """Return a function that is the compositional chain of funcs. If funcs is empty, returns the identity function. >>> chain()(3) 3 >>> chain(lambda x: 3 * x)(3) 9 >>> chain(lambda x: x + 1, lambda x: 3 * x)(3) 10 >>> chain(lambda x: x // 2, lambda x: x + 1, lambda x: 3 * x)(3) 5 """ # add your code below

Your solution

**must**use recursion.*Generators.*This problem will give you practice in working with generators that represent infinite sequences.You may

**not**use any built-in sequences (e.g. lists, tuples, dicts) for this problem.Implement a

`scale()`generator that, given an iterable of numbers, scales them by a constant to produce a new iterable. For example, given a generator`naturals()`for the natural numbers,`scale(naturals(), 2)`produces an iterable of the even natural numbers.def scale(items, factor): """Produce an iterable of the elements in items scaled by factor. Consumes the elements from items. >>> def naturals(): ... num = 0 ... while True: ... yield num ... num += 1 >>> values = scale(naturals(), 3) >>> [next(values) for i in range(5)] [0, 3, 6, 9, 12] """ # add your code below

Implement a

`merge()`generator that, given two infinite iterables whose elements are in strictly increasing order, produces a new iterable that contains the items from both input iterables, in increasing order and without duplicates.def merge(items1, items2): """Produce an ordered iterable that is the merge of the inputs. The resulting iterable contains the elements in increasing order from items1 and items2, without duplicates. Requires each of items1 and items2 to be infinite iterables in strictly increasing order. Consumes the elements from items1 and items2. >>> def naturals(): ... num = 0 ... while True: ... yield num ... num += 1 >>> values = merge(naturals(), naturals()) >>> [next(values) for i in range(5)] [0, 1, 2, 3, 4] >>> values2 = merge(scale(naturals(), 2), scale(naturals(), 3)) >>> [next(values2) for i in range(10)] [0, 2, 3, 4, 6, 8, 9, 10, 12, 14] """ # add your code below

A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, we can build an iterable of such numbers using a generator. Let us call the required iterable of numbers

`s`and notice the following facts about it.`s`begins with 1.- The elements of
`scale(s, 2)`are also elements of`s`. - The same is true for
`scale(s, 3)`and`scale(s, 5)`. - These are all of the elements of
`s`.

All that is left is to combine the elements from these sources, which can be done with the

`merge()`generator above. Fill in the`make_s()`generator that produces the required iterable`s`.def make_s(): """Produce iterable of ints that only have factors in {2, 3, 5}. >>> values = make_s() >>> [next(values) for i in range(18)] [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30] """ # add your code below

Place your solutions to questions 1-3 in the provided `hw3.py` file.
Submit `hw3.py` to the autograder before the deadline. Be sure to
register your partnership on the autograder if you are working with a
partner.