Mutating the list

Question

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?

Answer 1

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)

Answer 2

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)

Answer 3

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])

• overexchange: Canyou make my code recursively more elegant without closure?let me think of performance issues later.
• overexchange: yes I ran the test
• Gareth Rees: There's no need to import doctest as you can run doctests from the command line using python -m doctest myprogram.py.