**Note the special time:** *Due by 7pm on Wednesday, 3/20*

**Submission.** See the online submission instructions. We have
provided a starter file for the questions below.

**Readings.** Section 2.7
and Section 3.3
of the online lecture notes.

**Q1.** The following is our `Rational` implementation from lecture:

from fractions import gcd class Rational(object): """A mutable fraction. >>> f = Rational(3, 5) >>> f Rational(3, 5) >>> print(f) 3/5 >>> f.float_value 0.6 >>> f.numerator = 4 >>> f.float_value 0.8 >>> f.denominator -= 3 >>> f.float_value 2.0 """ def __init__(self, numer, denom): g = gcd(numer, denom) self.numerator = numer // g self.denominator = denom // g @property def float_value(self): return self.numerator / self.denominator def __repr__(self): return 'Rational({0}, {1})'.format(self.numerator, self.denominator) def __str__(self): return '{0}/{1}'.format(self.numerator, self.denominator) def __add__(self, num): return add_rational(self, num) def __mul__(self, num): return mul_rational(self, num) def __eq__(self, num): return eq_rational(self, num) def __bool__(self): return self.numerator != 0 def add_rational(r1, r2): denom = r1.denominator * r2.denominator numer1 = r1.numerator * r2.denominator numer2 = r1.denominator * r2.numerator return Rational(numer1 + numer2, denom) def mul_rational(r1, r2): return Rational(r1.numerator * r2.numerator, r1.denominator * r2.denominator) def eq_rational(r1, r2): return (r1.numerator * r2.denominator == r2.numerator * r1.denominator)

Alyssa P. Hacker is unhappy with this implementation: she believes that an
instance of a rational number should be immutable, so that the user cannot
change the number represented by a rational once it has been created. She writes
the following subclass of `Rational` that she thinks is immutable. (You can
find documentation on the `__setattr__` special method here )

class ImmutableRational(Rational): """An immutable fraction. >>> f = ImmutableRational(3, 5) >>> f ImmutableRational(3, 5) >>> f.numerator = 4 >>> f ImmutableRational(3, 5) >>> f.denominator -= 3 >>> f ImmutableRational(3, 5) """ def __init__(self, numer, denom): Rational.__init__(self, numer, denom) self.finalized = True def __setattr__(self, attr, value): if hasattr(self, 'finalized') and self.finalized: return object.__setattr__(self, attr, value) def __repr__(self): return 'ImmutableRational({0}, {1})'.format(self.numerator, self.denominator)

Show that Alyssa has not completely solved the problem of mutability by
completing the function below that mutates an `ImmutableRational`
instance. (Do not use `del` or `__delattr__`.)

def mutate_rational(r): """Mutate a rational by adding one to its denominator. >>> f = ImmutableRational(3, 5) >>> f ImmutableRational(3, 5) >>> mutate_rational(f) >>> f ImmutableRational(3, 6) """ "*** YOUR CODE HERE ***"

**Q2.** Write a class `Amount` that represents a collection of nickels and
pennies. Include a property method called `value` that computes the total
monetary value of the amount from the nickels and pennies.

Do not add an instance attribute called `value` to each `Amount` instance.
Instead, an `Amount` should have only two instance attributes: `nickels` and
`pennies`. You do not need to support direct assignment to `value`. (You are
welcome to add that feature as well; see the relevant Python Property docs).

Finally, write a subclass `MinimalAmount` with base class `Amount` that
overrides the constructor so that all amounts are *minimal* upon construction.
An `Amount` instance is minimal if it has no more than four pennies, but the
same value as the nickel and penny quantities passed as arguments:

class Amount(object): """An amount of nickels and pennies. >>> a = Amount(3, 7) >>> a.nickels 3 >>> a.pennies 7 >>> a.value 22 >>> a.nickels = 5 >>> a.value 32 """ "*** YOUR CODE HERE ***" class MinimalAmount(Amount): """An amount of nickels and pennies that is initialized with no more than four pennies, by converting excess pennies to nickels. >>> a = MinimalAmount(3, 7) >>> a.nickels 4 >>> a.pennies 2 >>> a.value 22 """ "*** YOUR CODE HERE ***"

**Q3.** Write a data-directed apply function that computes the area or perimeter
of either a square or a rectangle. Use a dictionary to store the implementations
of each function for each type:

class Square(object): def __init__(self, side): self.side = side class Rect(object): def __init__(self, width, height): self.width = width self.height = height def type_tag(s): return type_tag.tags[type(s)] type_tag.tags = {Square: 's', Rect: 'r'} def apply(operator_name, shape): """Apply operator to shape. >>> apply('area', Square(10)) 100 >>> apply('perimeter', Square(5)) 20 >>> apply('area', Rect(5, 10)) 50 >>> apply('perimeter', Rect(2, 4)) 12 """ "*** YOUR CODE HERE ***"

**Q4.** The following is the `Rlist` class from lecture, which implements the
recursive list data type, and the `map_rlist` function that maps a given
function over a given `Rlist` to produce a new `Rlist`:

class Rlist(object): """A recursive list consisting of a first element and the rest. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> len(s) 3 >>> s[0] 1 >>> s[1] 2 >>> s[2] 3 """ class EmptyList(object): def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): f = repr(self.first) if self.rest is Rlist.empty: return 'Rlist({0})'.format(f) else: return 'Rlist({0}, {1})'.format(f, repr(self.rest)) def __len__(self): return 1 + len(self.rest) def __getitem__(self, i): if i == 0: return self.first return self.rest[i - 1] def map_rlist(fn, s): """Return an Rlist resulting from mapping fn over the elements of s. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> map_rlist(lambda x: x * x, s) Rlist(1, Rlist(4, Rlist(9))) """ if s is Rlist.empty: return s return Rlist(fn(s.first), map_rlist(fn, s.rest))

Write a new `deep_map_rlist` function that also maps a given function `fn`
over an `Rlist` `s` to produce a new `Rlist`. However, if `s` contains
an `Rlist` as an element, then `deep_map_rlist` should recursively apply
`fn` to each of that `Rlist`'s elements rather than to that `Rlist`
itself.

*Hint*: You may find the built-in `isinstance` function useful.

def deep_map_rlist(fn, s): """Return an Rlist with the same structure as s but with fn mapped over its elements. An element that is an Rlist will have fn recursively mapped over its elements. >>> s = Rlist(1, Rlist(Rlist(2, Rlist(3)), Rlist(4))) >>> deep_map_rlist(lambda x: x * x, s) Rlist(1, Rlist(Rlist(4, Rlist(9)), Rlist(16))) """ "*** YOUR CODE HERE ***"

**Q5.** (Extra for experts) The `Rlist` class can represent lists with cycles.
That is, a list may contain itself as a sublist.

>>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> s[20] 3

- This question has two parts:
- Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle.
- Write a function has_cycle_constant that has the same behavior as has_cycle but requires only a constant amount of space.

Hint: The solution to B is short (~10 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

def has_cycle(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5))))) >>> s.rest.rest.rest.rest.rest = s.rest.rest >>> has_cycle(s) True >>> t = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5))))) >>> has_cycle(t) False """ "*** YOUR CODE HERE ***" def has_cycle_constant(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5))))) >>> s.rest.rest.rest = s >>> has_cycle_constant(s) True >>> t = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5))))) >>> has_cycle_constant(t) False """ "*** YOUR CODE HERE ***"