Filter Rlist (as a method) with Mutation
This problem uses the Rlist Class defined here.
Let’s write a method filter
that is part of the Rlist
class. It takes in a function and keeps all of the elements
that satisfy the function. This method should mutate the rlist that this method is called on. You may assume that the rlist
that this is being called on has at least one element that will remain in the list after it has been filtered. In other words,
this Rlist
cannot magically turn into an EmptyRlist
.
def filter(self, fn):
""" Mutates the rlist and modifies it such that the elements that
do not satisfy the function are removed.
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.filter(lambda x: x%2 == 1)
>>> s
Rlist(1, Rlist(3))
>>> r = Rlist(2, Rlist(1))
>>> r.filter(lambda x: x%2 == 1)
>>> r
Rlist(1)
>>> x = Rlist(1)
>>> x.filter(lambda x: x%2 == 1)
>>> x
Rlist(1)
>>> y = Rlist(1, Rlist(2, Rlist(2)))
>>> y.filter(lambda x: x%2 == 1)
>>> y
Rlist(1)
>>> z = Rlist(2, Rlist(1, Rlist(2)))
>>> z.filter(lambda x: x%2 == 1)
>>> z
Rlist(1)
>>> q = Rlist(2, Rlist(2, Rlist(1)))
>>> q.filter(lambda x: x%2 == 1)
>>> q
Rlist(1)
>>> p = Rlist(2, Rlist(2, Rlist(1, Rlist(3, Rlist(2)))))
>>> p.filter(lambda x: x%2 == 1)
>>> p
Rlist(1, Rlist(3))
"""
"***YOUR CODE HERE***"
def filter(self, fn):
"""
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.filter(lambda x: x%2 == 1)
>>> s
Rlist(1, Rlist(3))
>>> r = Rlist(2, Rlist(1))
>>> r.filter(lambda x: x%2 == 1)
>>> r
Rlist(1)
>>> x = Rlist(1)
>>> x.filter(lambda x: x%2 == 1)
>>> x
Rlist(1)
>>> y = Rlist(1, Rlist(2, Rlist(2)))
>>> y.filter(lambda x: x%2 == 1)
>>> y
Rlist(1)
>>> z = Rlist(2, Rlist(1, Rlist(2)))
>>> z.filter(lambda x: x%2 == 1)
>>> z
Rlist(1)
>>> q = Rlist(2, Rlist(2, Rlist(1)))
>>> q.filter(lambda x: x%2 == 1)
>>> q
Rlist(1)
>>> p = Rlist(2, Rlist(2, Rlist(1, Rlist(3, Rlist(2)))))
>>> p.filter(lambda x: x%2 == 1)
>>> p
Rlist(1, Rlist(3))
"""
if not fn(self.first):
self.first = self.rest.first
self.rest = self.rest.rest
self.filter(fn)
elif self.rest is Rlist.empty:
return
elif not fn(self.rest.first):
if self.rest.rest is Rlist.empty:
self.rest = Rlist.empty
else:
self.rest.first = self.rest.rest.first
self.rest.rest = self.rest.rest.rest
self.filter(fn)
else:
self.rest.filter(fn)
This problem was really difficult so definitely don’t feel discouraged if you weren’t able to come up with a solution. Here is my thought process for when I tried to solve the problem:
I looked at many different cases (as seen by my doctests) and determined several things. You need to make sure that both the current element, and the next element are both valid (meaning that they are either valid because of the function or they are the empty rlist).
First, we check to see if the first element is not valid. If it’s not, we need to adjust some
pointers such that we can check the next value. After reassigning the first and rest, we can simply call
self.filter(fn)
again since we have reduced the length of the rlist by 1. Because of this, we won’t reach
infinite recursion because our rlist is getting smaller.
In the second case, I check to see if the next item is valid. If it isn’t and the next, next item is the empty,
then I can simply set my rest
to be the empty list and be done. If there are more elements after the next, next
item, then we reassign the next element, and recursively call self.filter(fn)
again.
Finally, if the first and second elements are both valid, we can move on and call filter
on the rest of the list
which we see in the final else
clause.
I don't claim to be perfect so if you find an error on this page, please send me an email preferably with a link to this page so that I know what I need to fix!