-1
\$\begingroup\$

For the following question, the function

• should mutate the original list

• should NOT create any new lists

• should NOT return anything

Function that do not create new lists are said to be ”in place.” Such functions are often desirable because they do not require extra memory to operate.

Define "filter_mut", which takes a list and filters out elements that don’t satisfy a given predicate.

def filter_mut(pred, lst):
"""Filters lst by mutating it.
>>> lst = [1, 2, 3, 4]
>>> is_even = lambda x: x % 2 == 0
>>> filter_mut(is_even, lst)
>>> lst
[2, 4]
"""

Below is the solution:

def filter_mut(pred, lst):
    """Filters lst by mutating it.
    
    >>> lst = [1, 2, 3, 4]
    >>> is_even = lambda x: x % 2 == 0
    >>> filter_mut(is_even, lst)
    >>> lst
    [2, 4]
    """
    def filter(index):
        if index == len(lst) - 1:
            return        
        elif pred(lst[index]):
            filter(index + 1)         
        else:
            lst[index:] = lst[index + 1:]
            filter(index)
    filter(0)

lst = [1, 2, 3, 4]
is_even = lambda x: x % 2 == 0
filter_mut(is_even, lst)
print(lst)

Can we make this code more elegant in recursive approach? Basically I would like to avoid inner function filter.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Your current approach doesn't meet the requirements of the task - it does create new lists (the slice lst[index + 1:] creates one). Additionally, it fails to filter the last element. This is tricky to do recursively and neatly within the guidelines, unless you allow an additional index=0 parameter to filter_mut. \$\endgroup\$
    – jonrsharpe
    May 4 '15 at 9:06
  • \$\begingroup\$ Isnt lst[index + 1:] creating new list? \$\endgroup\$
    – lovesh
    May 4 '15 at 9:09
  • 3
    \$\begingroup\$ You haven't taken account of the advice in the answer you accepted to your last question. \$\endgroup\$ May 4 '15 at 9:10
  • \$\begingroup\$ lst[index + 1:] does not create new list. \$\endgroup\$ May 4 '15 at 10:30
  • \$\begingroup\$ @overexchange yes, it does. See the tutorial: "All slice operations return a new list containing the requested elements." \$\endgroup\$
    – jonrsharpe
    May 4 '15 at 12:37
2
\$\begingroup\$

The following implementation works, meets the requirements of the task, and is slightly neater than the current approach:

def filter_mut(pred, lst):
    """Filters lst by mutating it.

    >>> lst = [1, 2, 3, 4]
    >>> is_even = lambda x: x % 2 == 0
    >>> filter_mut(is_even, lst)
    >>> lst
    [2, 4]
    """
    def filter(index):
        if index < len(lst):  
            if pred(lst[index]):
                index += 1
            else:
                lst.pop(index)
            filter(index)
    filter(0)

If you allow a modification of the function definition, you can neaten it up further (and remove the current reliance on the function closure):

def filter_mut(pred, lst, index=0):
    """Filters lst by mutating it.

    >>> lst = [1, 2, 3, 4]
    >>> is_even = lambda x: x % 2 == 0
    >>> filter_mut(is_even, lst)
    >>> lst
    [2, 4]
    """
    if index < len(lst):  
        if pred(lst[index]):
            index += 1
        else:
            lst.pop(index)
       filter_mut(pred, lst, index)

However, compare that to a non-recursive solution:

def filter_mut(pred, lst):
    """Filters lst by mutating it.

    >>> lst = [1, 2, 3, 4]
    >>> is_even = lambda x: x % 2 == 0
    >>> filter_mut(is_even, lst)
    >>> lst
    [2, 4]
    """
    for index in range(len(lst)-1, -1, -1):
        if not pred(lst[index]):
            lst.pop(index)
\$\endgroup\$
4
  • \$\begingroup\$ Can I have something else instead of using existing functionality pop()? I mean how do I remove an element from list? In specific last element? \$\endgroup\$ May 4 '15 at 10:46
  • \$\begingroup\$ @overexchange del list[index]? \$\endgroup\$
    – jonrsharpe
    May 4 '15 at 11:08
  • \$\begingroup\$ how do I delete any element at particular index? am not sure what del is? \$\endgroup\$ May 4 '15 at 11:09
  • \$\begingroup\$ @overexchange I literally just told you that. What exactly is the problem? \$\endgroup\$
    – jonrsharpe
    May 4 '15 at 11:10
2
\$\begingroup\$

A quick nitpick about the phrasing

Function that do not create new lists are said to be ”in place.” Such functions are often desirable because they do not require extra memory to operate.

This is not strictly true. Any function that modifies its input as its primary output is in-place. Consider list.sort:

help(list.sort)
#>>> Help on method_descriptor:
#>>>
#>>> sort(...)
#>>>     L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*
#>>>

list.sort does store auxillary data structures.

So, technically

def filter_mut(pred, lst):
    lst[:] = filter(pred, lst)

would actually be valid (although outside of the spirit of the question) even on Python 2, where it returns a list.

Your use of the inner function is avoidable by using a default variable:

def filter_mut(pred, lst, index=0):
    if index == len(lst) - 1:
        return
    elif pred(lst[index]):
        filter_mut(pred, lst, index + 1)
    else:
        lst[index:] = lst[index + 1:]
        filter_mut(pred, lst, index)

However, this is not advisable. There is nothing wrong with inner functions.

But let's consider what you've done by using recursion. Hopefully you're aware that as you recurse a stack is built up:

fiter(0)
→ filter(1)
  → filter(2)
    → ...

This is stored in a list-like structure (albeit optimized for the use-case). This means you're using \$\mathcal{O}(n)\$ auxillary memory! This damages the whole point of the question.

You should consider the cleaner and more efficient iterative solution. Doing so is idiomatic for Python:

def filter_mut(pred, lst):
    index = 0
    while index < len(lst):
        if pred(lst[index]):
            index += 1
        else:
            lst[index:] = lst[index + 1:]

The line

lst[index:] = lst[index + 1:]

will actually create a slice, which is a new list. This can be almost the size of the original! Instead,

del lst[index]

is more idiomatic (and faster).

You can simplify the loop by iterating backwards, since you don't need to conditionally change the iteration index:

def filter_mut(pred, lst):
    for index in reversed(range(len(lst))):
        if not pred(lst[index]):
            del lst[index]

Note that for this you are moving some elements \$\mathcal{O}(n)\$ times:

T F F T F F T F
| | | | | | | |
T F F T F F T F
|  / / / / / /
T F T F F T F
|  / / / / /
T T F F T F
| | | | | |
T T F F T F
| |  / / /
T T F T F
| |  / /
T T T F
| | |
T T T

You want to minimize the number of /s. One way is to move lazily:

T F F T F F T F
| | | | | | | |
T F F T F F T F
|   | | | | | |
T · F T F F T F
|     | | | | |
T · · T F F T F
|   /   | | | |
T T · · F F T F
| |       | | |
T T · · · F T F
| |         | |
T T · · · · T F
| |     /     |
T T T · · · · F
| | |
T T T · · · · ·
| | |
T T T

This only moves the wanted elements into place when they are needed, avoiding gratuitous moves. Here's an implementation:

def filter_mut(pred, lst):
    tail = 0

    for i in range(len(lst)):
        if pred(lst[i]):
            lst[tail] = lst[i]
            tail += 1

    del lst[tail:]

Note that since filter is lazy, this is actually exactly what

def filter_mut(pred, lst):
    lst[:] = filter(pred, lst)

does. If you're unable to use the built-in filter, there's a trivial implementation:

def filter(pred, items):
    for elem in items:
        if pred(elem):
            yield elem

def filter_mut(pred, lst):
    lst[:] = filter(pred, lst)

Which is the final, Pythonic solution.

\$\endgroup\$
1
  • \$\begingroup\$ As per my course assignment, I don't know yet, what yield is? Let me ignore this for sometime. \$\endgroup\$ May 4 '15 at 10:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.