On 30 December 2012 04:59, David Kreuter <dkreuter@gmail.com> wrote:

When I write code for processing graphs it becomes very useful. For example:

def collapse_edge_undirected_graph(a, b): n = Node() n.connected = a.connected + b.connected for x in a.connected: x.connected.replace(a, n) for x in b.connected: x.connected.replace(b, n)

Assuming n.connected is the set of nodes connected to n, why use a list rather than a set? And if you need multi-edges, a dict mapping node to count of edges (i.e. a multiset). Paul.

On Sun, Dec 30, 2012 at 4:10 PM, Ned Batchelder <ned@nedbatchelder.com>wrote:

I wonder at the underlying philosophy of things being accepted or rejected in this way.

I'm no expert on the subject but here are a few criteria for builtin method inclusion: * Useful - show many popular use cases, e.g. attach many links to various lines on github/stackoverflow/bitbucket. * Hard to get right, i.e. user implementations tend to have bugs. * Would benefit greatly from C optimization * Have a great, obvious, specific, readable name * Don't overlap with anything else in the stdlib - TSBOAPOOOWTDI * Consistent with the rest of python, e.g. * Community approval * BDFL approval Brett wrote a bit on stdlib inclusion which may be relevant http://mail.python.org/pipermail/python-3000/2006-June/002442.html "that way may not be obvious at first unless you're Dutch." Yuval

On Mon, Dec 31, 2012 at 12:10 AM, Ned Batchelder <ned@nedbatchelder.com> wrote:

The two sides (count/index and replace/indexes) seem about the same to me:

- They are unambiguous operations. That is, no one has objected that reasonable people might disagree about how .replace() should behave, which is a common reason not to add things to the stdlib. - They implement simple operations that are easy to explain and will find use. In my experience, .indexes() is at least as useful as .count(). - All are based on element equality semantics. - Any of them could be implemented in a few lines of Python.

What is the organizing principle for the methods list (or any other built-in data structure) should have? I would hate for the main criterion to be, "these are the methods that existed in Python 2.3," for example. Why is .count() in and .replace() out?

The general problem with adding new methods to types rather than adding new functions+protocols is that it breaks ducktyping. We can mitigate that now by adding the new methods to collections.abc.Sequence, but it remains the case that relying on these methods being present rather than using the functional equivalent will needlessly couple your code to the underlying sequence implementation (since not all sequences inherit from the ABC, some are just registered). We also have a problem with replace() specifically that it *does* already exist in the standard library, as a non-mutating operation on str, bytes and bytearray. Adding it as a mutating method on sequences in general would create an immediate name conflict in the bytearray method namespace. That alone is a dealbreaker for that part of the idea. The question of an "indices" builtin or itertools function is potentially more interesting, but really, I don't think the algorithm David noted in his original post rises to the level of needing standardisation or acceleration: def indices(seq, val): for i, x in enumerate(seq): if x == val: yield i def map_assign(store, keys, val): for k in keys: store[k] = val def replace(seq, old, new): map_assign(seq, indices(seq, old), new) seq = [x, a, y, a] replace(seq, a, b) assert seq == [x, b, y, b] Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia

On 2012-12-30 16:00, Ned Batchelder wrote:

On 12/30/2012 10:05 AM, Nick Coghlan wrote:

...

On Mon, Dec 31, 2012 at 12:10 AM, Ned Batchelder <ned@nedbatchelder.com> wrote:

...

The two sides (count/index and replace/indexes) seem about the same to me:

- They are unambiguous operations. That is, no one has objected that reasonable people might disagree about how .replace() should behave, which is a common reason not to add things to the stdlib. - They implement simple operations that are easy to explain and will find use. In my experience, .indexes() is at least as useful as .count(). - All are based on element equality semantics. - Any of them could be implemented in a few lines of Python.

What is the organizing principle for the methods list (or any other built-in data structure) should have? I would hate for the main criterion to be, "these are the methods that existed in Python 2.3," for example. Why is .count() in and .replace() out? The general problem with adding new methods to types rather than adding new functions+protocols is that it breaks ducktyping. We can mitigate that now by adding the new methods to

collections.abc.Sequence, but it remains the case that relying on these methods being present rather than using the functional equivalent will needlessly couple your code to the underlying sequence implementation (since not all sequences inherit from the ABC, some are just registered).

We also have a problem with replace() specifically that it *does* already exist in the standard library, as a non-mutating operation on str, bytes and bytearray. Adding it as a mutating method on sequences in general would create an immediate name conflict in the bytearray method namespace. That alone is a dealbreaker for that part of the idea.

I don't understand the conflict? .replace() from sequence does precisely the same thing as .replace() from bytes if you limit the arguments to single-byte values. It seems perfectly natural to me. I must be missing something.

[snip] The difference is that for bytes and str it returns the result (they are immutable after all), but the suggested addition would mutate the list in-place. In order to be consistent it would have to return the result instead.

I would be very conservative here, since they are both builtin types, both sequences, and the reader may use the methods used as a hint about the type (a form of type inference if you will). The use case for list.replace() seems weak and we should beware of making standard interfaces too "thick" lest implementing alternative versions become too burdensome. --Guido On Sunday, December 30, 2012, Steven D'Aprano wrote:

On 31/12/12 03:58, MRAB wrote:

...

On 2012-12-30 16:00, Ned Batchelder wrote:

I don't understand the conflict? .replace() from sequence does

...

...

precisely the same thing as .replace() from bytes if you limit the arguments to single-byte values. It seems perfectly natural to me. I must be missing something.

[snip] The difference is that for bytes and str it returns the result (they are immutable after all), but the suggested addition would mutate the list in-place. In order to be consistent it would have to return the result instead.

Are you seriously suggesting that because str has a replace method with a specific API, no other type can have a replace method unless it has the same API?

Why must list.replace and str.replace do exactly the same thing? Lists and strings are not the same, and you cannot in general expect to substitute lists with strings, or vice versa.

collections.abc.**MutableSequence would seem to me to be the right place for a mutator replace method.

-- Steven ______________________________**_________________ Python-ideas mailing list Python-ideas@python.org http://mail.python.org/**mailman/listinfo/python-ideas<http://mail.python.org/mailman/listinfo/python-ideas>

-- --Guido van Rossum (on iPad)

On 12/30/2012 10:47 PM, Nick Coghlan wrote:

The problem is bytearray, not bytes and str.

bytearray is a builtin mutable sequence with a non-destructive replace() method. It doesn't matter that this is almost certainly just a mistake due to its immutable bytes heritage, the presence of that method is enough to categorically rule out the idea of adding a destructive replace() method to mutable sequences in general.

All this discussion is, of course, before getting into the fact that string, bytes, and bytearray .replace() methods all work on subsequences rather than elements.

On Mon, 31 Dec 2012 07:17:32 +0100 David Kreuter <dkreuter@gmail.com> wrote:

I don't think that consistency between str and list is desirable. If .index for example were consistent in str and list it would look like this:

[9, 8, 7, 6, 5].index([8,7]) # = 1

Also, reversed, sorted (copy) list.reverse, list.sort (in-place) From that perspective list.replace working in-place *is* consistent.

However, I can see that this '.replace' might cause more confusion than future code clarity.

Another name could be found if necessary.

What about .indices though?

I've never needed it myself. The fact that it's O(n) seems to hint that a list is not the right data structure for the use cases you may be thinking about :) Regards Antoine.

On 12/30/2012 9:10 AM, Ned Batchelder wrote:

On 12/30/2012 5:46 AM, Terry Reedy wrote:

...

On 12/29/2012 10:25 PM, David Kreuter wrote:

...

I think it would be nice to have a method in 'list' to replace certain elements by others in-place. Like this:

l = [x, a, y, a] l.replace(a, b) assert l == [x, b, y, b]

The alternatives are longer than they should be, imo. For example:

for i, n in enumerate(l):

Note that enumerate is a generic function of iterables, not a specific list method.

...

...

if n == a: l[i] = b

I dont see anything wrong with this. It is how I would do it in python. Wrap it in a function if you want. Or write it on two line ;-).

My deeper objection is that 'replace_all_in_place' is a generic mutable collection function, not a specific list or even mutable sequence function. Python 1 was stronger list oriented. Python 3 is mostly iterable oriented, with remnants of the Python 1 heritage.

I wonder at the underlying philosophy of things being accepted or rejected in this way. For example, here's a thought experiment: if list.count() and list.index() didn't exist yet, would we accept them as additions to the list methods?

I personally would have deleted list.find in 3.0. Count and index are not list methods but rather sequence methods, part of the sequence ABC. Tuples got them, as their only two public methods, in 3.0 to conform. This ties in to Nick's comment. (Actually counting a particular item in a collection is not specific to sequencess, but having multiple items to count tends to be.) It would be possible for count and index to be functions instead. But their definition as methods goes back to Python 1. Also note that .index has a start parameter, making it useful to get all indexes. See the code below.

By Terry's reasoning, there's no need to, since I can implement those operations in a few lines of Python.

We constantly get proposals to add new functions and methods that are easily written in a few lines. Everyone thinks their proposal is useful because it is useful in their work. If we accepted all such proposals, Python would have hundreds more.

Does that mean they persist only for backwards compatibility?

Backwards compatibility is important. Changing them to functions would be disruptive without sufficient gain.

Was their initial inclusion a violation of some "list method philosophy"?

No, it was part of the Python 1 philosophy of lists as the common data interchange type. As I said, this has changed in Python 3.

Or is there a good reason for them to exist, and if so, why shouldn't .replace() and .indexes() also exist?

Neither are list methods. Nicks gave a generic indexes generator. A specific list indexes generator can use repeated applications of .index with start argument. I do that 'inline' below.

I would hate for the main criterion to be, "these are the methods that existed in Python 2.3,"

Then you are hating reality ;-). The .method()s of basic builtin classes is close to frozen.

...

There is a perfectly good python version above that does the necessary search and replace as efficiently as possible. Thank you for posting it.

You say "as efficiently as possible," but you mean, "as algorithmically efficient as possible," which is true, they are linear, which is as good as it's going to get. But surely if coded in C, these operations would be faster.

You are right. Lets do the next-item search in C with .index. If the density of items to be replaces is low, as it would be for most applications, this should dominate. def enum(lis): for i, n in enumerate(lis): if n == 1: lis[i] = 2 a, b = 100, 10000 # started with 2,1 for initial tests start = a*([1]+b*[0]) after = a*([2]+b*[0]) # test that correct before test speed! # since the list is mutated, it must be reset for each test lis = start.copy() enum(lis) print('enum: ', lis == after) def repin(lis): i = -1 try: while True: i = lis.index(1, i+1) lis[i] = 2 except: pass lis = start.copy() repin(lis) print('repin: ', lis == after) from timeit import timeit # now for speed, remembering to reset for each test # first measure the copy time to subtract from test times print(timeit('lis = start.copy()', 'from __main__ import start', number=10)) print(timeit('lis = start.copy(); enum(lis)', 'from __main__ import start, enum', number=10)) print(timeit('lis = start.copy(); repin(lis)', 'from __main__ import start, repin', number=10)) # measure scan without replace to give an upper limit to python-coded replace # since lis is not mutated, it only needs to be defined once print(timeit('repin(lis)', 'from __main__ import a, b, repin; lis = a*(b+1)*[0]', number=10)) # prints enum: True repin: True 0.06801244890066886 0.849063227602523 0.2759397696510706 0.20790119084727898 After subtracting and dividing, enum take .078 seconds for 100 replacements in 1000000 items, repin just .021, which is essentially the time it takes just to scan 1000000 items. So doing the replacements also in C would not be much faster. Rerunning with 10000 replacements (a,b = 10000, 100), the times are .080 and .024. -- Terry Jan Reedy

On 31/12/12 01:10, Ned Batchelder wrote:

What is the organizing principle for the methods list (or any other built-in data structure) should have? I would hate for the main criterion to be, "these are the methods that existed in Python 2.3," for example. Why is .count() in and .replace() out?

I fear that it is more likely to be "they existed in Python 1.5". As far as I can tell, there have been very few new methods added to standard types since Python 1.5, and possibly before that. Putting aside dunder methods, the only public list methods in 3.3 that weren't in 1.5 are clear and copy. Tuples also have two new methods, count and index. Dicts have seen a few more changes: - has_key is gone; - fromkeys, pop, popitem, and setdefault are added. So changes to builtin types have been very conservative. -- Steven