Python memoization for functions that modify mutable arguments

Question

Say I have a function that modifies a list argument and a memoizer decorator, such as:

@memoizer
def add_1_to_list(list):
    for i in range(len(list)):
        list[i] += 1
    return list

In my main program, I have

list = [1, 1, 1, 1]
add_1_to_list(list)
print list

If my memoizer class only caches the return values and sets add_1_to_list to return the same value, then when I run the main program the first time, it will print [2, 2, 2, 2], while the second time, it will print [1, 1, 1, 1], since list is mutable.

Are there any solutions to get a memoizer class to detect that the function modifies an argument, that way we can note it and save modified arguments? I was able to see it visually by printing the argument before and after calling it in the memoizer class, but without knowing what type the arguments are and whether they are mutable/immutable, it seems difficult to test whether an argument has been modified or not.

Answer 1

The only possible answer to your question is don't. You are using memoization where memoization ought not be used.

Only memoize functions which have no side effects, or you're asking for trouble.

Are there any solutions to get a memoizer class to detect that the function modifies an argument?

It isn't the memoizer's responsibility to detect mutability, it is programmer's responsibility to decide whether or not to apply the memoizer to the function.

that way we can note it and save modified arguments

That sounds to me like over-complicating things. Besides, if you "save" modified arguments, you end up keeping references to them, preventing them from being deallocated.

Answer 2

Not sure how your memoizer is implemented, but you can use the function argument as the key to your cache memory. Something like:

def memoizer(func):

    mem = {}

    def wrapped(lst):
        key = tuple(lst)
        if key not in mem:
            print 'Actually computing for input %s...' % lst
            mem[key] = []
            mem[key][:] = func(lst)
        lst[:] = mem[key]
        return mem[key]
    
    return wrapped

@memoizer
def add_1_to_list(list):
    for i in range(len(list)):
        list[i] += 1
    return list

# Case 1
lst = [1, 1, 1, 1]
print 'Given', lst
print add_1_to_list(lst)
print add_1_to_list(lst)
print 'Finally lst is:', lst

# Case 2
lst = [1, 1, 1, 1]
print 'Given', lst
print add_1_to_list(lst)
print 'Finally lst is:', lst

Note that mem[key][:] will be necessary as add_1_to_list does not create a new list internally, so we need to make a copy of the result. lst[:] = mem[key] mimics the behavior of add_1_to_list which is to modify the given input list.

Output of Case 1:

Given [1, 1, 1, 1]

Actually computing for input [1, 1, 1, 1]...

[2, 2, 2, 2]

Actually computing for input [2, 2, 2, 2]...

[3, 3, 3, 3]

Finally lst is: [3, 3, 3, 3]

Now with some cache ready:

Given [1, 1, 1, 1]

[2, 2, 2, 2]

Finally lst is: [2, 2, 2, 2]