Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #105866 > unrolled thread

Re: Suggestion: make sequence and map interfaces more similar

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Suggestion: make sequence and map interfaces more similar "Marco S." <mail.python.org@marco.sulla.e4ward.com> - 2016-03-27 20:01 +0200
    Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-28 12:05 +1100
      Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-29 16:08 +0200
      Re: Suggestion: make sequence and map interfaces more similar Chris Angelico <rosuav@gmail.com> - 2016-03-30 01:31 +1100
      Re: Suggestion: make sequence and map interfaces more similar Marco Sulla <mail.python.org@marco.sulla.e4ward.com> - 2016-03-30 00:29 +0200
      Re: Suggestion: make sequence and map interfaces more similar Terry Reedy <tjreedy@udel.edu> - 2016-03-29 20:55 -0400
      Re: Suggestion: make sequence and map interfaces more similar Chris Angelico <rosuav@gmail.com> - 2016-03-30 11:56 +1100
      Re: Suggestion: make sequence and map interfaces more similar Random832 <random832@fastmail.com> - 2016-03-29 23:38 -0400
        Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-03-30 16:43 +1100
          Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-03-30 16:57 +1100
          Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 10:12 +0300
            Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-30 21:17 +1100
              Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 13:28 +0300
                Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-30 12:34 +0200
                  Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 13:57 +0300
                Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-30 23:22 +1100
                  Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-30 15:12 +0200
                    Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-31 02:56 +1100
                      Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-30 21:07 +0200
                        Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-31 13:40 +1100
                          Re: Suggestion: make sequence and map interfaces more similar Paul Rubin <no.email@nospam.invalid> - 2016-03-30 19:45 -0700
                            Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-03-31 17:45 +1100
                          Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-31 09:52 +0200
                            Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-31 21:36 +1100
                              Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-31 12:51 +0200
                              Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-31 13:22 +0200
                              Re: Suggestion: make sequence and map interfaces more similar Chris Angelico <rosuav@gmail.com> - 2016-03-31 22:57 +1100
                                Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-31 15:36 +0300
                                  Re: Suggestion: make sequence and map interfaces more similar Chris Angelico <rosuav@gmail.com> - 2016-03-31 23:48 +1100
                                    Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-31 17:02 +0300
                                      Re: Suggestion: make sequence and map interfaces more similar Michael Selik <michael.selik@gmail.com> - 2016-04-01 04:19 -0400
                                  Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-31 15:55 +0300
                                    Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-31 17:19 +0300
                              Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-31 15:08 +0200
                                Re: Suggestion: make sequence and map interfaces more similar Rustom Mody <rustompmody@gmail.com> - 2016-03-31 06:42 -0700
                              Re: Suggestion: make sequence and map interfaces more similar Chris Angelico <rosuav@gmail.com> - 2016-04-01 00:11 +1100
                              Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-31 14:17 +0100
                              Re: Suggestion: make sequence and map interfaces more similar Random832 <random832@fastmail.com> - 2016-03-31 09:27 -0400
                                Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-31 17:13 +0300
                                  Re: Suggestion: make sequence and map interfaces more similar Terry Reedy <tjreedy@udel.edu> - 2016-03-31 13:41 -0400
                              Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-31 15:12 +0100
                              Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-04-01 09:59 +0200
                              Re: Suggestion: make sequence and map interfaces more similar Tim Golden <mail@timgolden.me.uk> - 2016-04-01 09:27 +0100
                                Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-04-01 21:38 +1100
                                  Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-04-01 13:50 +0300
                                Re: Suggestion: make sequence and map interfaces more similar Rustom Mody <rustompmody@gmail.com> - 2016-04-01 07:41 -0700
                              Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-04-01 10:04 +0100
                      Re: Suggestion: make sequence and map interfaces more similar Marco Sulla <mail.python.org@marco.sulla.e4ward.com> - 2016-03-30 21:35 +0200
                      Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-30 21:31 +0100
              Re: Suggestion: make sequence and map interfaces more similar Manolo Martínez <manolo@austrohungaro.com> - 2016-03-30 12:26 +0200
                Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 13:40 +0300
                  Re: Suggestion: make sequence and map interfaces more similar Manolo Martínez <manolo@austrohungaro.com> - 2016-03-30 12:50 +0200
                    Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 14:21 +0300
                      Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-30 14:44 +0300
                        Re: Suggestion: make sequence and map interfaces more similar Manolo Martínez <manolo@austrohungaro.com> - 2016-03-30 14:29 +0200
                          Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-30 15:55 +0300
                            Re: Suggestion: make sequence and map interfaces more similar Manolo Martínez <manolo@austrohungaro.com> - 2016-03-30 15:13 +0200
                      Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-30 23:27 +1100
                        Re: Suggestion: make sequence and map interfaces more similar Marko Rauhamaa <marko@pacujo.net> - 2016-03-30 15:48 +0300
                          Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 17:38 +0300
                        Re: Suggestion: make sequence and map interfaces more similar Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-03-30 17:25 +0300
          Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-30 10:55 +0200
          Re: Suggestion: make sequence and map interfaces more similar Random832 <random832@fastmail.com> - 2016-03-30 08:50 -0400
            Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-31 03:02 +1100
              Re: Suggestion: make sequence and map interfaces more similar Random832 <random832@fastmail.com> - 2016-03-30 12:52 -0400
                Re: Suggestion: make sequence and map interfaces more similar Steven D'Aprano <steve@pearwood.info> - 2016-03-31 13:44 +1100
                  Re: Suggestion: make sequence and map interfaces more similar Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-03-31 10:04 +0200
                  Re: Suggestion: make sequence and map interfaces more similar Marco Sulla <mail.python.org@marco.sulla.e4ward.com> - 2016-03-31 13:58 +0200
                  Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-31 13:30 +0100
                  Re: Suggestion: make sequence and map interfaces more similar Marco Sulla <mail.python.org@marco.sulla.e4ward.com> - 2016-03-31 14:49 +0200
                  Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-31 14:14 +0100
              Re: Suggestion: make sequence and map interfaces more similar Marco Sulla <mail.python.org@marco.sulla.e4ward.com> - 2016-03-30 22:00 +0200
              Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-30 21:36 +0100
      Re: Suggestion: make sequence and map interfaces more similar Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-03-30 08:03 +0100

Page 1 of 4  [1] 2 3 4  Next page →

#105866 — Re: Suggestion: make sequence and map interfaces more similar

Steven D'Aprano wrote:

> The point you might have missed is that treating lists as if they were
> mappings violates at least one critical property of mappings: that the
> relationship between keys and values are stable.


This is true for immutable maps, but for mutable ones, you can simply do

map[key] = new_value

You can easily create a new class that extend dict and add to it a
method that emulated the insert method of lists. It will definitively
not break any contract, if your contract is "sequences are maps with
ordered integer keys that starts from zero and have no gaps".

Mark Lawrence wrote:

> I cannot see this happening unless you provide a patch on the bug
> tracker.  However I suspect you can get the same thing by subclassing
> dict.  Why don't you try it and let us know how you get on?

The problem with a vdict is that I should also create by zero a new
interface (ABC), since MutableMapping have an incompatible contract.
And to be much more useful I should code it inc C, and my C skills are
not so magnificent. Furthermore I would try to create a new sequence
interface that inherit from the vdict interface. More briefly, I need
much free time. But I suppose I can start with something quick and
dirty.

[toc] | [next] | [standalone]

#105885

On Mon, 28 Mar 2016 05:01 am, Marco S. wrote:

> Steven D'Aprano wrote:
> 
>> The point you might have missed is that treating lists as if they were
>> mappings violates at least one critical property of mappings: that the
>> relationship between keys and values are stable.
> 
> 
> This is true for immutable maps, but for mutable ones, you can simply do

No, it is true for mutable maps too.

When you add a new key:value to a dict, the other key:value pairs don't
change. That is the whole point of a mapping! Of course you can
deliberately change the value by re-assignment:

    map[key] = new_value

but that's not what I'm talking about. When you add a NEW key, the OTHER
keys DON'T change. That is ABSOLUTELY CRITICAL to a mapping. Anything which
lacks that property is not a mapping.

The relationship between the index of a value and the value in a sequence is
not stable. Inserting a new value can change the "key"(actually index) of
some or all of the existing values. The whole point of sequences is that
the position of values is NOT stable: they are intended to move around. You
can sort them, reverse them, delete them, insert new values, and the others
will move around to make room. If you think of the index as a key, this is
completely the opposite behaviour of mappings.

In a mapping, the key:value is stable, and must not change unless you
explicitly change it.

In a sequence, the index:value relationship is unstable, and can easily
change without notice, due to many different operations:

insertion
deletion
popping a value
sorting
shuffling
reversal of the sequence

and probably more.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#105987

Op 28-03-16 om 03:05 schreef Steven D'Aprano:
> On Mon, 28 Mar 2016 05:01 am, Marco S. wrote:
>
>> Steven D'Aprano wrote:
>>
>>> The point you might have missed is that treating lists as if they were
>>> mappings violates at least one critical property of mappings: that the
>>> relationship between keys and values are stable.
>>
>> This is true for immutable maps, but for mutable ones, you can simply do
> No, it is true for mutable maps too.
>
> When you add a new key:value to a dict, the other key:value pairs don't
> change. That is the whole point of a mapping! Of course you can
> deliberately change the value by re-assignment:
>
>     map[key] = new_value
>
> but that's not what I'm talking about. When you add a NEW key, the OTHER
> keys DON'T change. That is ABSOLUTELY CRITICAL to a mapping. Anything which
> lacks that property is not a mapping.

I'm not sure I agree with that.

> The relationship between the index of a value and the value in a sequence is
> not stable. Inserting a new value can change the "key"(actually index) of
> some or all of the existing values.

Which is not simply adding a key. Inserting a new value is IMO more like
doing an update.

>  The whole point of sequences is that
> the position of values is NOT stable: they are intended to move around.

I find that language too strong. The lists I use are generally stable.
Does that mean I'm using lists in a way not intended.

>  You
> can sort them, reverse them, delete them, insert new values, and the others
> will move around to make room. If you think of the index as a key, this is
> completely the opposite behaviour of mappings.

Not really. IMO a mapping is just a surjective function and sometimes a
list is a perfectly fine way to implement such a function.

The point I think the OP tries to make is that sometimes you need to write
a function that takes a surjective function as argument and produces some
result, but you just don't care whether this function is implemented as
a map or as a sequence.

Suppose you want to know how many times each value occurs and want to
map that. As it is you have to write something like the following.

def count(l):
    counted = defaultdict(int)
    try:
        itr = l.values()
    except AttributeError:
        itr = iter(l)
    for v in itr:
        counted[v] += 1
    return counted

What would be the big problem if a values method would be available
on a list which returned the iterator and if an items method would
be like calling enumerate?

[toc] | [prev] | [next] | [standalone]

#105988

On Wed, Mar 30, 2016 at 1:08 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> Op 28-03-16 om 03:05 schreef Steven D'Aprano:
>> When you add a new key:value to a dict, the other key:value pairs don't
>> change. That is the whole point of a mapping! Of course you can
>> deliberately change the value by re-assignment:
>>
>>     map[key] = new_value
>>
>> but that's not what I'm talking about. When you add a NEW key, the OTHER
>> keys DON'T change. That is ABSOLUTELY CRITICAL to a mapping. Anything which
>> lacks that property is not a mapping.
>
> I'm not sure I agree with that.

I am. The similarity between "mapping with integers as keys" and
"sequence" is that both of them can be subscripted. And that's fine;
Python lets you define __getitem__ in any way you like. OrderedDict is
somewhere between "sequence with associated keys" and "mapping with
inherent order", and there's no problem with that.

But the definition of a sequence, and likewise the definition of a
mapping, goes deeper than that. A sequence has *relative* stability;
if one item is at a lower index than another, it will continue to be
at a lower index, until you change one of those two items. Changes
elsewhere in the sequence might bring them closer together or push
them further apart, but one of them is still earlier in the sequence
than the other. A mapping, on the other hand, has *absolute*
stability. Any given key->value relationship is stable in and of
itself. If you stuff a thing into a dict under a particular key, you
expect to be able to get it back using that key, not some other.

Sure, you can use a tuple to represent an immutable mapping between
dense integers and values. And there are times when that's perfectly
acceptable - here's two ways of depicting the month lengths in a
non-leap year in the Gregorian calendar:

mapping = {1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9:
30, 10: 31, 11: 30, 12: 31}
sequence = (None, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

Both of them let you look up 6 and get back that June has 30 days. The
sequence is forced to start from zero, but that's a small matter (and
if you number your months 0-11 instead of 1-12, no difference at all).
But the only operation these two data types truly share is
subscripting. If you want to be able to iterate over these in calendar
order, you don't switch out the dict for an OrderedDict - you use the
tuple. If you want to be able to use month names instead of numbers,
you don't mess around with the tuple - you use the dict.

The whole idea of making sequences and mappings more similar is highly
distasteful to me, and I've figured out why. It's the exact problem
with the PHP array - it's not sure whether to act as a mapping or a
sequence, and standard library functions can behave oddly in the
presence of all-numeric keys that aren't intended to be a sequence.
The two types are fundamentally different, and you almost never want
to treat them identically - at best, you want to have one specific
function that handles either type, and that's most cleanly handled
inside that function, not by adding mapping-like features to sequences
or vice versa.

ChrisA

[toc] | [prev] | [next] | [standalone]

#106012

On 29 March 2016 at 16:31, Chris Angelico <rosuav@gmail.com> wrote:
> But the definition of a sequence, and likewise the definition of a
> mapping, goes deeper than that. A sequence has *relative* stability;
> if one item is at a lower index than another, it will continue to be
> at a lower index, until you change one of those two items. Changes
> elsewhere in the sequence might bring them closer together or push
> them further apart, but one of them is still earlier in the sequence
> than the other. A mapping, on the other hand, has *absolute*
> stability. Any given key->value relationship is stable in and of
> itself. If you stuff a thing into a dict under a particular key, you
> expect to be able to get it back using that key, not some other.

It's the same arguments of Steven D'Aprano. Let me counter these
arguments with this example:

>>> class StrangeDict(dict):
...     def insert(self, k, v):
...         if k in self:
...             for key in [x for x in sorted(self.keys()) if x >= k]:
...                 v_next = self[key]
...                 self[key] = v
...                 v = v_next
...
...             self[key+1] = v
...
>>> a = StrangeDict({0:5, 1:7, 2: 14})
>>> a.insert(1, 5)
>>> a
{0: 5, 1: 5, 2: 7, 3: 14}

Yes, it's a terrible class and lacks a lot of safety checks, but I
don't think at all it violates the map contract. You can continue and
add some constraint at __init__() about key types and their
contiguity, some other methods and voila', you'll get a list-like
class.

Let me add that an items() and keys() for sequences will be also
useful for day-by-day programming, since they will be a shortcut for
enumerate(seq) and range(len(seq))

> The whole idea of making sequences and mappings more similar is highly
> distasteful to me, and I've figured out why. It's the exact problem
> with the PHP array - it's not sure whether to act as a mapping or a
> sequence

This is a good point. This is not true for mutable sequences (lists),
since they will have a lot of methods (append, pop etc) that allows
you to distinguish them, but immutable sequences like tuples will be
not easily distinguishable using duck typing.

I think the main problem is in __getitem__. __getitem__ can be used as
slice method checking if its parameter is a slice. If the slice method
was a separated method, this problem will not arise.


On 27 March 2016 at 21:24, Mark Lawrence <breamoreboy@yahoo.co.uk> wrote:
> Why do you need a new interace if all you're trying to do is create a
> vdict class that has "iter(d) == iter(d.values()), and should also
> have a count() method, like sequence types"?

Since simply adding get(), items(), keys(), values() to existing
sequence interface will likely break existing code, I would try also
to write new sequence types, using a common interface with maps. This
is my idea.

[toc] | [prev] | [next] | [standalone]

#106022

On 3/29/2016 6:29 PM, Marco Sulla via Python-list wrote:

> Let me add that an items() and keys() for sequences will be also
> useful for day-by-day programming, since they will be a shortcut for
> enumerate(seq) and range(len(seq))

To me they are useless and confusing duplications since enumerate()(seq) 
and range(len(seq)) are quite different from dict.items and dict.keys. 
They cannot be used interchangably.

Dict.keys/values/items are re-iterable, set-like *dynamic views* of 
dicts.  They are not iterators.  They support binary set operations and 
inter-operate with sets.

 >>> {1:1, 2:2}.keys() ^ {1, 3}
{2, 3}
 >>> {1, 3} ^ {1:1, 2:2}.keys()
{2, 3}

They not independent objects but are views of the contests of the dict. 
They are relatively easy to implement because dicts are key-hashed sets 
of pairs. At least in CPython, changing a dict disables view iterators.

 >>> d={1:1, 2:2}
 >>> di = iter(d)
 >>> next(di)
1
 >>> d[3] = 3
 >>> next(di)
Traceback (most recent call last):
   File "<pyshell#8>", line 1, in <module>
     next(di)
RuntimeError: dictionary changed size during iteration

Enumerates are iterators.  Ranges are independent collections.  Neither 
support binary set operations.  Enumerates and range iterators are not 
disabled by sequence changes.

> Since simply adding get(), items(), keys(), values() to existing
> sequence interface will likely break existing code, I would try also
> to write new sequence types, using a common interface with maps.

seq.get is plausible, but the use cases are not clear.  It is trivial to 
write, so it needs justification.  A major use of dict.get is to supply 
an empty list for values that can be appended to.
    d.get(key, []).append(val)
A similar use with lists could just as well be done with a dict.

For the rest, try writing sequence view classes that actually mimic dict 
views and interoperate with sets and views.  Find the dict view tests 
and adapt them to seq views.  To use the same code with dicts and seqs, 
add functions that return a dict view or seq view depending on the class 
of the collections.

     def keys(ds):
         reture ds.keys() if isinstance(ds, dict) else SeqKeys(ds)

You might search for 'python sequence view' first, and if there is 
nothing already on PyPI, add a seqview module there.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#106023

On Wed, Mar 30, 2016 at 9:29 AM, Marco Sulla via Python-list
<python-list@python.org> wrote:
> On 29 March 2016 at 16:31, Chris Angelico <rosuav@gmail.com> wrote:
>> But the definition of a sequence, and likewise the definition of a
>> mapping, goes deeper than that. A sequence has *relative* stability;
>> if one item is at a lower index than another, it will continue to be
>> at a lower index, until you change one of those two items. Changes
>> elsewhere in the sequence might bring them closer together or push
>> them further apart, but one of them is still earlier in the sequence
>> than the other. A mapping, on the other hand, has *absolute*
>> stability. Any given key->value relationship is stable in and of
>> itself. If you stuff a thing into a dict under a particular key, you
>> expect to be able to get it back using that key, not some other.
>
> It's the same arguments of Steven D'Aprano. Let me counter these
> arguments with this example:
>
>>>> class StrangeDict(dict):
> ...     def insert(self, k, v):
> ...         if k in self:
> ...             for key in [x for x in sorted(self.keys()) if x >= k]:
> ...                 v_next = self[key]
> ...                 self[key] = v
> ...                 v = v_next
> ...
> ...             self[key+1] = v
> ...
>>>> a = StrangeDict({0:5, 1:7, 2: 14})
>>>> a.insert(1, 5)
>>>> a
> {0: 5, 1: 5, 2: 7, 3: 14}
>
> Yes, it's a terrible class and lacks a lot of safety checks, but I
> don't think at all it violates the map contract. You can continue and
> add some constraint at __init__() about key types and their
> contiguity, some other methods and voila', you'll get a list-like
> class.

The map contract is this:

x = StrangeDict()
x[123] = 456
...
assert x[123] == 456

Your mapping does violate the map contract.

ChrisA

[toc] | [prev] | [next] | [standalone]

#106026

On Tue, Mar 29, 2016, at 20:56, Chris Angelico wrote:
> The map contract is this:
> 
> x = StrangeDict()
> x[123] = 456
> ...
> assert x[123] == 456
> 
> Your mapping does violate the map contract.

So, you can put *anything* in that "..."?

x = dict()
x[123] = 456
x[123] = 789
assert x[123] == 456

dict violates the map contract.

[toc] | [prev] | [next] | [standalone]

#106028

On Wednesday 30 March 2016 14:38, Random832 wrote:

> On Tue, Mar 29, 2016, at 20:56, Chris Angelico wrote:
>> The map contract is this:
>> 
>> x = StrangeDict()
>> x[123] = 456
>> ...
>> assert x[123] == 456
>> 
>> Your mapping does violate the map contract.
> 
> So, you can put *anything* in that "..."?

Yes, we're all very impressed that you spotted the trivial and obvious 
loophole that changing a key:value will change the key:value that you just 
changed *wink* but that doesn't really move the discussion anywhere.

This is not an argument about dicts being mutable, because clearly they 
aren't. This is an argument about key:value pairs being stable. "Stable" 
doesn't mean "immutable". If you change the value associated with a key 
directly, then it will change. That's the whole point. But if you change 
*one* key, the relationship between *other* keys and their values shouldn't 
change.

Given a surjection (many-to-one mapping) between keys and values in a 
mapping, we expect that changing the mapping of one key will not affect 
other keys. To be pedantic, by "change" I mean deleting the key (and, if 
necessary, value) or reassigning a new value to the key. To be even more 
pedantic, mutations to the value *do not count*.

Specifically, insertions and deletions to the mapping never affect the 
existing keys. But, critically, insertions and deletions to a sequence do 
sometimes affect the index of existing items.

So while we can say that there is a surjective function that maps the index 
of a sequence to an item, but that relationship fails to meet the 
requirements for it to be a mapping type like a dict.

https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection


If somebody wants to insist that this is a kind of mapping, I can't 
disagree, but it isn't useful as a mapping type.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#106029

On Wednesday 30 March 2016 16:43, Steven D'Aprano wrote:

> This is not an argument about dicts being mutable, because clearly they
> aren't.

Er, I meant *immutable*. Dicts aren't immutable.


-- 
Steve

[toc] | [prev] | [next] | [standalone]

#106031

Steven D'Aprano writes:

> Given a surjection (many-to-one mapping)

No. And I doubt that Wikipedia says that.

[toc] | [prev] | [next] | [standalone]

#106040

On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:

> Steven D'Aprano writes:
> 
>> Given a surjection (many-to-one mapping)
> 
> No. And I doubt that Wikipedia says that.


No to what? What are you disagreeing with?


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#106044

Steven D'Aprano writes:

> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:
>
>> Steven D'Aprano writes:
>> 
>>> Given a surjection (many-to-one mapping)
>> 
>> No. And I doubt that Wikipedia says that.
>
> No to what? What are you disagreeing with?

Surjection does not mean many-to-one mapping. It means something else.

[toc] | [prev] | [next] | [standalone]

#106046

Op 30-03-16 om 12:28 schreef Jussi Piitulainen:
> Steven D'Aprano writes:
>
>> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:
>>
>>> Steven D'Aprano writes:
>>>
>>>> Given a surjection (many-to-one mapping)
>>> No. And I doubt that Wikipedia says that.
>> No to what? What are you disagreeing with?
> Surjection does not mean many-to-one mapping. It means something else.

I think this is my fault. I used "surjective function" wrongly in
my first response.

-- 
Antoon.

[toc] | [prev] | [next] | [standalone]

#106049

Antoon Pardon writes:

> Op 30-03-16 om 12:28 schreef Jussi Piitulainen:
>> Steven D'Aprano writes:
>>
>>> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:
>>>
>>>> Steven D'Aprano writes:
>>>>
>>>>> Given a surjection (many-to-one mapping)
>>>> No. And I doubt that Wikipedia says that.
>>> No to what? What are you disagreeing with?
>> Surjection does not mean many-to-one mapping. It means something else.
>
> I think this is my fault. I used "surjective function" wrongly in
> my first response.

Thanks. I missed that. Now I at least see why Steven may have brought
the concept up at all - it doesn't seem relevant, either.

[toc] | [prev] | [next] | [standalone]

#106056

On Wed, 30 Mar 2016 09:28 pm, Jussi Piitulainen wrote:

> Steven D'Aprano writes:
> 
>> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:
>>
>>> Steven D'Aprano writes:
>>> 
>>>> Given a surjection (many-to-one mapping)
>>> 
>>> No. And I doubt that Wikipedia says that.
>>
>> No to what? What are you disagreeing with?
> 
> Surjection does not mean many-to-one mapping. It means something else.


Oh, if only I had linked to the Wikipedia page earlier... oh wait, I did.
Here it is again:

https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection


The relevant definition is:


    The function is surjective (onto) if every element of the codomain is
mapped to by at least one element of the domain. (That is, the image and
the codomain of the function are equal.) A surjective function is a
surjection. Notationally:

    \forall y \in B, \exists x \in A \text{ such that } y = f(x).\ 



and the relevant diagram is the image labelled "Non-injective and
surjective", also seen here:

https://en.wikipedia.org/wiki/File:Surjection.svg


Why is a mapping (such as a dict) best described as a surjection? Consider:

d = {1: None, 2: 'a', 3: 'b', 4: None}


Every key has exactly one value. There are no values without a key, and
every value has *at least* one key.

To be an injection or a bijection, it must be one-to-one. Since multiple
keys can map to the same value, it's not an injection or a bijection.

Every value must have a key: there are no values in the dict without a key.
Hence, it's a surjection.

Although Wikipedia don't use the description, "many-to-one" is a good way of
describing surjections, since you can have many keys mapped to a single
value. To be precise, some surjections may be one-to-one, and not all
many-to-one relations are surjections. But the distinguishing feature of a
surjection is that each value must have *at least* one key, which describes
dicts and other such mappings.

And for those who don't trust Wikipedia:

http://mathsforall.co.uk/userfiles/SECTION%203B%20Injective%20and%20Surjective%20functions%2027_11_06.pdf




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#106068

Op 30-03-16 om 14:22 schreef Steven D'Aprano:
> On Wed, 30 Mar 2016 09:28 pm, Jussi Piitulainen wrote:
>
>> Steven D'Aprano writes:
>>
>>> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote:
>>>
>>>> Steven D'Aprano writes:
>>>>
>>>>> Given a surjection (many-to-one mapping)
>>>> No. And I doubt that Wikipedia says that.
>>> No to what? What are you disagreeing with?
>> Surjection does not mean many-to-one mapping. It means something else.
>
> Oh, if only I had linked to the Wikipedia page earlier... oh wait, I did.
> Here it is again:
>
> https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection
>
>
> The relevant definition is:
>
>
>     The function is surjective (onto) if every element of the codomain is
> mapped to by at least one element of the domain. (That is, the image and
> the codomain of the function are equal.) A surjective function is a
> surjection. Notationally:
>
>     \forall y \in B, \exists x \in A \text{ such that } y = f(x).\ 
>
>
>
> and the relevant diagram is the image labelled "Non-injective and
> surjective", also seen here:
>
> https://en.wikipedia.org/wiki/File:Surjection.svg
>
>
> Why is a mapping (such as a dict) best described as a surjection? Consider:
>
> d = {1: None, 2: 'a', 3: 'b', 4: None}
>
>
> Every key has exactly one value. There are no values without a key, and
> every value has *at least* one key.

That second remark depends on what you consider the codomain. You could
of course define the codomain as the set of actual values in the mapping,
but that seems to be very artificial since it means that the codomain can
changes any time a value is changed, added or removed.

A more intuitive view would be that the codomain is the set of things
that potentially can be a value in your mapping (in this application).
So looking at your example 'c' seems to be such a potential value which
for the moment doesn't have a key. So your mapping is no surjection.
 

> To be an injection or a bijection, it must be one-to-one. Since multiple
> keys can map to the same value, it's not an injection or a bijection.
>
> Every value must have a key: there are no values in the dict without a key.
> Hence, it's a surjection.

Only if you use the special python meaning of (dictionary) values in this context.
If you use the ordinary (mathematical) meaning, there are lots of values that
don't have a key, like every two characters string.

-- 
Antoon.

[toc] | [prev] | [next] | [standalone]

#106088

On Thu, 31 Mar 2016 12:12 am, Antoon Pardon wrote:

> Op 30-03-16 om 14:22 schreef Steven D'Aprano:

[...]
>> Why is a mapping (such as a dict) best described as a surjection?
>> Consider:
>>
>> d = {1: None, 2: 'a', 3: 'b', 4: None}
>>
>>
>> Every key has exactly one value. There are no values without a key, and
>> every value has *at least* one key.
> 
> That second remark depends on what you consider the codomain. You could
> of course define the codomain as the set of actual values in the mapping,
> but that seems to be very artificial since it means that the codomain can
> changes any time a value is changed, added or removed.

But that's exactly what the mapping does.

Let's start with something that looks like a mathematical mapping, a
function f(x) from positive integers to positive integers:

f(x) = x**2

Here's our dict:

d = {1: 1, 2: 4, 3: 9, 4: 16}

You're saying that the codomain should be "all positive integers", and
likewise the domain. But this is wrong, because the mapping d isn't defined
for all positive integers:

d[5]  # raise KeyError

We can only say that the domain is the *actual keys in the dict*.

And likewise for the codomain. We can't say that the codomain is all
positive integers, since the mapping is not defined for any values of x
except the given keys.

Because dicts are mutable, we can do this:

d[2] = 7


but that's precisely what we *can't* do with mathematical functions! We
can't just declare that, from now on, x**2 will equal 7 if x is 2. So any
modification of the dict must give us a new and different function. Before,
we had the function:

# d equivalent to
f(x): {1,2,3,4} --> {1,4,9,16} where 
    f(1) = 1
    f(2) = 4
    f(3) = 9
    f(4) = 16


After executing the line d[2] = 7, we have the completely different
function:

f(x): {1,2,3,4} --> {1,7,9,16} where 
    f(1) = 1
    f(2) = 7
    f(3) = 9
    f(4) = 16


Now consider what happens when we execute:

del d[4]
d['a'] = None


That's the nature of dicts as mappings: they don't actually come very close
to the semantics of mathematical functions. Any talk of surjections,
domains, codomains etc is going to be, at best, an analogy.

So all of this discussion is stretching the mathematical terms to their
breaking point. Dicts aren't actually functions in the mathematical sense,
and in the general case, they don't have well-defined domains and
codomains.

Describing them as surjective (or any other such term) requires a lot of
hand-waving. I happen to think that the analogy works very well (otherwise
I wouldn't have given it), but others think I'm being sloppy, well, yes I
am, and I'll withdraw it.

Because fundamentally, it doesn't matter whether dicts are surjections or
not. They're still many-to-one mappings, and those mappings between keys
and values should not change due to the insertion or deletion of unrelated
keys.

If the OP wants to create his own "StrangeDict", which he himself described
as "terrible", then he can do so. But to make all dicts and lists behave in
this "terrible" and "strange" way is a terrible idea.



[...]
> Only if you use the special python meaning of (dictionary) values in this
> context. If you use the ordinary (mathematical) meaning, there are lots of
> values that don't have a key, like every two characters string.

Well, we're actually discussing Python dictionaries. So, damn straight, of
course I'm going to use the meaning of words as they apply to dicts.




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#106104

Op 30-03-16 om 17:56 schreef Steven D'Aprano:
> On Thu, 31 Mar 2016 12:12 am, Antoon Pardon wrote:
> 
>> Op 30-03-16 om 14:22 schreef Steven D'Aprano:
> 
> [...]
>>> Why is a mapping (such as a dict) best described as a surjection?
>>> Consider:
>>>
>>> d = {1: None, 2: 'a', 3: 'b', 4: None}
>>>
>>>
>>> Every key has exactly one value. There are no values without a key, and
>>> every value has *at least* one key.
>>
>> That second remark depends on what you consider the codomain. You could
>> of course define the codomain as the set of actual values in the mapping,
>> but that seems to be very artificial since it means that the codomain can
>> changes any time a value is changed, added or removed.
> 
> But that's exactly what the mapping does.

No it generally doesn't. I see no reason when at one moment I can write the following.

  assert map.values == {2, 5, 7, 9}
  map[3] = 8

to claim the codomain has changed. The actual function has changed yes but
since the application shows that the universe of possible mapping represented
by this specific variable containes functions in which 8 is an element of
the function image. This is best expressed by saying 8 is part of the codomain
whether or not 8 is part of the actual values at any specific moment.

Sure you sometimes work with a map in which the image is the domain, like
you did with your map of a limit square function but I consider those
as exceptions, not the general case.


> And likewise for the codomain. We can't say that the codomain is all
> positive integers, since the mapping is not defined for any values of x
> except the given keys.
> 
> Because dicts are mutable, we can do this:
> 
> d[2] = 7
> 
> 
> but that's precisely what we *can't* do with mathematical functions! We
> can't just declare that, from now on, x**2 will equal 7 if x is 2. So any
> modification of the dict must give us a new and different function. Before,
> we had the function:

So? The best way IMO to look at this is as a family of functions between
a domain and a codomain. Because that is the problem space you are looking
at. If within this problem space you have found a surjection, the normal
way to understand that is that you have found a function in which the
image is the total of the possible value set.

> # d equivalent to
> f(x): {1,2,3,4} --> {1,4,9,16} where 
>     f(1) = 1
>     f(2) = 4
>     f(3) = 9
>     f(4) = 16
> 
> 
> After executing the line d[2] = 7, we have the completely different
> function:

So? Since this change of a function is presumably a step in searching
a solution within some problem space, the domain and codomain of both
functions are the same. Even if the function is not total nor surjective
in this way.

> That's the nature of dicts as mappings: they don't actually come very close
> to the semantics of mathematical functions. Any talk of surjections,
> domains, codomains etc is going to be, at best, an analogy.

At any specific time a dictionary is a perfect representation of a
mathematical function.

> So all of this discussion is stretching the mathematical terms to their
> breaking point. Dicts aren't actually functions in the mathematical sense,
> and in the general case, they don't have well-defined domains and
> codomains.

But that part of the problem you represent by the dictionary often enough
has a well defined domain and codomain.

> Because fundamentally, it doesn't matter whether dicts are surjections or
> not. They're still many-to-one mappings, and those mappings between keys
> and values should not change due to the insertion or deletion of unrelated
> keys.

Repeating your opion without further arguments doesn't lend any support
to that opinion. If within the problem space you are working on, such a change
would make sense as a step to generate the next mapping from the previous
one, i don't see what the problem is if one could make use of this.

> If the OP wants to create his own "StrangeDict", which he himself described
> as "terrible", then he can do so. But to make all dicts and lists behave in
> this "terrible" and "strange" way is a terrible idea.

Calling something a terrible idea isn't a strong arguement. Other "terrible"
ideas have made it in the language.

> [...]
>> Only if you use the special python meaning of (dictionary) values in this
>> context. If you use the ordinary (mathematical) meaning, there are lots of
>> values that don't have a key, like every two characters string.
> 
> Well, we're actually discussing Python dictionaries. So, damn straight, of
> course I'm going to use the meaning of words as they apply to dicts.

How so? We were talking about functions and how dicts could represent them.
So when next we talk about a characteristic of such functions I don't see
why we should use the meaning as they apply to dicts, since we weren't talking
about the dicts.

-- 
Antoon.

[toc] | [prev] | [next] | [standalone]

#106120

On Thu, 31 Mar 2016 06:07 am, Antoon Pardon wrote:

>> Because fundamentally, it doesn't matter whether dicts are surjections or
>> not. They're still many-to-one mappings, and those mappings between keys
>> and values should not change due to the insertion or deletion of
>> unrelated keys.
> 
> Repeating your opion without further arguments doesn't lend any support
> to that opinion. If within the problem space you are working on, such a
> change would make sense as a step to generate the next mapping from the
> previous one, i don't see what the problem is if one could make use of
> this.


Enough of the hypothetical arguments about what one could do or might do.
Let's see a concrete example of actual real world code used in production,
not a mickey-mouse toy program, where it is desirable that adding or
deleting one key will modify the rest of the keys in the mapping.

Arguing for the sake of arguing about what somebody might want is not
productive. Let's see some actual concrete use cases where you have a
database or mapping between keys and values, say something like this:

mapping = {
 # name: address
 "fred": "123 Smith Street",
 "george": "27 Main Road",
 "sally": "72a Short Street"
 }


where it is desirable to have this behaviour:

# adding a new key
mapping["mary"] = "31 King Street"
# changes the other keys
assert mapping["george"] != "27 Main Road"


No hypothetical cases where somebody might or could want this behaviour. I'm
not interested in "mights" and "coulds". I want to see an actual
application where adding a new key to a mapping is expected to change the
other keys.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.python

csiph-web