Python weirdness involving map and reduce

Question

Sorry for the vague title, but I really have no idea what's going on here.

from functools import reduce

arr = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

def strxo(n):
    if (n == -1):
        return "X"
    elif (n == 1):
        return "O"
    else:
        return "_"

def prboard(board):
    print(reduce(lambda x, y: x + "\n" + y, list(map(lambda l: reduce(lambda a, b: strxo(a) + strxo(b), l), board))))

prboard(arr)

Desired output:

___
___
___

Real output:

__
__
__

And when I change the final else on strxo to return str(n) instead of return "_" I get:

000
000
000

Which is what I would expect and the shape I want, but I want to replace those zeroes. What is causing this?

I don't understand how you're expecting to get 5 underscores out of calling a function three times. Or why the desired output is 5x3 in the first place while at the same time a 3x3 grid of 0s is the desired shape. — abarnert, Aug 09 '18 at 22:38
Step 1 of debugging: Rewrite your code so that it's readable. Ideally get rid of that functional style using `reduce` and use list comprehensions instead. But at the very least, split that monstrosity into multiple lines. — Aran-Fey, Aug 09 '18 at 22:40
Also, why are you doing this with `map` and `reduce` in the first place? Your outer `reduce` is just a less efficient and harder to understand `'\n'.join`, your `list(map(lambda…))` is a less efficient and harder to understand list comprehension, and your inner `reduce`… I'm not sure what it's supposed to be doing; why do you call `strxo` on the accumulated value here? And why does this all have to be one monstrous line, instead of breaking it up into smaller pieces you can understand and debug yourself? — abarnert, Aug 09 '18 at 22:41
@abarnert I did it that way because it's what I'm used to using in JavaScript, I'm coming back to python after a long time, so I was just trying to hash out a simple tic-tac-toe without looking too much up. Everyone on this post has been very helpful! — William Papsco, Aug 09 '18 at 22:59

juanpa.arrivillaga · Accepted Answer · 2018-08-09T22:54:52.897

6

The problem is that your inner most reduce function, the one acting on your sublists, is always turning the second argument to _:

lambda a, b: strxo(a) + strxo(b)

So, on the last element of that reduce, b is __, which gets turned into _!

You want to map strxo onto everything first, and then reduce using concatenation.

So you want something like this:

reduce(lambda x, y: x + "\n" + y, map(lambda l: reduce(lambda a, b: a + b, map(strxo, l)), board))

Note, I removed the unecessary call to list.

But more importantly, stop using reduce and the concatenation operator to join strings!

It is unnecessarily verbose, and it is inefficient to boot (it will have quadratic time complexity).

Instead, use:

joinstr = ''.join

Which is a perfectly fine function. Functional programming doesn't mean "use map and reduce everywhere possible".

So, here's some good functional programming:

joinstr = ''.join
join_newline = '\n'.join

def board_str(board):
    return join_newline(map(lambda l: joinstr(map(strxo,l)), board))

Better yet, you should just use list comprehensions, which are eminently functional constructs (Python stole them from Haskell, btw). It is frequently more readable than map + lambda:

def board_string(board):
    return join_newline([joinstr(map(strxo, l)) for l in board])

edited Aug 09 '18 at 22:54

answered Aug 09 '18 at 22:40

juanpa.arrivillaga

88,713
10
131
172

1

It turns the *second* argument into an underscore? Not the *first* one? – Aran-Fey Aug 09 '18 at 22:42
1

@Aran-Fey it turns *both*, that's the problem, so it never accumulates multiple things... – juanpa.arrivillaga Aug 09 '18 at 22:43
1

For the lazy, here's the readable, efficient, and correct implementation without any of that functional stuff: `print('\n'.join(''.join(strxo(n) for n in row) for row in arr))`. – Aran-Fey Aug 09 '18 at 22:47
1

@Aran-Fey I would use a list-comprehension, it is actually faster on CPython, due to some implementation details of course :) – juanpa.arrivillaga Aug 09 '18 at 22:52
1

I prefer to avoid hurting the readability with additional pairs of brackets... and hope that someday generators will have a `__length_hint__` (which I assume is the reason why `join` is faster with lists) :( – Aran-Fey Aug 09 '18 at 22:55
This is great, thanks! I was using all of those reduce and map functions because it's what I'm used to from JavaScript. I was getting all upset at how unreadable everything was, too. Python does have nicely readable syntax, I just have to use it! – William Papsco Aug 09 '18 at 22:57
2

@Aran-Fey it's because there's a "fast path" in the implementation if the container is already a list or tuple, otherwise, it calls list on it anyway! – juanpa.arrivillaga Aug 09 '18 at 22:58
1

also, "Functional programming doesn't mean "use map and reduce everywhere possible"." It's like you know me personally :') – William Papsco Aug 09 '18 at 23:00
1

@WilliamPapsco well, the Pythonic way would probably be to just use that one liner Aran showed. I was just demonstrating a functional style, which involves defining re-usable, referentially transparent functions. Python itself isn't heavily geared towards functional programing, it just takes the nice functional constructs like list comprehensions when they work well, but it is a very imperative oriented language I would say, if you code idiomatically – juanpa.arrivillaga Aug 09 '18 at 23:01
1

Technically, I'm not sure there's quadratic behavior. Recent CPython can sometimes eliminate it for string concat, and PyPy even more often, and they also both have hardcoded optimizations for very short strings. But still, "It _might_ not be quadratic (but will still be an order of magnitude slower than `join` because of the monstrously higher constant factor)" probably isn't a good reason to concatenate strings when you don't have to. :) – abarnert Aug 09 '18 at 23:06
2

@Aran-Fey Actually, the reason `join` is faster with lists is that (in CPython) `join` just turns anything you give it except a `list` or `tuple` into a `list`, so it can directly iterate the list-or-tuple internal storage array. And `[…]` is faster than `list(…)` (not by as much as it was in early 3.x, but still significantly so, and part of that is not eliminable because of silly semantic edge cases). – abarnert Aug 09 '18 at 23:08
Man, I had no idea `S.join` worked this way! What a useful function! As an example: `";".join(["a", "b", "c"])` returns `a;b;c` – William Papsco Aug 09 '18 at 23:15
1

@WilliamPapsco Or even `";".join('abc')`, because strings are iterable too. – abarnert Aug 10 '18 at 00:47

Python weirdness involving map and reduce

1 Answers1