reduce() anomaly?

[Stephen C. Waterbury]

This seems like it ought to work, according to the
description of reduce(), but it doesn't. Is this
a bug, or am I missing something?

Python 2.3.2 (#1, Oct 20 2003, 01:04:35)
[GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-5)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.[color=blue][color=green][color=darkred]
>>> d1 = {'a':1}
>>> d2 = {'b':2}
>>> d3 = {'c':3}
>>> l = [d1, d2, d3]
>>> d4 = reduce(lambda x, y: x.update(y), l)[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'update'[color=blue][color=green][color=darkred]
>>> d4 = reduce(lambda x, y: x.update(y), l, {})[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'update'

- Steve.

[Alex Martelli]

Re: reduce() anomaly?

Stephen C. Waterbury wrote:
[color=blue]
> This seems like it ought to work, according to the
> description of reduce(), but it doesn't. Is this
> a bug, or am I missing something?[/color]

the latter.
[color=blue]
> Python 2.3.2 (#1, Oct 20 2003, 01:04:35)
> [GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-5)] on linux2
> Type "help", "copyright" , "credits" or "license" for more information.[color=green][color=darkred]
> >>> d1 = {'a':1}
> >>> d2 = {'b':2}
> >>> d3 = {'c':3}
> >>> l = [d1, d2, d3]
> >>> d4 = reduce(lambda x, y: x.update(y), l)[/color][/color][/color]

the update method returns None.
[color=blue]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'[/color]

right.
[color=blue][color=green][color=darkred]
> >>> d4 = reduce(lambda x, y: x.update(y), l, {})[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'[/color]

same issue.

If you want to abuse reduce at all costs for this purpose,
reduce(lambda x, y: x.update(y) or x, l) might work.


Alex

[David C. Fox]

Re: reduce() anomaly?

Stephen C. Waterbury wrote:
[color=blue]
> This seems like it ought to work, according to the
> description of reduce(), but it doesn't. Is this
> a bug, or am I missing something?
>
> Python 2.3.2 (#1, Oct 20 2003, 01:04:35)
> [GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-5)] on linux2
> Type "help", "copyright" , "credits" or "license" for more information.[color=green][color=darkred]
> >>> d1 = {'a':1}
> >>> d2 = {'b':2}
> >>> d3 = {'c':3}
> >>> l = [d1, d2, d3]
> >>> d4 = reduce(lambda x, y: x.update(y), l)[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'[color=green][color=darkred]
> >>> d4 = reduce(lambda x, y: x.update(y), l, {})[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'
>
> - Steve.[/color]

The update method updates the dictionary in place, but returns None.
Thus, after the first call to x.update(y), reduce is trying to call
x.update(y) with x equal to None. Hence the error.

Alternatives which work include

def rupdate(d, other):
d.update(other)
return d

reduce(rupdate, l)

and

d = {}
map(lambda x: d.update(x), l)

David

[Peter Otten]

Re: reduce() anomaly?

Stephen C. Waterbury wrote:
[color=blue]
> This seems like it ought to work, according to the
> description of reduce(), but it doesn't. Is this
> a bug, or am I missing something?
>
> Python 2.3.2 (#1, Oct 20 2003, 01:04:35)
> [GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-5)] on linux2
> Type "help", "copyright" , "credits" or "license" for more information.[color=green][color=darkred]
> >>> d1 = {'a':1}
> >>> d2 = {'b':2}
> >>> d3 = {'c':3}
> >>> l = [d1, d2, d3]
> >>> d4 = reduce(lambda x, y: x.update(y), l)[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'[color=green][color=darkred]
> >>> d4 = reduce(lambda x, y: x.update(y), l, {})[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> File "<stdin>", line 1, in <lambda>
> AttributeError: 'NoneType' object has no attribute 'update'
>
> - Steve.[/color]

No bug, your lambda evaluates d1.update(d2) on the first call and then
returns the result of the update() method which is None. So on the secend
call None.update(d3) fails. Here's what you might have intended:
[color=blue][color=green][color=darkred]
>>> d1 = {'a':1}
>>> d2 = {'b':2}
>>> d3 = {'c':3}
>>> l = [d1, d2, d3]
>>> d4 = reduce(lambda x, y: x.update(y) or x, l)
>>> d4[/color][/color][/color]
{'a': 1, 'c': 3, 'b': 2}

Note the side effect on d1
[color=blue][color=green][color=darkred]
>>> d1[/color][/color][/color]
{'a': 1, 'c': 3, 'b': 2}

if you don't provide an initial dictionary.

Peter

[Francis Avila]

reduce()--what is it good for? (was: Re: reduce() anomaly?)

"Alex Martelli" <aleax@aleax.it > wrote in message
news:3fbqb.9787 8$e5.3584611@ne ws1.tin.it...[color=blue]
> Stephen C. Waterbury wrote:
> If you want to abuse reduce at all costs for this purpose,
> reduce(lambda x, y: x.update(y) or x, l) might work.[/color]

Just out of curiosity, for what kind of problems do we find reduce to just
be the Right Way? I mean, summing a big list of numbers is fun and all, but
I never find any use for it otherwise. I *often* try to think if reduce
would be useful when I come across some collection-of-values manipulation
task, but usually one wants to repeat an operation on a whole set of values,
not reduce the set to one value.

So, are there any *non-trivial* and *unabusive* uses of reduce, where any
other way would be tedious, repetitive, slow, unclear, etc.? I'm very
curious to see them.

reduce--the black sheep of the functional-Python herd?
--
Francis Avila

[Erik Max Francis]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

Francis Avila wrote:
[color=blue]
> Just out of curiosity, for what kind of problems do we find reduce to
> just
> be the Right Way? I mean, summing a big list of numbers is fun and
> all, but
> I never find any use for it otherwise. I *often* try to think if
> reduce
> would be useful when I come across some collection-of-values
> manipulation
> task, but usually one wants to repeat an operation on a whole set of
> values,
> not reduce the set to one value.[/color]

I don't use reduce extremely routinely, but I certainly do find myself
using it. Grepping through my Python sources, the most common uses I
find are summing together lists of numeric values and joining together
(flattening) a list of lists (though only when the contained lists
themselves do not contain any sequences as elements).
[color=blue]
> So, are there any *non-trivial* and *unabusive* uses of reduce, where
> any
> other way would be tedious, repetitive, slow, unclear, etc.? I'm very
> curious to see them.[/color]

My cellular automaton engine CAGE uses reduce several times, although
admittedly this use is academic (obviously a good way to implement a
ReductionRule is almost by definition with a reduce operation :-). Even
then, there are times when, say, you want to get the sum of the states
of the cells in the neighborhood, and "neighborho od" is defined in a
sufficiently generic way that the states of the neighborhood are just a
list of state values.

My Solar System calculator BOTEC has a similar application; when
plotting courses, you can have an arbitrary number of transfers, and
those transfers can each have an arbitrary number of burns. So it's
quite convenient to do a reduce on the list of burns (a sequence of
sequences), and then a reduce on the list of deltavees for the transfers
(a sequence of numerics).

--
Erik Max Francis && max@alcyone.com && http://www.alcyone.com/max/
__ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
/ \ Thousands have lived without love, not one without water.
\__/ W.H. Auden

[Alex Martelli]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

Erik Max Francis wrote:
...[color=blue]
> Francis Avila wrote:
>[color=green]
>> Just out of curiosity, for what kind of problems do we find reduce to
>> just
>> be the Right Way? I mean, summing a big list of numbers is fun and
>> all, but
>> I never find any use for it otherwise. I *often* try to think if[/color][/color]
...[color=blue]
> I don't use reduce extremely routinely, but I certainly do find myself
> using it. Grepping through my Python sources, the most common uses I
> find are summing together lists of numeric values and joining together[/color]

In Python 2.3, we have sum for that (much faster, too).
[color=blue]
> (flattening) a list of lists (though only when the contained lists
> themselves do not contain any sequences as elements).[/color]

_UN_fortunately sums works for that too -- but almost as slowly as reduce.
E.g., on a small example:

[alex@lancelot bo]$ timeit.py -c -s'lol=[range(20)]*20'
'reduce(list.__ add__, lol, [])'
10000 loops, best of 3: 91 usec per loop

[alex@lancelot bo]$ timeit.py -c -s'lol=[range(20)]*20' -s'import operator'
'reduce(operato r.add, lol, [])'
10000 loops, best of 3: 88 usec per loop

[alex@lancelot bo]$ timeit.py -c -s'lol=[range(20)]*20' 'sum(lol, [])'
10000 loops, best of 3: 82 usec per loop

while a simple loop is way faster:

[alex@lancelot bo]$ timeit.py -c -s'lol=[range(20)]*20' 'x=[]' 'for l in
lol: x.extend(l)'
10000 loops, best of 3: 26 usec per loop

and can easily be sped up a little more:

[alex@lancelot bo]$ timeit.py -c -s'lol=[range(20)]*20' 'x=[]' 'xe=x.extend'
'for l in lol: xe(l)'
10000 loops, best of 3: 20 usec per loop


Given the typical use cases of reduce are covered by sum -- and sometimes
even better by simple loops &c -- then I would say that in Python 2.3 and
following reduce should not be used often at all.


Alex

[Alex Martelli]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

Francis Avila wrote:
...[color=blue]
> Just out of curiosity, for what kind of problems do we find reduce to just
> be the Right Way? I mean, summing a big list of numbers is fun and all,[/color]

And best handled by sum (in Python 2.3).
[color=blue]
> reduce--the black sheep of the functional-Python herd?[/color]

Nope -- apply beats it, given that in the last few years apply(f, args) is
best spelled f(*args) ...!-)


Alex

[Duncan Booth]

Re: reduce() anomaly?

"David C. Fox" <davidcfox@post .harvard.edu> wrote in
news:bjbqb.8185 6$mZ5.559701@at tbi_s54:
[color=blue]
> and
>
> d = {}
> map(lambda x: d.update(x), l)
>[/color]

which can be written more concisely without the lambda:

d = {}
map(d.update, l)

--
Duncan Booth duncan@rcp.co.u k
int month(char *p){return(1248 64/((p[0]+p[1]-p[2]&0x1f)+1)%12 )["\5\x8\3"
"\6\7\xb\1\x9\x a\2\0\4"];} // Who said my code was obscure?

[anton muhin]

Re: reduce()--what is it good for?

> Just out of curiosity, for what kind of problems do we find reduce to just[color=blue]
> be the Right Way? I mean, summing a big list of numbers is fun and all, but
> I never find any use for it otherwise. I *often* try to think if reduce
> would be useful when I come across some collection-of-values manipulation
> task, but usually one wants to repeat an operation on a whole set of values,
> not reduce the set to one value.
>
> So, are there any *non-trivial* and *unabusive* uses of reduce, where any
> other way would be tedious, repetitive, slow, unclear, etc.? I'm very
> curious to see them.
>
> reduce--the black sheep of the functional-Python herd?
> --[/color]

IMHO, not. Once I read an article that explains that foldr and
foldl---almost Python's reduce---are most important HOFs. Actually,
functions like map can be easily defined with reduce:

def my_map(func, seq):
return reduce(lambda seq, el: seq + [func(el)], seq, [])

print my_map(lambda x: 2*x, [1, 2, 3, 4, 5])

regards,
anton.

[Jeremy Fincher]

Re: reduce() anomaly?

Duncan Booth <duncan@NOSPAMr cp.co.uk> wrote in message news:<Xns942B93 E4AE037duncanrc pcouk@127.0.0.1 >...[color=blue]
> which can be written more concisely without the lambda:
>
> d = {}
> map(d.update, l)[/color]

Although he shouldn't be using map at all for this case; he's not
using the resulting list.

Just a plan for loop will suffice:

for otherDict in l:
d.update(otherD ict)

Jeremy

[Alex Martelli]

Re: reduce() anomaly?

Jeremy Fincher wrote:
[color=blue]
> Duncan Booth <duncan@NOSPAMr cp.co.uk> wrote in message
> news:<Xns942B93 E4AE037duncanrc pcouk@127.0.0.1 >...[color=green]
>> which can be written more concisely without the lambda:
>>
>> d = {}
>> map(d.update, l)[/color]
>
> Although he shouldn't be using map at all for this case; he's not
> using the resulting list.[/color]

Absolutely true.

[color=blue]
> Just a plan for loop will suffice:
>
> for otherDict in l:
> d.update(otherD ict)[/color]

And if one needs to get top performance, an _almost_ plain for loop
will give performance just as good as map (rather than, say, 15% worse
or so -- not a worry in 99.999% of the cases, of course...):

d_upda = d.update
for otherDictin l:
d_upda(otherDic t)

[the usual case of "manual constant subexpression hoisting" where the
constant subexpression is the attribute lookup for d.update ...).


Alex

[Bob Gailer]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

At 03:41 PM 11/5/2003, Francis Avila wrote:
[color=blue]
>"Alex Martelli" <aleax@aleax.it > wrote in message
>news:3fbqb.978 78$e5.3584611@n ews1.tin.it...[color=green]
> > Stephen C. Waterbury wrote:
> > If you want to abuse reduce at all costs for this purpose,
> > reduce(lambda x, y: x.update(y) or x, l) might work.[/color]
>
>Just out of curiosity, for what kind of problems do we find reduce to just
>be the Right Way? I mean, summing a big list of numbers is fun and all, but
>I never find any use for it otherwise. I *often* try to think if reduce
>would be useful when I come across some collection-of-values manipulation
>task, but usually one wants to repeat an operation on a whole set of values,
>not reduce the set to one value.
>
>So, are there any *non-trivial* and *unabusive* uses of reduce, where any
>other way would be tedious, repetitive, slow, unclear, etc.? I'm very
>curious to see them.[/color]

One's prior programming experience can affect one's view of reduce. My
favorite language, prior to Python, was APL. APL's native data container is
the array, and reduce is a native operator in APL. So we used reduce a lot,
sometimes to add things up, other times to check for all or any conditions,
other times for other at this moment forgotten purposes. A companion of
reduce in APL is scan, which did reduce but preserved all the intermediate
values (cumulative sum for example).

To expand your reduce horizons in Python, consider reduce as a way to
examine the relationship between successive pairs of a sequence. For
example one might wants the difference between successive elements: given
seq = [1,3,4,7] we'd like a differences == [2,1,3].

differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)

Bob Gailer
bgailer@alum.rp i.edu
303 442 2625


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.532 / Virus Database: 326 - Release Date: 10/27/2003

[David Eppstein]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

In article <mailman.507.10 68171071.702.py thon-list@python.org >,
Bob Gailer <bgailer@alum.r pi.edu> wrote:
[color=blue]
> To expand your reduce horizons in Python, consider reduce as a way to
> examine the relationship between successive pairs of a sequence. For
> example one might wants the difference between successive elements: given
> seq = [1,3,4,7] we'd like a differences == [2,1,3].
>
> differences = []
> def neighborDiffere nce(left, right):
> differences.app end(right - left)
> return right
> reduce(neighbor Difference, seq)[/color]

seq=[1,3,4,7]
[y-x for x,y in zip(seq,seq[1:])]

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

[Georgy Pruss]

Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)

seq=[1,3,4,7]
map( int.__sub__, seq[1:], seq[:-1] ) # nearly twice faster than ....zip.... for long arrays

G-:

"David Eppstein" <eppstein@ics.u ci.edu> wrote in message news:eppstein-D499AF.21573206 112003@news.ser vice.uci.edu...[color=blue]
> In article <mailman.507.10 68171071.702.py thon-list@python.org >,
> Bob Gailer <bgailer@alum.r pi.edu> wrote:
>
> <...>[color=green]
> > seq = [1,3,4,7] we'd like a differences == [2,1,3].
> >[/color]
> <...>
>
> seq=[1,3,4,7]
> [y-x for x,y in zip(seq,seq[1:])]
>
> --
> David Eppstein http://www.ics.uci.edu/~eppstein/
> Univ. of California, Irvine, School of Information & Computer Science[/color]