map vs list; why different behaviour?

Question

In the course of implementing the "Variable Elimination" algorithm for a Bayes' Nets program, I encountered an unexpected bug that was the result of an iterative map transformation of a sequence of objects.

For simplicity's sake, I'll use an analogous piece of code here:

>>> nums = [1, 2, 3]
>>> for x in [4, 5, 6]:
...     # Uses n if x is odd, uses (n + 10) if x is even
...     nums = map(
...         lambda n: n if x % 2 else n + 10, 
...         nums)
...
>>> list(nums)
[31, 32, 33]

This is definitely the wrong result. Since [4, 5, 6] contains two even numbers, 10 should be added to each element at most twice. I was getting unexpected behaviour with this in the VE algorithm as well, so I modified it to convert the map iterator to a list after each iteration.

>>> nums = [1, 2, 3]
>>> for x in [4, 5, 6]:
...     # Uses n if x is odd, uses (n + 10) if x is even
...     nums = map(
...         lambda n: n if x % 2 else n + 10,
...         nums)
...     nums = list(nums)
...
>>> list(nums)
[21, 22, 23]

From my understanding of iterables, this modification shouldn't change anything, but it does. Clearly, the n + 10 transform for the not x % 2 case is applied one fewer times in the list-ed version.

My Bayes Nets program worked as well after finding this bug, but I'm looking for an explanation as to why it occurred.

Answer 1

The answer is very simple: map is a lazy function in Python 3, it returns an iterable object (in Python 2 it returns a list). Let me add some output to your example:

In [6]: nums = [1, 2, 3]

In [7]: for x in [4, 5, 6]:
   ...:     nums = map(lambda n: n if x % 2 else n + 10, nums)
   ...:     print(x)
   ...:     print(nums)
   ...:     
4
<map object at 0x7ff5e5da6320>
5
<map object at 0x7ff5e5da63c8>
6
<map object at 0x7ff5e5da6400>

In [8]: print(x)
6

In [9]: list(nums)
Out[9]: [31, 32, 33]

Note the In[8] - the value of x is 6. We could also transform the lambda function, passed to map in order to track the value of x:

In [10]: nums = [1, 2, 3]

In [11]: for x in [4, 5, 6]:
   ....:     nums = map(lambda n: print(x) or (n if x % 2 else n + 10), nums)
   ....:     

In [12]: list(nums)
6
6
6
6
6
6
6
6
6
Out[12]: [31, 32, 33]

Because map is lazy, it evaluates when list is being called. However, the value of x is 6 and that is why it produces confusing output. Evaluating nums inside the loop produces expected output.

In [13]: nums = [1, 2, 3]

In [14]: for x in [4, 5, 6]:
   ....:     nums = map(lambda n: print(x) or (n if x % 2 else n + 10), nums)
   ....:     nums = list(nums)
   ....:     
4
4
4
5
5
5
6
6
6

In [15]: nums
Out[15]: [21, 22, 23]

Answer 2

The issue has to do with how the x variable is accessed by the lambda functions you are creating. The way Python's scoping works, the lambda functions will always use the latest version of x from the outside scope when they're called, not the value that it had when they were defined.

Since map is lazy, the lambda functions don't get called until after the loop (when you consume the nested maps by passing them to list) and so, they all use the last x value.

To make each lambda function save the value x has when they are defined, add x=x like this:

lambda n, x=x: n if x % 2 else n + 10

This specifies an argument and its default value. The default will be evaluated at the time the lambda is defined, so when the lambda gets called later (without a second argument), the x inside the expression will be that saved default value.

Answer 3

If you want to use the lazy version, you need to fix x in each loop. functools.partial does exactly that:

from functools import partial

def myfilter(n, x):
    return n if x % 2 else n + 10

nums = [1, 2, 3]
for x in [4, 5, 6]:
    f = partial(myfilter, x=x)
    nums = map(f, nums)

>>> list(nums)
[21, 22, 23]