1
\$\begingroup\$

For the following question, the function

• should mutate the original list

• should NOT create any new lists

• should NOT return anything

Functions 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.

Implement the function map_mut, which applies a function fn onto every element of a list called lst.

def map_mut(fn, lst):
"""Maps fn onto lst by mutation.
>>> lst = [1, 2, 3, 4]
>>> map_mut(lambda x: x**2, lst)
>>> lst
[1, 4, 9, 16]
"""
*** Your code here***

Below is the solution:

def map_mut(fn, lst):
    """Maps fn onto lst by mutation.

    >>> lst = [1, 2, 3, 4]
    >>> map_mut(lambda x: x**2, lst)
    >>> lst
    [1, 4, 9, 16]
    """
    def mutate(index):
        if len(lst) == index:
            return
        else:
            lst[index] = fn(lst[index])
            return mutate(index + 1)
    return mutate(0)
lst = [1, 2, 3, 4]
map_mut(lambda x: x**2, lst)

Can we improve this solution in recursive approach?

\$\endgroup\$
3
\$\begingroup\$

Eliminate the tail recursion. Python does not optimize tail calls so the recursion costs O(N) stack memory. You can achieve the requirements with a simple loop.

Your recursive solution could be expressed more concisely. Functions return None if they do not otherwise return a value.

def mutate(index):
    if index < len(lst):
        lst[index] = fn(lst[index])
        mutate(index + 1)
\$\endgroup\$
5
\$\begingroup\$

Your solution is too complicated. I would also say that it is not idiomatic Python, since it's using a weird technique to perform simple iteration. The problem does not call for a recursive approach, so you should not use recursion here.

def map_mut(fn, lst):
    """(docstring here)"""
    for index, value in enumerate(lst):
        lst[index] = fn(value)
\$\endgroup\$
2
\$\begingroup\$

You got the tests, what about running them?

It is useful to automatically run your tests, just

import doctest

# code

doctest.testmod()

As simple as possible

You are using closures and recursion and other mind-bending stuff while the function could be written:

def map_mut(fn, lst):
    """Maps fn onto lst by mutation.

    >>> lst = [1, 2, 3, 4]
    >>> map_mut(lambda x: x**2, lst)
    >>> lst
    [1, 4, 9, 16]
    """
    for index in range(len(lst)):
        lst[index] = fn(lst[index])
\$\endgroup\$
  • \$\begingroup\$ Canyou make my code recursively more elegant without closure?let me think of performance issues later. \$\endgroup\$ – overexchange May 3 '15 at 2:12
  • 1
    \$\begingroup\$ yes I ran the test \$\endgroup\$ – overexchange May 3 '15 at 9:03
  • 1
    \$\begingroup\$ There's no need to import doctest as you can run doctests from the command line using python -m doctest myprogram.py. \$\endgroup\$ – Gareth Rees May 4 '15 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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