We want to define a function `filter_rlist` that takes in a function and an rlist and returns a new rlist that keeps all the items that satisfy the given input function. For this, we will be using the functional representation of our rlists using tuples and we will have the following constructors and selectors to use:

``````empty_rlist = None

def rlist(first, rest):
return (first, rest)

def first(r):
return r[0]

def rest(r):
return r[1]
``````
``````def filter_rlist(fn, r):
"""
Takes in a function, fn, and an rlist, r.
Returns a new rlist that keeps all the elements
that satisfy the given function.

>>> r = rlist(1, rlist(4, rlist(5, rlist(3, rlist(9, empty_rlist)))))
>>> filter_rlist(lambda x: x % 2 == 0, r)
(4, None)
"""
``````

Toggle Solution

``````def filter_rlist(fn, r):
"""
Takes in a function, fn, and an rlist, r.
Returns a new rlist that keeps all the elements
that satisfy the given function.

>>> r = rlist(1, rlist(4, rlist(5, rlist(3, rlist(9, empty_rlist)))))
>>> filter_rlist(lambda x: x % 2 == 0, r)
(4, None)
"""
if r == empty_rlist:
return r
if fn(first(r)):
return rlist(first(r), filter_rlist(fn, rest(r)))
return filter_rlist(fn, rest(r))
``````

Basically, we want to check to see if the first element of our rlist satisfies the input function. If it does, then we need construct a new rlist, keeping the first element, and recursively applying the filter on the rest. If it does not satisfy the function, then we can just recurse on the rest and that will disregard the current element. Finally, our base case is when we have the `empty_rlist`. When we have an `empty_rlist`, we don’t have to filter anything else out because we’ve already filtered everything!

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!