map/filter/reduce/lambda opinions and background unscientificmini-survey

[Steven D'Aprano]

Yes, but where should they go? Adding functions in the standard
library is one thing. Adding builtins is another. Builtins make every
python process heavier. This may not matter on your desktop, but
Python gets used in embedded applications as well, and it does
there. Builtins also clutter the namespace. Nothing really wrong with
that, but it's unappealing.

I'd say that removing functions is a bad thing. On the other hand, I'd
say moving them from builtins to the standard library when Python has
functionality that covers most of the use cases for them is a good
thing.

The latter has occured for map, filter, and reduce. Lambda I'm not so
sure of, but it gets swept up with the same broom. Moving the first
three into a library module seems like a good idea. I'm not sure about
removing lambda. Removing map, filter and reduce remove most of my
use cases for it. But not all of them.

Metoobe!!!

Practicality beats purity: I am perfectly happy to have
list comps in the language and fast, efficient
functional programming tools in a module. I'm even
happy to see sum and product and zip as builtins, even
though logically they belong with map and reduce in the
(hypothetical) functional module.

I know Python isn't, and never will be, a purely
functional language. But being able to use some
functional techniques is good, and shouldn't be lost.

 

[Robert Kern]

But the Python 3000 plan, at least what we've heard of it so far, isn't
to move it to a standard library module. It's to remove it altogether,
replacing it with sum and product. Since sum and product don't cover
all the uses cases for reduce, this is a case of taking one function
that handles all the required use cases and replacing it with _two_
functions that don't. Since it's doubling the footprint of the reduce
functionality, arguments about avoiding pollution are red herrings.

Four, in fact. sum(), product(), any(), and all().

The problem with this discussion is that no one is saying anything
new[1]. We've heard all of the arguments for and against removing these
functions. Over and over and over again. They're not changing anyone's
mind, not yours, not mine, and definitely not Guido's.

And it's not even like Python 3000 is around the corner or in any stage
of concrete planning. Adding our voices to the chorus *now* won't make a
bit of difference, nor should it. The size of the chorus doesn't matter;
Python isn't developed by votes. We tried that once before; it didn't
work so well.

When planning for Python 3000 really gets going, when Guido gets a
year's sabbatical to work on it, when we can see how
map/filter/reduce/lambda fit into the whole scheme of how this new
language works, *then* is the time to be having these discussions. Right
now, all we're doing is making each other bitter and angry for no good
reason.

[1] Okay, there was that guy who predicted that list comprehensions and
first-class functions were the next to go. That was new. But also wrong.
I think we can discount that.

--
Robert Kern
(e-mail address removed)

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

 

[Carl Banks]

The shamelessness with which you inflated the verbosity of the latter
is hilarious.
[snip]

[ x**2 + y**2 for (x,y) in izip(xlist,ylist) ]

Now there's no longer much advantage in conciseness for the map version
(seeing that you'd have to define a function to pass to map), and this
is more readable.

If you're doing heavy functional programming,
listcomps are tremendously unwieldy compared to
map et al.

Having a dollar each way I see

Don't think so. The verbosity I spoke of was your describing the code
snippets in English, not the conciseness of the example. map and
friends are more concise than listcomps, I wasn't arguing that, except
that for the typical Pythonic use of listcomps it isn't much. One
listcomp or one call to map is not "heavily functional."

 

[Carl Banks]

Interesting; could you post an example of this? Whenever I try to think
of that, I come up with unwieldly syntax for the functional case. In
purely functional code the results of map/filter/etc would probably be
directly used as arguments to other functions, which might make the
calls longer than I'd consider pretty. This is especially true with
lots of lambda-ing to declare temporary expressions.

I suspect you're misunderstanding what I mean by heavily functional.

You appear to see maps and listcomps merely as a shortcut for a for
loop. You're comparing the map shortcut and the listcomp shortcut and
seeing which one's less verbose. In a mostly procedural program which
uses functional constructs in isolation, listcomps are going to win
most of those battles.

Heavily functional programming is a different mindset altogether. In
heavily functional programming, things like maps and filters and
function applications are actually what you're thinking about. map
isn't an indirect way to do a for loop; it's a direct way to do a map.

When your mind is focused on "applying a function to each member of
this list and returning a list of the results" as opposed to
"convenient shortcut to a for loop", map is going to be far superior to
a listcomp. And when you're doing dozens and dozens of maps over a
large purely functional program, you don't want to write out a listcomp
every single time you want to do it.

 

[Terry Hancock]

I personally think that map looks clearer than a list comprehension for
a simple function call, e.g.

I have to disagree

map(str, sequence)

This says "call a function 'map' on 'str' and 'sequence'"

Which, syntactically, is not terribly informative.

I have to remember:

* "str" is actually a callable
* "map" is a mathematical concept of linking one thing to another. What
things? "str to sequence"? No! Wrong guess. "str" is the "mapping function",
and the result is the thing sequence is to be linked to.

Now, sure, I know all this, and I learned what "map" did from the manual,
but it's not especially easy to remember.

This on the other hand,

[str(x) for x in sequence]

is practically plain English:

"call the function "str" on x, for every x in sequence"

Other than chopping out a few words, and using the () operator instead
of "call", it's hard to imagine this being any closer to exactly what you
would say to describe the operation. And for most of us, English comes
easier than Computer Science jargon.

 

[Tom Anderson]

Four, in fact. sum(), product(), any(), and all().

I'll just chip in and say i'd quite like a flatten(), too; at the moment,
i have one like this:

def flatten(ll):
return reduce(lambda a, l: a.extend(l), ll, [])

A builtin, which had fast special-case code for then the argument is a
list of lists (rather than an iterable of iterables), would be nice, since
this is a reasonably big use of reduce for me.

How would one do that as a list comp, by the way? I'm really not very good
with them yet.

[1] Okay, there was that guy who predicted that list comprehensions and
first-class functions were the next to go. That was new. But also wrong.
I think we can discount that.

True. Guido will only get rid of those after he's got rid of lowercase
letters in identifiers.

tom

 

[Peter Hansen]

This on the other hand,

[str(x) for x in sequence]

is practically plain English:

"call the function "str" on x, for every x in sequence"

Other than chopping out a few words, and using the () operator instead
of "call", it's hard to imagine this being any closer to exactly what you
would say to describe the operation. And for most of us, English comes
easier than Computer Science jargon.

And with a better choice of names than "x", that line becomes even more
self-documenting.

[str(parrot) for parrot in sequence], for example, tells you much more
about what is going on than str(x) does.

Exactly what, I have no idea... but it says _so_ much more. ;-)

-Peter

 

[George Sakkis]

I'll just chip in and say i'd quite like a flatten(), too; at the moment,
i have one like this:

def flatten(ll):
return reduce(lambda a, l: a.extend(l), ll, [])

This doesn't work; a.extend() returns None, not the extended list a:

seq = [[1,2],[3],[],[4,[5,6]]]
flatten(seq)

AttributeError: 'NoneType' object has no attribute 'extend'

This works for 1-level flattening:

def flatten(ll):
return reduce(lambda a, l: a.extend(l) or a, ll, [])
[1, 2, 3, 4, [5, 6]]

And finally for recursive flattening:

def flatten(seq):
return reduce(_accum, seq, [])

def _accum(seq, x):
if isinstance(x,list):
seq.extend(flatten(x))
else:
seq.append(x)
return seq
[1, 2, 3, 4, 5, 6]


George

 

[Christopher Subich]

[str(parrot) for parrot in sequence], for example, tells you much more
about what is going on than str(x) does.

Exactly what, I have no idea... but it says _so_ much more. ;-)

Yarr! Avast! Etc!

 

[Christopher Subich]

I suspect you're misunderstanding what I mean by heavily functional.

Heavily functional programming is a different mindset altogether. In
heavily functional programming, things like maps and filters and
function applications are actually what you're thinking about. map
isn't an indirect way to do a for loop; it's a direct way to do a map.

That's true; I'm more comfortable with procedural programming in
general, but I had a few classes that used LISP and understand what
you're talking about.

That said, Python itself is mostly a procedural language, with the
functional tools really being bolted on[1]. When we're talking about
Py3K, I think we're really talking about a redesign and rethink of
pretty much the entire language -- with list and generator
comprehensions, for procedural programming the need for map and lambda
goes away. Reduce isn't directly replaced, of course, but a for-loop
implementation (for procedural programming) is clearer, more powerful,
more explicit, and possibly faster.

That said, I very much like the idea of putting map and filter in a
functional module. For applications like functional-style programming
where map/etc are clearer, that keeps them in the library for efficient
use, yet it leaves the native language with OO(g)WTDI [Only One (good)
Way to Do It].

[1] -- lambda excepted. I think it's kind of cute, in a baby-mammal
kind of way.

 

[Steven Bethard]

Well, reduce covers 100% of them, and it's one function, and it's
already there.

And it's almost two times slower:

$ python -m timeit -s "x = xrange(1000)" "sum(x)"
10000 loops, best of 3: 92.5 usec per loop

$ python -m timeit -s "from operator import add; x = xrange(1000)"
"reduce(add, x)"
10000 loops, best of 3: 157 usec per loop

And that's only if I have the sense to import from operator:

$ python -m timeit -s "x = xrange(1000); add = lambda x, y: x + y"
"reduce(add, x)"
1000 loops, best of 3: 587 usec per loop

Note that the simple for-loop beats the case where you define your own
function because it doesn't have the repeated overhead of function calls
(which are expensive in Python):

$ python -m timeit -s "sum = 0; x = xrange(1000)" "for i in x: sum += i"
10000 loops, best of 3: 291 usec per loop

What would really help here is if you could identify the cases where you
think reduce is really a gain. A lot of them are actually not good
practice in Python because of the function-call overhead. However, I'm
willing to be convinced otherwise with a few good examples.

STeVe

 

[Erik Max Francis]

And it's almost two times slower:

That's because you're not using operator.add.

 

[Carl Banks]

That said, Python itself is mostly a procedural language, with the
functional tools really being bolted on[1].

[etc., snip]


Yeah, that's pretty much what I said in the first place.

 

[Ron Adam]

And finally for recursive flattening:

def flatten(seq):
return reduce(_accum, seq, [])

def _accum(seq, x):
if isinstance(x,list):
seq.extend(flatten(x))
else:
seq.append(x)
return seq


[1, 2, 3, 4, 5, 6]


George

How about this for a non recursive flatten.

def flatten(seq):
s = []
while seq:
while isinstance(seq[0],list):
seq = seq[0]+seq[1:]
s.append(seq.pop(0))
return s

seq = [[1,2],[3],[],[4,[5,6]]]
flatten(seq)


Ron

 

[Steven Bethard]

That's because you're not using operator.add.

Huh? Please re-read my post. That's exactly what I used.

STeVe

 

[mcherm]

Lambda is no more an obscure name than "function", "decorator", "closure",
"class", or "module". The first time you come across it, you don't know
what it means. Then you learn what it means, and then you know.

I believe you've made two errors here. First of all, "lambda" is part
of the Python language, while "function", "decorator", "closure", and
"module" are not. The fact that some words which are NOT part of the
Python language are obscure has no bearing whatsoever on "lambda". The
obnubilation created by this comparison is an obscure word also, but,
it isn't relevent to the Python language.

The second error is that I believe most english speakers COULD provide
a definition for the fairly common words "function", "class", and
"decorator". The exact meaning of "class" might not be what they expect
at first, but exposure to any object oriented language would make the
concept quickly familiar. But "lambda" has a very clear meaning... it's
a letter of the greek alphabet. The connection between that letter and
anonymous functions is tenuous at best, and fails the test of making
Python read like "executable pseudocode".

-- Michael Chermside

 

[Tom Anderson]

I'll just chip in and say i'd quite like a flatten(), too; at the moment,
i have one like this:

def flatten(ll):
return reduce(lambda a, l: a.extend(l), ll, [])

This doesn't work; a.extend() returns None, not the extended list a:

Ah, no, very good, i was hoping someone would notice that. Well done.

I think my lambda looks more like lambda a, b: a + b, but i realised the
other day that extend could make it more efficient, and didn't think it
through properly.

tom

 

[Steven D'Aprano]

I believe you've made two errors here. First of all, "lambda" is part
of the Python language, while "function", "decorator", "closure", and
"module" are not.

Sorry, but you are mistaken. "lambda" is a _reserved_ word in the
Python language, while "function" etc are not, but they are certainly
part of the language. Try explaining what def and import do without
using the words "function" or "module". Maybe you can do it, using
circumlocutions, but it isn't easy, and costs clarity.

[snip]

The second error is that I believe most english speakers COULD provide
a definition for the fairly common words "function", "class", and
"decorator". The exact meaning of "class" might not be what they expect
at first,

Function, in the sense of a mathematical function, I agree. Class as in
the thing you go to at school and decorator as in the person who advises
you what colour curtains to have, certainly. But in the Python sense? No.
Especially not decorator, which I believe most _programmers_ would have
trouble explaining, let alone non-programmer English speakers. I know I do.

but exposure to any object oriented language would make the
concept quickly familiar.

Just as exposure to functional languages would make lambda very familiar.

But "lambda" has a very clear meaning... it's
a letter of the greek alphabet. The connection between that letter and
anonymous functions is tenuous at best, and fails the test of making
Python read like "executable pseudocode".

Think back to when you were a schoolboy at your first day of school.
Unless you had a very unusual upbringing, you probably had never heard the
word "function" before. There is nothing about the word "function" that
brings to mind "a mathematical entity which transforms a variable into a
different variable", let alone "a programming subroutine that returns a
result". (Or for that matter, "the purpose which a person or thing is
for", as in the function of a spanner is to tighten nuts on bolts.)

You had to learn that word, discover what it means, and then it becomes
familiar. You don't notice the process only because it happened so long
ago, at an age that your brain was operating in "language acquisition
mode" and picking up vocabulary at an incredible rate.

There is nothing about the word "string" that especially brings to mind
"an array of bytes representing characters". The analogy of "string of
characters" to "string of beads" breaks down as soon as you have multiple
lines of text. And as for float, that's what boats do, heaven only knows
what it has to do with numbers.

(Yes, I know what it has to do with numbers. But that is something I had
to learn, and even now I still have difficulty because I expect floats to
operate like mathematical real numbers, and they don't.)

And dare I say it, what do constricting snakes have to do with programming?

I won't say that the anonymous function meaning of lambda comes to my mind
before the Greek letter, but it isn't very far behind, and rapidly
catching up. (I use lambda a lot more than I speak Greek.) It wouldn't
surprise me if one day I think of Python programming before the Greek
letter, just as the world aleph brings to my mind the sense of infinity
before the sense of it being a Hebrew letter.

 

[Tom Anderson]

And finally for recursive flattening:

def flatten(seq):
return reduce(_accum, seq, [])

def _accum(seq, x):
if isinstance(x,list):
seq.extend(flatten(x))
else:
seq.append(x)
return seq

flatten(seq)

[1, 2, 3, 4, 5, 6]

How about this for a non recursive flatten.

def flatten(seq):
s = []
while seq:
while isinstance(seq[0],list):
seq = seq[0]+seq[1:]
s.append(seq.pop(0))
return s

seq = [[1,2],[3],[],[4,[5,6]]]
flatten(seq)

The trouble with these is that they make a lot of temporary lists -
George's version does it with the recursive calls to flatten, and Ron's
with the slicing and concatenating. How about a version which never makes
new lists, only appends the base list? We can use recursion to root
through the lists ...

def isiterable(x):
return hasattr(x, "__iter__") # close enough for government work

def visit(fn, x): # perhaps better called applytoall
if (isiterable(x)):
for y in x: visit(fn, y)
else:
fn(x)

def flatten(seq):
a = []
def appendtoa(x):
a.append(x)
visit(appendtoa, seq)
return a

If you hate recursion, you can write a non-recursive version of visit;
you'll have to manage a stack of lists yourself, though. Something like:

def visit(fn, x):
if (not isiterable(x)): x = (x,)
stack = [None] # stack of iterators
cur = iter(x) # current iterator
while (cur != None):
try:
thing = cur.next()
if (isiterable(thing)):
stack.append(cur)
cur = iter(thing)
else:
fn(thing)
except StopIteration:
cur = stack.pop()

There might be a cleverer way to do this.

tom

 

[Terry Hancock]

Sorry, but you are mistaken. "lambda" is a _reserved_ word in the
Python language, while "function" etc are not, but they are certainly
part of the language. Try explaining what def and import do without
using the words "function" or "module". Maybe you can do it, using
circumlocutions, but it isn't easy, and costs clarity.

This is still a relevant distinction. One relevant point is that I am
perfectly free to use, say, the Spanish or Chinese word to describe
"module" or "function", but the keywords "def" and "import" will
remain the same.

Function, in the sense of a mathematical function, I agree. Class as in
the thing you go to at school and decorator as in the person who advises
you what colour curtains to have, certainly. But in the Python sense? No.
Especially not decorator, which I believe most _programmers_ would have
trouble explaining, let alone non-programmer English speakers. I know I do.

The "Python sense" is not arbitrary. There are very direct visual or logical
(i.e. INTUITIVE) connections between these words' *English* meanings (not
just mathematical, either) and their meanings in Python.

A "Function" is (in English) (kdict-gcide*):
1.) The act of executing or performing any duty, office, or
calling; performance....
2.) The appropriate action of any special organ or
part of an animal or vegetable organism...
[...]
5.) (math) A quantity so connected with another quantity,
that if any alteration be made in the latter there will be
a consequent alteration in the former.

The programming use is probably *closer* to the English meaning
than the math jargon meaning (except in the sense of "functional
programming" which leans more on the math meaning.

Similarly, "decorate" is 'make more attractive by adding ornament, colour, etc.'
In Python, a "decorator" applies a wrapper to a function to provide it with
some additional functionality. The function definition is furthermore
"decorated" with the decorator declaration to give it more meaning, which
is arguably more aesthetically pleasing (otherwise, why not literally wrap
with a function after defining the function?). These meanings are very
connected with the English definition of the word.

"Class" can, of course, mean a room in which you teach classes, but again
Webster's will certainly provide meaning much closer to the programming
term:

1. A group of individuals ranked together as possessing
common characteristics...

[2 is the class of students sense]

3. A comprehensive division of animate or inanimate objects,
grouped together on account of their common
characteristics
4. A set; a kind or description, species or variety.

Meanings 1,3, & 4 are all arguably intimately connected to the OOP meaning,
especially meaning #3 which even mentions "objects". (And I won't bother
to point out that the English meaning of "object" is tied closely to what it
means in programming).

A similar argument can be made for "object", "module", "script", and
even "method" and "program".

Now, if you are armed ONLY with the English definition, you will possibly
run into some trouble, because the programming usage is a *specialization*
of the term -- we strictly take only *one* of the English definitions to apply,
and we narrow its meaning a bit. "Objects" in computer science never means
"the purpose of the program" nor does it ever refer to "a small brick", even
though the English word can mean both of those things. But it's not exactly
a shocker that a programming term is going to apply to things you can find
in a program, so I don't think we're stumping the newbie with such terms.


"lambda" has no such advantage. Here's the *entire* gcide definition:

Lambda \Lamb"da\, n. [NL., fr. Gr. la`mbda.]
1. The name of the Greek letter [Lambda], [lambda],
corresponding with the English letter L, l.
[1913 Webster]

2. (Anat.) The point of junction of the sagittal and lambdoid
sutures of the skull.
[1913 Webster]

3. (Phys.) A subatomic particle carrying no charge, having a
mass equal to 2183 times that of an electron; it decays
rapidly, typically forming a nucleon and a pion. --MW10
[PJC]

Lambda moth (Zool.), a moth so called from a mark on its
wings, resembling the Greek letter lambda ([Lambda]).
[1913 Webster]

Just as exposure to functional languages would make lambda very familiar.

Yeah, well, there *is* an entry in the "Online Dictionary of Computing":

LAMBDA
A version of typed lambda-calculus, used to describe
semantic domains.
["Outline of a Mathematical Theory of Computation",
D.S. Scott, TM PRG-2, PRG, Oxford U, 1971].

If even this means what "lambda" does in Python, I would be surprised,
certainly it doesn't mean a whole lot to me.

Think back to when you were a schoolboy at your first day of school.
Unless you had a very unusual upbringing, you probably had never heard the
word "function" before.

Total BS. I knew the word "function" in it's English language sense, probably
by the time I was 6. I *know* my kids know it.

There is nothing about the word "function" that
brings to mind "a mathematical entity which transforms a variable into a
different variable",

They'll get this in about the 6th grade, IIRC.

let alone "a programming subroutine that returns a
result".

It also *does something*, which is what my first understanding of a "function"
was. Side-effects would seem to be perfectly natural to anyone with an
English language background, I guess. ;-)

(Or for that matter, "the purpose which a person or thing is
for", as in the function of a spanner is to tighten nuts on bolts.)

You are really stretching if you think kids (let alone average adults) don't
know this meaning of the word "function".

You had to learn that word, discover what it means, and then it becomes
familiar. You don't notice the process only because it happened so long
ago, at an age that your brain was operating in "language acquisition
mode" and picking up vocabulary at an incredible rate.

If you're arguing that language is acquired rather than innate, you
are bludgeoning an obvious point. The point is that *jargon* should
ideally derive in a natural way from commonly-used language, if
we want it to be easy to acquire for people who don't learn programming
between the ages of 1 and 5 as we learn our native languages. Even
in the 21st century, I think this includes just about all of us. ;-)

There is nothing about the word "string" that especially brings to mind
"an array of bytes representing characters". The analogy of "string of
characters" to "string of beads" breaks down as soon as you have multiple
lines of text.

Ah, but that's useful. "Strings" AREN'T "multiple lines of text" in the
computer's memory, are they? '\n' is just another bead. The "multiple
lines" is a representation, or way of laying out the beads. Very useful
distinction, and immediately driven by the choice of analogy.

I'm going to use that, thanks. ;-)

And as for float, that's what boats do, heaven only knows
what it has to do with numbers.

Ah, yes. Here, it is clear that Fortran whips Python on readability, it
calls them "reals". The only problem is that real mathematicians probably
had conniption fits about the fact that "real" variables actually represent
"rational" numbers.

(Yes, I know what it has to do with numbers. But that is something I had
to learn, and even now I still have difficulty because I expect floats to
operate like mathematical real numbers, and they don't.)

And dare I say it, what do constricting snakes have to do with programming?

Nothing. Then again *we* know that "Python" hasn't anything to do
with snakes, either. ;-D

I won't say that the anonymous function meaning of lambda comes to my mind
before the Greek letter, but it isn't very far behind, and rapidly
catching up. (I use lambda a lot more than I speak Greek.) It wouldn't
surprise me if one day I think of Python programming before the Greek
letter, just as the world aleph brings to my mind the sense of infinity
before the sense of it being a Hebrew letter.

Then it is clearly *not you* who should be served by the naming scheme.
Anyone so deeply trained and experienced should be expected to adapt,
you have the wherewithall to do so. It is the new user for whom the clarity
of the jargon is so important.

Personally, I find the term "anonymous function" to be a whole lot clearer
than "lambda" or "lambda function". Indeed, if asked what "lambda" means,
my reply is it's a "stupid name for an anonymous function", and if my
listener is less savvy "for a function that doesn't have a name, because you
only use it once".

Having said that, I too will miss the *concept* of an anonymous function,
although I wouldn't mind at all if its name changed, or if it were somehow
integrated into the "def" keyword's usage. Using backticks or some other
syntax delimiter also sounds promising, although we're sort of running out
of them. ;-)